laporan modul 6 graph

PRAKTIKUM ALGORITMA DAN STRUKTUR DATA

MODUL KE-6

GRAPH

DOSEN PEMBINA:

Nur Hayatin,S.ST

Nama Kelompok :

Revana Jian A. (09560002)

Iji Rahayu S. (09560006)

Mika Purnamasari (09560014)

Musthafa Almanfaluthi (09560019)

Fauzan Azhima (09560042)

LABORATORIUM PEMROGRAMAN

PROGRAM STUDI TEKNIK INFORMATIKA

FAKULTAS TEKNIK

UNIVERSITAS MUHAMMADIYAH MALANG

2010

I. TUJUAN Mahasiswa mampu :

1. Memahami dan mampu menggunakan ADT Graph

II. ALAT YANG DIGUNAKAN Peralatan yang digunakan :

1.Perangkat PC yang terinstall Java

2.Editor Java

III. DASAR TEORI

Struktur Data Graph Struktur data yang berbentuk network/jaringan, hubungan antar elemen adalah

many-to-many. Keterhubungan dan jarak tidak langsung antara dua kota = data,

keterhubungan langsung dari kota-kota lainnya yang memperantarainya. Penerapan struktur

data linear atau hirarkis pada masalah graph dapat dilakukan tetapi kurang efisien. Struktur

data graph secara eksplisit menyatakan keterhubungan ini sehingga pencariannya langsung

(straight forward) dilakukan pada strukturnya sendiri.

1. Struktur Data Linear = keterhubungan sekuensial antara entitas data

2. Struktur Data Tree = keterhubungan hirarkis

3. Struktur Data Graph = keterhubungan tak terbatas antara entitas data.

Contoh graph : Informasi topologi jaringan dan keterhubungan antar kota-kota

Graph terdiri dari himpunan verteks (node) dan himpunan sisi (edge, arc). Verteks

menyatakan entitas-entitas data dan sisi menyatakan keterhubungan antara verteks.

Notasi matematis graph G adalah :

G = (V, E)

Sebuah sisi antara verteks x dan y ditulis {x, y}.

Subgraph : graph yang merupakan suatu subset (bagian) graph yang connected

Graph H = (V1, E1) disebut subgraph dari graph G jika V1 adalah himpunan bagian dari V

dan E1 himpunan bagian dari E.

Jenis Graph a. Directed Graph (Digraph)

Jika sisi-sisi graph hanya berlaku satu arah. Misalnya : {x,y} yaitu arah x ke y, bukan

dari y ke x; x disebut origin dan y disebut terminus. Secara notasi sisi digraph ditulis sebagai

vektor (x, y).

Contoh Digraph G = {V, E} :

V = {A, B, C, D, E, F, G, H, I,J, K, L, M}

E = {(A,B),(A,C), (A,D), (A,F), (B,C), (B,H), (C,E), (C,G), (C,H), (C,I), (D,E),

(D,F), (D,G), (D,K), (D,L), (E,F), (G,I), (G,K), (H,I), (I,J), (I,M), (J,K),

(J,M), (L,K), (L,M)}.

b. Graph Tak Berarah (Undirected Graph atau Undigraph) Setiap sisi {x, y} berlaku pada kedua arah: baik x ke y maupun y ke x. Secara grafis

sisi pada undigraph tidak memiliki mata panah dan secara notasional menggunakan kurung

kurawal.

Contoh Undigraph G = {V, E}

V = {A, B, C, D, E, F, G, H, I,J, K, L, M}

E = { {A,B},{A,C}, {A,D}, {A,F}, {B,C}, {B,H}, {C,E}, {C,G}, {C,H}, {C,I}, {D,E},

{D,F}, {D,G}, {D,K}, {D,L}, {E,F}, {G,I}, {G,K}, {H,I}, {I,J}, {I,M}, {J,K},

{J,M}, {L,K}, {L,M}}.

Khusus graph, undigraph bisa sebagai digraph (panah di kedua ujung edge berlawanan).

Struktur data linear maupun hirarkis adalah juga graph. Node-node pada struktur linear

ataupun hirarkis adalah verteks-verteks dalam pengertian graph dengan sisi-sisinya

menyusun node-node tersebut secara linear atau hirarkis. Struktur data linear adalah juga

tree dengan pencabangan pada setiap node hanya satu atau tidak ada. Linear 1-way linked

list (digraph), linear 2-way linked list (undigraph).

