laporan modul 6 graph
Post on 04-Apr-2015
729 Views
Preview:
TRANSCRIPT
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’)
public boolean wasVisited;
// ------------------------------------------------------------
public Vertex(char lab) // constructor
{
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;
// -----------------------------------------------------------
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;
theStack = new StackX();
} // end constructor
// -----------------------------------------------------------
public void addVertex(char lab)
{
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);
}
// ------------------------------------------------------------
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.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.dfs(); // depth-first search
System.out.println();
} // end main()
} // end class Graph
////////////////////////////////////////////////////////////////
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 final int SIZE = 20;
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
{
public char label; // label (e.g. ‘A’)
public boolean wasVisited;
// -------------------------------------------------------------
public Vertex(char lab) // constructor
{
label = lab;
wasVisited = false;
}
// -------------------------------------------------------------
} // end class Vertex
////////////////////////////////////////////////////////////////
Public class BFS
{
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 Queue theQueue;
// ------------------
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;
theQueue = new Queue();
} // end constructor
// -------------------------------------------------------------
public void addVertex(char lab)
{
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);
}
// -------------------------------------------------------------
public void bfs() // breadth-first search
{ // begin at vertex 0
vertexList[0].wasVisited = true; // mark it
displayVertex(0); // display it
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
for(int j=0; j<nVerts; j++) // reset flags
vertexList[j].wasVisited = false;
} // end bfs()
// -------------------------------------------------------------
// 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)
{
BFS theGraph = new BFS();
theGraph.addVertex('A'); // 0 (start for dfs)
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.bfs(); // breadth-first search
System.out.println();
} // end main()
} // end class Graph
////////////////////////////////////////////////////////////////
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 final int MAX_VERTS = 20;
private Vertex vertexList[]; // array of vertices
public int adjMat[][]; // adjacency matrix
public int nVerts; // current number of vertices
// -------------------------------------------------------------
public Graph1() // 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[])
{
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.addVertex('2'); // 1
theGraph.addVertex('3'); // 2
theGraph.addVertex('4'); // 3
theGraph.addEdge(0,2); // AB
theGraph.addEdge(1,2); // BC
theGraph.addEdge(2,3); // AD // GRAPH A
System.out.print("Visits: ");
theGraph.displayVertex(0);
theGraph.displayVertex(1);
theGraph.displayVertex(2);
theGraph.displayVertex(3);
System.out.println();
}
if(a == 2){
theGraph.addVertex('1'); // 0
theGraph.addVertex('2'); // 1
theGraph.addVertex('3'); // 2
theGraph.addVertex('4'); // 3
theGraph.addVertex('5'); // 4
theGraph.addVertex('6'); // 5
theGraph.addEdge(0,1); // AB
theGraph.addEdge(0,2); // BC
theGraph.addEdge(0,4); // AD
theGraph.addEdge(1,3); // AB
theGraph.addEdge(2,5); // BC
theGraph.addEdge(3,4); // AD
theGraph.addEdge(3,5); // AB
theGraph.addEdge(4,5); // BC // GRAPH B
System.out.print("Visits: ");
theGraph.displayVertex(0);
theGraph.displayVertex(1);
theGraph.displayVertex(2);
theGraph.displayVertex(3);
theGraph.displayVertex(4);
theGraph.displayVertex(5);
System.out.println();
}
if(a == 3){
theGraph.addVertex('1'); // 0
theGraph.addVertex('2'); // 1
theGraph.addVertex('3'); // 2
theGraph.addVertex('4'); // 3
theGraph.addEdge(0,1); // AB
theGraph.addEdge(1,0); // BC
theGraph.addEdge(0,2); // AD
theGraph.addEdge(2,0); // AB
theGraph.addEdge(1,3); // BC
theGraph.addEdge(3,1); // AD
theGraph.addEdge(2,3); // AB
theGraph.addEdge(3,2); // BC // GRAPH C
System.out.print("Visits: ");
theGraph.displayVertex(0);
theGraph.displayVertex(1);
theGraph.displayVertex(2);
theGraph.displayVertex(3);
System.out.println();
}
if(a == 4){
theGraph.addVertex('1'); // 0
theGraph.addVertex('2'); // 1
theGraph.addVertex('3'); // 2
theGraph.addVertex('4'); // 3
theGraph.addVertex('5'); // 4
theGraph.addEdge(0,1); // AB
theGraph.addEdge(0,3); // BC
theGraph.addEdge(2,1); // AD
theGraph.addEdge(3,2); // AB
theGraph.addEdge(2,4); // BC
theGraph.addEdge(4,1); // BC // GRAPH D
System.out.print("Visits: ");
theGraph.displayVertex(0);
theGraph.displayVertex(1);
theGraph.displayVertex(2);
theGraph.displayVertex(3);
theGraph.displayVertex(4);
System.out.println();
}
}
} // end class Graph
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 {
public final int MAX_VERTS = 20;
private Vertex vertexList[];
public int adjMat[][];
public int nVerts;
public Graph() {
vertexList = new Vertex[MAX_VERTS];
adjMat = new int[MAX_VERTS][MAX_VERTS];
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) {
vertexList[nVerts++] = new Vertex(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){
System.out.print(vertexList[v].label);
}
class Vertex {
public char label;
public boolean wasVisited;
public Vertex(char lab){
label = lab;
wasVisited = false;
}
}
public static void main (String args[])
{
Graph theGraph = new Graph();
theGraph.addVertex('A');
theGraph.addVertex('B');
theGraph.addVertex('C');
theGraph.addVertex('D');
theGraph.addVertex('E');
System.out.print("Graph: ");
theGraph.displayVertex(0);
theGraph.displayVertex(1);
theGraph.displayVertex(2);
theGraph.displayVertex(3);
theGraph.displayVertex(4);
System.out.print("\n\nWeight edge AB:");
theGraph.addEdge(0, 1,5);
System.out.print("Weight edge BC:");
theGraph.addEdge(1, 2,3);
System.out.print("Weight edge AD:");
theGraph.addEdge(0, 3,2);
System.out.print("Weight edge DE:");
theGraph.addEdge(3, 4,1);
}
}
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).
theGraph.displayVertex(1); � Statement ini merupakan pemanggilan vertex 1. maka vertex
1 ditampilkan (B)
theGraph.displayVertex(2); � Statement ini merupakan pemanggilan vertex 2. maka vertex
2 ditampilkan (C).
theGraph.displayVertex(3); � Statement ini merupakan pemanggilan vertex 3. maka vertex
3 ditampilkan (D).
theGraph.displayVertex(4); � Statement ini merupakan pemanggilan vertex 4. maka vertex
4 ditampilkan (E).
Dapat digambarkan graph-nya adalah sebagai berikut :
Output program 2:
--------------------------------------------- 3 ------------------------------------------ package modul6_algodat_mika;
class StackX
{
private final int SIZE = 20;
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 char label; // label (e.g. ‘A’)
public boolean wasVisited;
// ------------------------------------------------------------
public Vertex(char lab)
{
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;
// -----------------------------------------------------------
public DFS()
{
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;
theStack = new StackX();
}
public void addVertex(char lab)
{
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);
}
// ------------------------------------------------------------
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');
theGraph.addVertex('B');
theGraph.addVertex('C');
theGraph.addVertex('D');
theGraph.addVertex('E');
theGraph.addVertex('F');
theGraph.addEdge(0,1);
theGraph.addEdge(0,3);
theGraph.addEdge(1,2);
theGraph.addEdge(1,3);
theGraph.addEdge(2,5);
theGraph.addEdge(3,5);
theGraph.addEdge(5,4);
System.out.print("Visits: ");
theGraph.dfs();
System.out.println();
}
}
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 boolean wasVisited;
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() {
vertexList = new Vertex[MAX_VERTS];
adjMat = new int[MAX_VERTS][MAX_VERTS];
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);
}
}
for(int j=0; j<nVerts; j++)
vertexList[j].wasVisited = false;
}
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;}
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);
theGraph.addEdge(0, 2);
theGraph.addEdge(0, 3);
theGraph.addEdge(1, 3);
theGraph.addEdge(2, 0);
theGraph.addEdge(2, 1);
theGraph.addEdge(3, 1);
theGraph.addEdge(3, 2);
System.out.print("Visits (BFS): ");
theGraph.bfs();
System.out.println();
System.out.println("Weight Edge : ");
theGraph.displayEdge(0, 1, 1);
System.out.println("");
theGraph.displayEdge(0, 2, 9);
System.out.println("");
theGraph.displayEdge(0, 3, 6);
System.out.println("");
theGraph.displayEdge(1, 3, 3);
System.out.println("");
theGraph.displayEdge(2, 0, 1);
System.out.println("");
theGraph.displayEdge(2, 1, 2);
System.out.println("");
theGraph.displayEdge(3, 1, 3);
System.out.println("");
theGraph.displayEdge(3, 2, 4);
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,
dan diberi bobot(weight) 9.
displayEdge(0, 3, 6) � artinya kita menghubungkan array index 0 ke index 3 yaitu X ke T,
dan diberi bobot(weight) 6.
displayEdge(1, 3, 3) � artinya kita menghubungkan array index 1 ke index 3 yaitu Y ke T,
dan diberi bobot(weight) 3.
displayEdge(2, 0, 1) � artinya kita menghubungkan array index 2 ke index 0 yaitu S ke X,
dan diberi bobot(weight) 1.
displayEdge(2, 1, 2) � artinya kita menghubungkan array index 2 ke index 1 yaitu S ke Y,
dan diberi bobot(weight) 2.
displayEdge(3, 1, 3) � artinya kita menghubungkan array index 3 ke index 1 yaitu T ke Y,
dan diberi bobot(weight) 3.
displayEdge(3, 2, 4) � artinya kita menghubungkan array index 3 ke index 2 yaitu T ke S,
dan diberi bobot(weight) 4.
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 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(String 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);
}
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 boolean wasVisited;
public Vertex(String lab) // constructor
{
label = lab;
wasVisited = false;
}
} // end class Vertex
// -------------------------------------------------------------
public static void main (String args[])
{
Graph theGraph = new Graph();
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: ");
theGraph.displayVertex(0);
System.out.print("\nindex 1: ");
theGraph.displayVertex(1);
System.out.print("\nindex 2: ");
theGraph.displayVertex(2);
System.out.print("\nindex 3: ");
theGraph.displayVertex(3);
System.out.print("\nindex 4: ");
theGraph.displayVertex(4);
System.out.print("\nindex 5: ");
theGraph.displayVertex(5);
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).
top related