MODUL STRUKTUR DATA

PRAKTIKUM GRAPH

1. Tujuan
Tujuan Instruksional Umum :
Mampu mengimplementasikan Graph untuk kasus sederhana.

Tujuan Instruksional Khusus :

1. Dapat menjelaskan konsep Graph
2. Dapat menyajikan Graph dengan menggunakan matrix incident
3. Dapat menyajikan Graph dengan menggunakan matrix adjacent

2. Dasar Teori
Graph adalah kumpulan dari simpul dan busur yang secara matematis dinyatakan
sebagai :
G = (V, E)
Dimana
G = Graph
V = Simpul atau Vertex, atau Node, atau Titik
E = Busur atau Edge, atau arc
Contoh Graph :
v1

e1

B c

e4 e3

v3

Graph G

Vertex V yaitu v1,v2,v3,v4

Edge E yaitu e1, e2, e3, e4

Dilihat dari busurnya, Graph terbagi menjadi 2 yaitu directed graph dan undirected
graph. Pada directed graph busurnya memiliki arah dan sebaliknya pada undirected
graph busurnya tidak memiliki arah.

Gambar Graph G sebelumnya merupakan contoh undirected graph.

Contoh Directed Graph :

v1

e1 e2

B c

e4 e3

Pada directed graph, urutan simpul memiliki arti.

Graph Berbobot (weighted graph)
- Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2
buah simpul, maka busur tersebut dinyatakan memiliki bobot.
- Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik,
jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, waktu yang
dibutuhkan untuk pengerjaan suatu aktifitas, dll.

Contoh:
v1

A 7

8 5

B c

9 2

v3

Terminologi Graph :
- Incident. Jika e merupakan busur dengan simpul-simpulnya adalah x dan y
yang ditulis e=(x,y), maka x dan y disebut “terletak” pada e, dan e disebut
incident dengan x dan y.
- Degree sebuah simpul adalah jumlah busur yang incident dengan simpul
tersebut.
- Indegree sebuah simpul pada graph berarah adalah jumlah busur yang
kepalanya incident dengan simpul tersebut, atau jumlah busur yang “masuk”
atau menuju simpul tersebut.
 - Outdegree sebuah simpul pada graph berarah adalah jumlah busur yang
ekornya incident dengan simpul tersebut, atau jumlah busur yang “keluar”
atau berasal dari simpul tersebut.
- Adjacent
Pada graph tidah berarah, 2 buah simpul disebut adjacent bila ada busur yang
menghubungkan kedua simpul tersebut.
Pada graph berarah, simpul x disebut adjacent dengan simpul y bila ada busur
dari x ke y.
- Successor dan Predecessor
Pada graph berarah, bila simpul v adjacent dengan simpul w, maka simpul v
adalah successor simpul w, dan simpul w adalah predecessor dari simpul v.
- Path
Sebuah path adalah serangkaian simpul-simpul yang berbeda, yang adjacent
secara berturut-turut dari simpul satu ke simpul berikutnya.

Representasi Graph dengan Matrix

Adjacency Matrix Undirected Graph

Contoh Graph:

B c

Matrix Adjacency:
Nyatakan 1 jika berhubungan 0 jika tidak
 A B C D

A 0 1 1 0

B 1 0 0 1

C 1 0 0 1

D 0 1 1 0

Adjacency Matrix Directed Graph

Contoh Graph:

B c

Dari\Ke A B C D

A 0 1 1 0

B 0 0 0 1

C 0 0 0 1

D 0 0 0 0

 Ke …
Untuk Graph berbobot jika ada hubungan maka angka 1 dapat diganti dengan
bobotnya.

Incidence Matrix Undirected Graph

Contoh Graph:

e1 e2

B c

e4 e3

Matrix Incidence:
Nyatakan 1 jika berhubungan 0 jika tidak
e1 e2 e3 e4

A 1 1 0 0

B 1 0 0 1

C 0 1 1 0

D 0 0 1 1
3. Percobaan
PERCOBAAN 1 : Penyajian Graph
1. Buatlah Proyek Baru – Java Application - dengan nama CobaGraph
2. Buatlah class baru dengan nama [Link], source code tampak seperti
berikut:

public class Vertex {

private String label;

private boolean wasVisited;

public Vertex(String label) {

[Link] = label;
[Link] = false;
}

public String getLabel() {

return label;
}

public void setLabel(String label) {

[Link] = label;
}

public boolean isWasVisited() {

return wasVisited;
}

public void setWasVisited(boolean wasVisited) {

[Link] = wasVisited;
}

}
3. Buatlah class baru dengan nama [Link], source code tampak seperti
berikut:

public class Edge {

private String label;
private Vertex fromVertex;
private Vertex toVertex;
private Double weight;

public Edge(String label, Vertex fromVertex, Vertex toVertex)

{
[Link] = label;
[Link] = fromVertex;
 [Link] = toVertex;
[Link] = 0.0;
}

public Edge(String label, Vertex fromVertex, Vertex toVertex,

Double weight) {
[Link] = label;
[Link] = fromVertex;
[Link] = toVertex;
[Link] = weight;
}

public Double getWeight() {

return weight;
}

public String getLabel() {

return label;
}

public void setLabel(String label) {

[Link] = label;
}

public void setWeight(Double weight) {

[Link] = weight;
}

public Vertex getFromVertex() {

return fromVertex;
}

public void setFromVertex(Vertex fromVertex) {

[Link] = fromVertex;
}

public Vertex getToVertex() {

return toVertex;
}

public void setToVertex(Vertex toVertex) {

[Link] = toVertex;
}

}
4. Buatlah class baru dengan nama [Link], source code tampak seperti
berikut:

public class Graph {

 private int numVertices;
private int numEdges;

private Vertex vertices[];

private Edge edges[];

private boolean isVertexExist(Vertex vertex) {

for (int i = 0; i < numVertices; i++) {
if
(vertices[i].getLabel().contentEquals([Link]())) {
return true;
}
}
return false;
}

private int getVertexIndex(Vertex vertex) {

for (int i = 0; i < numVertices; i++) {
if
(vertices[i].getLabel().contentEquals([Link]())) {
return i;
}
}
return -1;
}

public void addVertex(Vertex vertex) {

if (isVertexExist(vertex)) {
[Link]("Vertex Already Exist");
return;
}
vertices[numVertices] = vertex;
++numVertices;
}

public Graph() {
[Link] = new Vertex[10];
[Link] = new Edge[20];
}

public void addEdge(Vertex fromVertex, Vertex toVertex) {

if (!isVertexExist(fromVertex)) {
[Link]("From Vertex does not exist");
return;
}
if (!isVertexExist(toVertex))
{ [Link]("To Vertex does not
exist");
}

edges[numEdges] = new Edge("e" +

[Link](numEdges), fromVertex, toVertex);
++numEdges;
 }

public void addEdge(Vertex fromVertex, Vertex toVertex,

Double weight) {
if (!isVertexExist(fromVertex))
{ [Link]("From Vertex does not exist");
return;
}
if (!isVertexExist(toVertex))
{ [Link]("To Vertex does not
exist");
}

edges[numEdges] = new Edge("e" +

[Link](numEdges), fromVertex, toVertex, weight);
++numEdges;
}
}

5. Mencoba Program. Modifikasi method main pada Class CobaGraph sehingga

terlihat seperti source berikut:

public static void main(String[] args)

{ Graph myGraph = new Graph();

Vertex a = new Vertex("A");

Vertex b = new Vertex("B");
Vertex c = new Vertex("C");
Vertex d = new Vertex("D");
Vertex e = new Vertex("E");

[Link](a);
[Link](b);
[Link](c);
[Link](d);

[Link](a, b);
[Link](a, d);
[Link](c, a);
[Link](b, d);
[Link](d, c);
}
Jalankanlah program tersebut. Gambarkanlah bentuk Graphnya !
PERCOBAAN 2 : Adjacent Matrix

1. Modifikasilah class [Link] pada praktikum sebelumnya dengan

menambahkan method public void displayAdjacent().

2. Mencoba Program. Gunakan method tersebut pada main pada Class

CobaGraph. Contoh Output tampak seperti gambar berikut :

PERCOBAAN 3 : Incidence Matrix

1. Modifikasilah class [Link] pada praktikum sebelumnya dengan
menambahkan method public void displayIncidence().

2. Mencoba Program. Gunakan method tersebut pada main pada Class

CobaGraph. Contoh Output tampak seperti gambar berikut :

4. Latihan dan Evaluasi

1. Disconnected Graph adalah bentuk graph dimana salah satu vertexnya tidak
memiliki edge. Modifikasilah program diatas yang akan memunculkan pesan
 “Disconnected Graph” jika dijumpai graph tersebut
tergolong disconnected Graph.
2. Complete Graph adalah jenis Graph dimana tiap
vertexnya terhubung secara langsung dengan vertex
lainnya. Modifikasilah program diatas yang akan
memunculkan pesan “Complete Graph” jika dijumpai
graph tersebut tergolong disconnected Graph.
3. Cetaklah indegree dan outdegree dari sebuah vertex/simpul.

5. Referensi
1. Dale, Nell B., et al. 2001. Object Oriented Data
Structured Using Java. Sudbury: Jones and
Bartlett Publishers, Inc.
2. Hubbard, John R. 2007. Data Structure With Java.
New York: McGraw-Hill Companies, Inc.