Graph berbobot (Weighted Graph) Graph dengan sisi mempunyai Bobot/ Biaya. “Biaya" ini bisa mewakili banyak aspek: biaya

ekonomi suatu aktifitas, jarak geografis/tempuh, waktu tempuh, tingkat kesulitan, dan lain

sebagainya.

Contoh :

Graph ini merupakan Undirected Weighted Graph. Order dari verteks A = 4, verteks B = 3,

dst. Adjacentcy list dari D adalah = {A, E, F, G, K, L}.

Representasi Graph Adjacency Matrix

• Representasi Matrik ordo nxn ,

dimana n = vertex/node

• A(i,j) = 1, jika antara node i dan node j terdapat edge/terhubung.

Array Adjacency Lists

• Adjacency list for vertex i is a linear list of vertices adjacent from vertex i.

• An array of n adjacency lists.

Algoritma-Algoritma Pencarian Pencarian vertex adalah proses umum dalam graph. Terdapat 2 metode pencarian:

Depth First Search (DFS) : Pada setiap pencabangan, penelusuran verteks-verteks yang belum dikunjungi dilakukan

secara lengkap pada pencabangan pertama, kemudian selengkapnya pada pencabangan

kedua, dan seterusnya secara rekursif.

Algoritma Depth First Search :

1. Algoritma diawali pada vertex S dalam G

2. Kemudian algoritma menelusuri graph dengan suatu insiden edge (u, v) ke current

vertex u.

3. Jika edge (u, v) menunjuk ke suatu vertex v yang siap untuk dikunjungi, maka kita

ikuti jalur mundur ke current vertex u. Jika pada sisi lain, edge (u, v) menunjuk ke

vertex v yang tidak dikunjungi, maka kita pergi ke v dan v menjadi current vertex.

4. Kita proses ini hingga kita mencapai sasaran akhir.

5. Pada titik ini, kita mulai jalur mundur. Proses ini berakhir ketika jalur mundur

menunjuk balik ke awal vertex.

void graph()

{ for semua node u do

{ colour[u]=white;

p[u]=NULL;

}

time = 0;

for semua node u do

if colour[u] == white then

DFS(u);

}

void DFS(u)

{ visit(u); time = time + 1;

d[u] = time;colour[u] = grey;

for semua node v adjacent ke u do

{ if colour[v] == white then

{ p[v] = u; DFS(u); }

}

time = time + 1; f[u] = time;

colour[u] = black;

}

Breadth First Search (BFS) : Pada setiap pencabangan penelusuran verteks-verteks yang belum dikunjungi dilakukan

pada verteks-verteks adjacent, kemudian berturut-turut selengkapnya pada masing-masing

pencabangan dari setiap verteks adjacent tersebut secara rekursif.

Algoritma Breadth First Search :

BFS diawali dengan vertex yang diberikan, yang mana di level 0. Dalam stage pertama, kita

kunjungi semua vertex di level 1. Stage kedua, kita kunjungi semua vertex di level 2. Disini

vertex baru, yang mana adjacent ke vertex level 1, dan seterusnya. Penelusuran BFS

berakhir ketika setiap vertex selesai ditemui.

Implementasi algoritma BFS

Algoritma BFS menjadi kurang straightforward jika dinyatakan secara rekursif. Jadi

sebaiknya diimplementasikan secara nonrekursif dengan memanfaatkan queue sebagai

struktur data pendukung

void BFS()

{ Queue q = new Queue();

Vertex v, w, t;

for (setiap vertex v dalam G)

v.Status = false;

for (setiap vertex v dalam G)

{ if (v.Status == false)

{ v.Status = true; q.Enqueue(v);

while (EmptyQueue(Q) == false)

{ w = q.Dequeue();

visit(w);

for (setiap vertex T adjacent dari w)

{ if (t.Status == false)

{ t.Status = true;

q.Enqueue(t);

}

}

}

}

}

}

IV. PROSEDUR PELAKSANAAN Prosedur pelaksanaan praktikum adalah sebagai berikut :

1.Mahasiswa menerima tugas yang diberikan oleh dosen/asisten

2.Mahasiswa mengerjakan tugas yang diberikan

3.Asisten/dosen menilai pekerjaan mahasiswa

V. LATIHAN

1. Class Graph.java, menggunakan representasi adjacency matrix.

public class Graph {

public final int MAX_VERTS = 20;

private Vertex vertexList[]; // array of vertices

public int adjMat[][]; // adjacency matrix public int nVerts; // current number of vertices

// -------------------------------------------------------------

public Graph() // constructor

{ vertexList = new Vertex[MAX_VERTS];

// adjacency matrix

adjMat = new int[MAX_VERTS][MAX_VERTS];

nVerts = 0;

for(int j=0; j<MAX_VERTS; j++) // set adjacency

for(int k=0; k<MAX_VERTS; k++) // matrix to 0

adjMat[j][k] = 0; } // end constructor

// -------------------------------------------------------------

public void addVertex(char lab) // argument is label

{ vertexList[nVerts++] = new Vertex(lab);

}

// -------------------------------------------------------------

public void addEdge(int start, int end)

{

adjMat[start][end] = 1;

adjMat[end][start] = 1;

}

// -------------------------------------------------------------

public void displayVertex(int v)

{ System.out.print(vertexList[v].label);

}

class Vertex

{ public char label; // label (e.g. ‘A’)

public boolean wasVisited;

public Vertex(char lab) // constructor

{

label = lab;

wasVisited = false;

}

} // end class Vertex // -------------------------------------------------------------

public static void main (String args[])

{

Graph theGraph = new Graph();

theGraph.addVertex('A'); // 0

theGraph.addVertex('B'); // 1

theGraph.addVertex('C'); // 2

theGraph.addVertex('D'); // 3

theGraph.addVertex('E'); // 4

theGraph.addEdge(0, 1); // AB

theGraph.addEdge(1, 2); // BC

theGraph.addEdge(0, 3); // AD

theGraph.addEdge(3, 4); // DE

System.out.print("Visits: ");

theGraph.displayVertex(1);

System.out.println();

}

} // end class Graph

2. Class DFS.java didalam kelas ini ada method pencarian DFS

class StackX

{

private final int SIZE = 20;

private int[] st;

private int top;

// -----------------------------------------------------------

public StackX() // constructor

{

st = new int[SIZE]; // make array

top = -1;

}

// -----------------------------------------------------------

public void push(int j) // put item on stack { st[++top] = j; }

// -----------------------------------------------------------

public int pop() // take item off stack

{ return st[top--]; }

// ------------------------------------------------------------

public int peek() // peek at top of stack

{ return st[top]; }

// ------------------------------------------------------------

public boolean isEmpty() // true if nothing on stack-

{ return (top == -1); }

// ------------------------------------------------------------

} // end class StackX

////////////////////////////////////////////////////////////////

class Vertex

{

public char label; // label (e.g. ‘A’)


// ------------------------------------------------------------


{

label = lab;

wasVisited = false;

}

// ------------------------------------------------------------

} // end class Vertex

////////////////////////////////////////////////////////////////

Public class DFS

{

private final int MAX_VERTS = 20;

private Vertex vertexList[]; // list of vertices

private int adjMat[][]; // adjacency matrix

private int nVerts; // current number of vertices

private StackX theStack;

// -----------------------------------------------------------


{

vertexList = new Vertex[MAX_VERTS];

// adjacency matrix


nVerts = 0;



adjMat[j][k] = 0;

theStack = new StackX();

} // end constructor

// -----------------------------------------------------------

public void addVertex(char lab)

{

vertexList[nVerts++] = new Vertex(lab);

}

// -----------------------------------------------------------


{



}

// ------------------------------------------------------------


{

System.out.print(vertexList[v].label);

}

// ------------------------------------------------------------

public void dfs() // depth-first search

{ // begin at vertex 0

vertexList[0].wasVisited = true; // mark it

displayVertex(0); // display it

theStack.push(0); // push it

while( !theStack.isEmpty() ) // until stack empty,

{

// get an unvisited vertex adjacent to stack top

int v = getAdjUnvisitedVertex( theStack.peek() );

if(v == -1) // if no such vertex,

theStack.pop();

else // if it exists,

{

vertexList[v].wasVisited = true; // mark it

displayVertex(v); // display it

theStack.push(v); // push it

}

} // end while

// stack is empty, so we’re done

for(int j=0; j<nVerts; j++) // reset flags

vertexList[j].wasVisited = false;

} // end dfs

// ------------------------------------------------------------

// returns an unvisited vertex adj to v

public int getAdjUnvisitedVertex(int v)

{

for(int j=0; j<nVerts; j++)

if(adjMat[v][j]==1 && vertexList[j].wasVisited==false)

return j;

return -1;

} // end getAdjUnvisitedVertex()

// ------------------------------------------------------------

public static void main(String[] args)

{

DFS theGraph = new DFS();

theGraph.addVertex('A'); // 0 (start for dfs)










theGraph.dfs(); // depth-first search


} // end main()


////////////////////////////////////////////////////////////////

3. Class BFS.Java didalam kelas ini ada method pencarian BFS

// bfs.java

// demonstrates breadth-first search

// to run this program: C>java BFSApp

////////////////////////////////////////////////////////////////

class Queue

{


private int[] queArray;

private int front;

private int rear;

// -------------------------------------------------------------

public Queue() // constructor

{

queArray = new int[SIZE];

front = 0;

rear = -1;

}

// -------------------------------------------------------------

public void insert(int j) // put item at rear of queue

{

if(rear == SIZE-1)

rear = -1;

queArray[++rear] = j;

}

// -------------------------------------------------------------

public int remove() // take item from front of queue

{

int temp = queArray[front++];

if(front == SIZE)

front = 0;

return temp;

}

// -------------------------------------------------------------

public boolean isEmpty() // true if queue is empty

{

return ( rear+1==front || (front+SIZE-1==rear) );

}

// -------------------------------------------------------------

} // end class Queue

////////////////////////////////////////////////////////////////

class Vertex

{



// -------------------------------------------------------------


{

label = lab;

wasVisited = false;

}

// -------------------------------------------------------------


////////////////////////////////////////////////////////////////

Public class BFS

{





private Queue theQueue;

// ------------------


{


// adjacency matrix


nVerts = 0;



adjMat[j][k] = 0;

theQueue = new Queue();


// -------------------------------------------------------------


{


}

// -------------------------------------------------------------


{



}

// -------------------------------------------------------------


{


}

// -------------------------------------------------------------

public void bfs() // breadth-first search




theQueue.insert(0); // insert at tail

int v2;

while( !theQueue.isEmpty() ) // until queue empty,

{

int v1 = theQueue.remove(); // remove vertex at head

// until it has no unvisited neighbors

while( (v2=getAdjUnvisitedVertex(v1)) != -1 )

{ // get one,

vertexList[v2].wasVisited = true; // mark it

displayVertex(v2); // display it

theQueue.insert(v2); // insert it

} // end while

} // end while(queue not empty)

// queue is empty, so we’re done



} // end bfs()

// -------------------------------------------------------------



{



return j;

return -1;


// -------------------------------------------------------------


{

BFS theGraph = new BFS();

theGraph.addVertex('A'); // 0 (start for dfs)










theGraph.bfs(); // breadth-first search


} // end main()


////////////////////////////////////////////////////////////////

VI. TUGAS PRAKTIKUM

1. Dengan menggunakan class Graph.java, representasikan graph berikut kemudian

gambarkan graph-nya : a. V1 = {1,2,3,4}, E1 = {(1,3),(2,3),(3,4)} b. V1 = {1,2,3,4,5,6}, E2 = {(1,2),(1,3),(1,5) ,(2,4),(3,6) ,(4,5),(4,6) ,(5,6)} c. V1 = {1,2,3,4}, E3 = {(1,2),(2,1),(1,3) ,(3,1),(2,4) ,(4,2) ,(3,4) ,(4,3)} d. V1 = {1,2,3,4,5}, E5 = {(1,2),(1,4),(3,2),(4,3),(3,5),(5,2)}

2. Modifikasi program Graph.java sehingga class tersebut dapat digunakan untuk

representasi weight graph (graph berbobot).

3. Dengan memanfaatkan class yang ada pada latihan, telusuri dengan menggunakan

metode DFS untuk gambar graph berikut :

4. Terdapat Weight-graph yang disimpan dalam memory dengan matrix sebagai berikut :

=

0430

0021

3000

6910

T

S

Y

X

W

Tugas : Dengan memanfaatkan class yang ada pada latihan, telusuri dengan

menggunakan metode BFS dan gambarkan Graph-nya.

5. Modifikasi program yang sudah ada untuk mendapatkan gambar graph seperti berikut :

X Y S T

Dimana :

V = {Nina, Toni, Ale, Riza, Joko, Firda}

E={{Nina,Toni},{Toni,Riza},{Nina,Riza},{Toni,Ale},{Ale,Joko},{Riza,Joko},{Firda,Joko

}}

VII. HASIL PRAKTIKUM

--------------------------------------------- 1 ------------------------------------------ import java.util.Scanner;

public class Graph1

{



public int adjMat[][]; // adjacency matrix

public int nVerts; // current number of vertices

// -------------------------------------------------------------

public Graph1() // constructor

{


// adjacency matrix


nVerts = 0;



adjMat[j][k] = 0;


// -------------------------------------------------------------

public void addVertex(char lab) // argument is label

{


}

// -------------------------------------------------------------


{



}

// -------------------------------------------------------------


{


}

class Vertex

{




{

label = lab;

wasVisited = false;

}


// -------------------------------------------------------------


{

Scanner input = new Scanner (System.in);

System.out.println("Pilih Graph");

System.out.println("1. graph a");

System.out.println("2. graph b");

System.out.println("3. graph c");

System.out.println("4. graph d");

System.out.print("nomor ? : ");

int a = input.nextInt();

Graph1 theGraph = new Graph1();

if(a == 1){

theGraph.addVertex('1'); // 0




theGraph.addEdge(0,2); // AB

theGraph.addEdge(1,2); // BC

theGraph.addEdge(2,3); // AD // GRAPH A







}

if(a == 2){









theGraph.addEdge(0,4); // AD





theGraph.addEdge(4,5); // BC // GRAPH B









}

if(a == 3){












theGraph.addEdge(3,2); // BC // GRAPH C







}

if(a == 4){











theGraph.addEdge(4,1); // BC // GRAPH D








}

}


OUTPUT :

\

ANALISIS :

Program ini menggunakan class Graph.java dan program ini terdiri dari 4 buah graph, yaitu :

a. V1 = {1,2,3,4}, E1 = {(1,3),(2,3),(3,4)}

Graph ini adalah graph undigraph yang terdiri 4 vertex dan terdiri 3 edge.

b. V1 = {1,2,3,4,5,6}, E2 = {(1,2),(1,3),(1,5) ,(2,4),(3,6) ,(4,5),(4,6) ,(5,6)}

Graph ini adalah graph undigraph terdiri 6 vertex dan terdiri 8 edge.

c. V1 = {1,2,3,4}, E3 = {(1,2),(2,1),(1,3) ,(3,1),(2,4) ,(4,2) ,(3,4) ,(4,3)}\

Graph ini adalah graph digraph terdiri 4 vertex dan terdiri 8 edge.

d. V1 = {1,2,3,4,5}, E5 = {(1,2),(1,4),(3,2),(4,3),(3,5),(5,2)}

Graph ini adalah graph digraph terdiri 5 vertex dan terdiri 6 edge.

Ketika menjalankan program ini pertama-tama kita akan memilih graph mana yang mau

ditampilkan. Jika memilih 1 maka graph (a) akan ditampilkan vertex-vertex yang ada pada

graph (a) dan begitupun (b), (c) dan (d).

--------------------------------------------- 2 ------------------------------------------ package modul6_algodat_mika;

import java.awt.Label;

public class Graph {


private Vertex vertexList[];

public int adjMat[][];

public int nVerts;

public Graph() {



nVerts = 0;

for(int j=0; j<MAX_VERTS; j++)

for(int k=0; k<MAX_VERTS; k++)

adjMat[j][k] = 0;

}

public void addVertex(char lab) {


}

public void addEdge(int start, int end, int bobot){

adjMat[start][end] = bobot;

adjMat[end][start] = bobot;

System.out.println(" "+bobot);

}

public void displayVertex(int v){


}

class Vertex {

public char label;


public Vertex(char lab){

label = lab;

wasVisited = false;

}

}


{


theGraph.addVertex('A');

theGraph.addVertex('B');

theGraph.addVertex('C');

theGraph.addVertex('D');

theGraph.addVertex('E');

System.out.print("Graph: ");






System.out.print("\n\nWeight edge AB:");

theGraph.addEdge(0, 1,5);

System.out.print("Weight edge BC:");


System.out.print("Weight edge AD:");


System.out.print("Weight edge DE:");


}

}

Analisa program 2:

Program ini merupakan reperesentasi dari weight graph (graph berbobot), disini kita

membuat 5 vertex (A, B, C, D, E) yang disimpan kedalam array. Index aray dimulai dari

index 0, berarti :

Vertex A berada di index 0

Vertex B berada di index 1

Vertex C berada di index 2

Vertex D berada di index 3, dan

Vertex E berada di index 4

Kemudian kita membuat edge (hubungan antar vertex)

addEdge(0, 1, 5) � artinya menghubungkan array index 0 ke index 1 yaitu A ke B, dan

diberi bobot 5

addEdge(1, 2, 3) � artinya menghubungkan array index 1 ke index 2 yaitu B ke C, dan

diberi bobot 3.

addEdge(0, 3, 2) � artinya menghubungkan array index 0 ke index 3 yaitu A ke D, dan

diberi bobot 2.

addEdge(3, 4, 1) � artinya menghubungkan array index 3 ke index 4 yaitu D ke E, dan

diberi bobot 1.

theGraph.displayVertex(0); � Statement ini merupakan pemanggilan vertex 0. maka vertex

0 ditampilkan (A).


1 ditampilkan (B)


2 ditampilkan (C).


3 ditampilkan (D).


4 ditampilkan (E).

Dapat digambarkan graph-nya adalah sebagai berikut :

Output program 2:

--------------------------------------------- 3 ------------------------------------------ package modul6_algodat_mika;

class StackX

{


private int[] st;

private int top;

// -----------------------------------------------------------

public StackX()

{

st = new int[SIZE]; // make array

top = -1;

}

// -----------------------------------------------------------

public void push(int j) // put item on stack

{ st[++top] = j; }

// -----------------------------------------------------------

public int pop() // take item off stack

{ return st[top--]; }

// ------------------------------------------------------------

public int peek() // peek at top of stack

{ return st[top]; }

// ------------------------------------------------------------

public boolean isEmpty() // true if nothing on stack-

{ return (top == -1); }

// ------------------------------------------------------------

}

class Vertex

{



// ------------------------------------------------------------

public Vertex(char lab)

{

label = lab;

wasVisited = false;

}

// ------------------------------------------------------------


////////////////////////////////////////////////////////////////

public class DFS

{





private StackX theStack;

// -----------------------------------------------------------

public DFS()

{


// adjacency matrix


nVerts = 0;



adjMat[j][k] = 0;

theStack = new StackX();

}


{


}


{



}

// ------------------------------------------------------------


{


}

// ------------------------------------------------------------

public void dfs() // depth-first search




theStack.push(0); // push it

while( !theStack.isEmpty() ) // until stack empty,

{

// get an unvisited vertex adjacent to stack top

int v = getAdjUnvisitedVertex( theStack.peek() );

if(v == -1) // if no such vertex,

theStack.pop();

else // if it exists,

{

vertexList[v].wasVisited = true; // mark it

displayVertex(v); // display it

theStack.push(v); // push it

}

} // end while

// stack is empty, so we’re done



} // end dfs



{



return j;

return -1;



{

DFS theGraph = new DFS();

theGraph.addVertex('A');

theGraph.addVertex('B');

theGraph.addVertex('C');

theGraph.addVertex('D');

theGraph.addVertex('E');

theGraph.addVertex('F');

theGraph.addEdge(0,1);








theGraph.dfs();


}

}

Analisa program 3 : Program ini adalah program untuk menelusuri graph dengan metode DFS (Depth-First

Search), disini kita membuat 6 vertex (A,B,C,D,E,F) yang disimpan pada array.

Index array dimulai dari index 0, jadi vertex A terletak pada array index 0

vertex B pada index 1

vertex C pada index 2

vertex D pada index 3

vertex E pada index 4, dan

vertex F pada index 5.

Kemudian kita menghubungkan vertex-vertex tersebut (membuat edge) sesuai dengan

gambar graph yang ada pada soal 3.

addEdge(0,1) artinya kita menghubungkan array index 0 ke index 1 yaitu A ke B.

addEdge(0,3) artinya kita menghubungkan array index 0 ke index 3 yaitu A ke D.

addEdge(1,2) artinya kita menghubungkan array index 1 ke index 2 yaitu B ke C.

addEdge(1,3) artinya kita menghubungkan array index 1 ke index 3 yaitu B ke D.

addEdge(2,5) artinya kita menghubungkan array index 2 ke index 5 yaitu C ke F.

addEdge(3,5) artinya kita menghubungkan array index 3 ke index 5 yaitu D ke F.

addEdge(5,4) artinya kita menghubungkan array index 5 ke index 4 yaitu F ke E.

Setelah itu kita telusuri (visit) graph tersebut dengan metode DFS (metode penelusuran

percabang), dan hasilnya adalah seperti gambar berikut:

--------------------------------------------- 4 ------------------------------------------ class Queue

{

private final int SIZE = 10; //tidak dapat dirubah lagi

private int[] queArray;

private int front;

private int rear;

public Queue(){

queArray = new int[SIZE];

front = 0;

rear = -1;}

public void insert(int j){

if(rear == SIZE-1)

rear = -1;

queArray[++rear] = j;}

public int remove(){

int temp = queArray[front++];

if(front == SIZE)

front = 0;

return temp;}

public boolean isEmpty()

{return ( rear+1==front || (front+SIZE-1==rear) );}

}

class Vertex{

public char label;


public Vertex(char lab) {

label = lab;

wasVisited = false;}

}

public class BFS{

private final int MAX_VERTS = 10; //jumlah maksimal vertex

private Vertex vertexList[];

private int adjMat[][];

private int nVerts;

private Queue theQueue;

public BFS() {



nVerts = 0;

for(int j=0; j<MAX_VERTS; j++)

for(int k=0; k<MAX_VERTS; k++)

adjMat[j][k] = 0;

theQueue = new Queue();}

public void addVertex(char lab){

vertexList[nVerts++] = new Vertex(lab); }

public void addEdge(int start, int end){

adjMat[start][end] = 1; }

public void displayVertex(int v) {

System.out.print(vertexList[v].label);}

public void displayEdge(int start, int end , int weight) {

System.out.print(vertexList[start].label+""+vertexList[end].label+"="+weight);}

public void bfs() {

vertexList[0].wasVisited = true;

displayVertex(0);

theQueue.insert(0);

int v2;

while( !theQueue.isEmpty() )

{

int v1 = theQueue.remove();

while( (v2=getAdjUnvisitedVertex(v1)) != -1 )

{

vertexList[v2].wasVisited = true;

displayVertex(v2);

theQueue.insert(v2);

}

}



}

public int getAdjUnvisitedVertex(int v) {



return j;

return -1;}

public static void main(String[] args){

BFS theGraph = new BFS();

theGraph.addVertex('X');

theGraph.addVertex('Y');

theGraph.addVertex('S');

theGraph.addVertex('T');

theGraph.addEdge(0, 1);








System.out.print("Visits (BFS): ");

theGraph.bfs();


System.out.println("Weight Edge : ");

theGraph.displayEdge(0, 1, 1);

System.out.println("");















}

}

Analisa program 4: Program ini adalah program penelusuran graph dengan metode BFS(Breadth-First Search),

disini kita akan menelusuri graph yang memiliki matrix sebagai berikut:

=

0430

0021

3000

6910

T

S

Y

X

W

Terlebih dahulu kita membuat vertex-vertexnya, yaitu X Y S T yang disimpan pada array,

index array dimulai dari 0 berarti:

vertex X berada pada index 0,

vertex Y berada pada index 1,

vertex S berada pada index 2, dan

vertex T berada pada index 3.

Kemudian menghubungkan vertex-vertex tersebut (membuat edge-nya) dan menetapkan

nilai weight(bobot) dari masing-masing edge sesuai dengan matrix diatas.

displayEdge(0, 1, 1) � artinya kita menghubungkan array index 0 ke index 1 yaitu X ke Y,

dan diberi bobot(weight) 1.

displayEdge(0, 2, 9) � artinya kita menghubungkan array index 0 ke index 2 yaitu X ke S,


displayEdge(0, 3, 6) � artinya kita menghubungkan array index 0 ke index 3 yaitu X ke T,


displayEdge(1, 3, 3) � artinya kita menghubungkan array index 1 ke index 3 yaitu Y ke T,


displayEdge(2, 0, 1) � artinya kita menghubungkan array index 2 ke index 0 yaitu S ke X,


displayEdge(2, 1, 2) � artinya kita menghubungkan array index 2 ke index 1 yaitu S ke Y,


displayEdge(3, 1, 3) � artinya kita menghubungkan array index 3 ke index 1 yaitu T ke Y,


displayEdge(3, 2, 4) � artinya kita menghubungkan array index 3 ke index 2 yaitu T ke S,


Dari matrix diatas dapat digambarkan graph-nya adalah sebagai berikut:

X Y S T

Output program :

--------------------------------------------- 5 ------------------------------------------ import java.io.InputStream;

import java.util.Scanner;

public class Graph

{



public int adjMat[][]; // adjacency matrix

public int nVerts; // current number of vertices

// -------------------------------------------------------------


{


// adjacency matrix


nVerts = 0;



adjMat[j][k] = 0;


// -------------------------------------------------------------

public void addVertex(String lab) // argument is label

{


}

// -------------------------------------------------------------


{



}

// -------------------------------------------------------------


{


}

public void displayEdge(int v1, int v2)

{

System.out.print("Vertex Start = "+v1+"\nVertex End = "+v2+"\n");

System.out.print(vertexList[v1].label);

System.out.print(" -----> ");

System.out.print(vertexList[v2].label);

}

public void displayAdj(int x, int v){

System.out.print(adjMat[x][v]);

}

class Vertex{

public String label; // label (e.g. ‘A’)


public Vertex(String lab) // constructor

{

label = lab;

wasVisited = false;

}


// -------------------------------------------------------------


{


theGraph.addVertex("Nina"); // 0

theGraph.addVertex("Toni"); // 1

theGraph.addVertex("Ale"); // 2

theGraph.addVertex("Riza"); // 3

theGraph.addVertex("Joko"); // 4

theGraph.addVertex("Firda"); // 5

theGraph.addEdge(0, 1); // Nina-Toni

theGraph.addEdge(0, 3); // Nina-Riza

theGraph.addEdge(1, 3); // Toni-Riza

theGraph.addEdge(1, 2); // Toni-Ale

theGraph.addEdge(2, 4); // Ale-Joko

theGraph.addEdge(3, 4); // Riza-Joko

theGraph.addEdge(4, 5); // Joko-Firda

System.out.println("Nama-nama Vertex : ");

System.out.print("index 0: ");


System.out.print("\nindex 1: ");










System.out.println("\n--------------------");

Graph a =new Graph();

Scanner s = new Scanner (System.in);

System.out.print("1. Input Vertex Index = ");

int v1 ;

v1 = s.nextInt();

System.out.print("2. Input Vertex Index = ");

int v2;

v2 =s.nextInt();

System.out.print("\n");

theGraph.displayEdge(v1,v2);

System.out.print("\n\nAdjecency Matriks adalah = ");

theGraph.displayAdj(v1, v2);

System.out.print("\n");

}

}

Analisa program 5: Program ini adalah program untuk membuat sebuah graph, yaitu graph yang sesuai dengan

gambar yang ada pada soal 5.Disini kita membuat 6 vertex (Nina, Toni, Ale, Riza, Joko,

Firda), disimpan pada sebuah array, index array dimulai dengan index 0, berarti:

Nina berada pada array index 0

Toni berada pada array index 1

Ale berada pada array index 2

Riza berada pada array index 3

Joko berada pada array index 4

Firda berada pada array index 5

Kemudian kita menghubungkan vertex-vertex tersebut (membuat edge-nya) sesuai dengam

gambar pada soal 5.

Nina � Toni , berarti hubungkan array index 0 ke index 1

Nina � Riza , berarti hubungkan array index 0 ke index 3

Toni � Riza , berarti hubungkan array index 1 ke index 3

Toni � Ale , berarti hubungkan array index 1 ke index 2

Ale � Joko , berarti hubungkan array index 2 ke index 4

Riza � Joko , berarti hubungkan array index 3 ke index 4

Joko � Firda , berarti hubungkan array index 4 ke index 5

Pada program ini user perlu menginputkan index vertex, pertama inputkan index vertex start

(vertex asal-nya) kemudian inputkan lagi index vertex end (vertex tujuan).

Misalkan, user menginputkan vertex index pertama=0 dan vertex index kedua=1, berarti

vertex start adalah 0 dan vertex end adalah 1, yaitu Nina Toni

dan nilai Adjacency matrix-nya adalah 1.

VIII. KESIMPULAN

• Graph terdiri dari himpunan verteks (node) dan himpunan sisi (edge). Verteks

menyatakan entitas-entitas data dan sisi menyatakan keterhubungan antara verteks.

• Jenis-jenis graph:

o Directed graph(graf berarah)

o Undirected graph(graf tidak berarah), dan

o Weighted graph(graf berbobot).

• Algoritma Breadth-First Search (BFS) dan Depth-First Search (DFS) merupakan

algoritma untuk melakukan kunjungan pada simpul-simpul graf dengan cara yang

sistematis.

• BFS adalah algoritma pencarian graf yang mulai mencari dari simpul akar dan

kemudian mencari ke semua simpul yang bertetangga. Untuk setiap simpul-simpul

tetangga yang telah dikunjungi, simpul-simpul lain yang belum dikunjungi yang

bertetangga dengan simpul tersebut akan ditelusuri.

• BFS merupakan penelusuran graph perlevel.

• DFS adalah algoritma untuk melakukan traversal atau pencarian pada sebuah graf atau

pohon. Dimulai dari simpul akar, pencarian akan dilakukan dan mengeksplorasi sejauh

mungkin pada tiap cabang.

• DFS merupakan penelusuran graph percabang (child node).

laporan modul 6 graph

Documents