Algoritma Struktur Data
2024
MODUL PRAKTIKUM ALGORITMA DAN STRUKTUR DATA
MODUL 9
GRAPH
Graph adalah kumpulan dari simpul dan busur yang secara matematis dinyatakan sebagai
berikut:
G = (V, E)
Dimana:
G = Graph
V = Simpul atau Vertex, atau Node, atau Titik E = Busur atau Edge, atau arc
A. Jenis Graph
1. Graph berarah dan tak berarah
Dapat dilihat dari bentuk busur yang artinya urutan penyebutan pasangan 2 simpul.
• Graph tak berarah (undirected graph atau non-directed graph):
o Urutan simpul dalam sebuah busur tidak dipentingkan. Misalkan busur e1
dapatdisebut busur AB atau BA.
• Graph berarah (directed graph):
o Urutan simpul mempunyai arti. Mis busur AB adalah e1 sedangkan busur
BA adalah e8.
2. Graph berbobot (Wiehted Graph)
• Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul,
maka busur tersebut dinyatakan memiliki bobot.
Praktikum Sistem Informasi 2024 1
MODUL PRAKTIKUM ALGORITMA DAN STRUKTUR DATA
• Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah
rata-rata kendaraan perhari yang melalui sebuah jalan, dll.
Panjang busur (atau bobot) mungkin tida digambarkan secara panjang yang proporsional
dengan bobotnya. Misal bobot 5 digambarkan lebih panjang dari 7.
B. Istilah pada Graph
1. Incident
Jika e merupakan busur dengan simpul – simpulnya adalah v dan w yang ditulis e = (v, w),
maka v dan w disebut “terletak” pada e, dan e disebut incident dengan v dan w.
2. Degree (derjata), indegree dan outdegree
• 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.
3. Adjacent
Pada graph tidak berarah, 2 buah simpul disebut adjacent bila ada busur yang
menghubungkan kedua simpul tersebut simpul v dan w disebut adjacent.
Pada graph berarah, simpul v disebut adjacent dengan simpul w bila ada busur w ke v
ke v.
Praktikum Sistem Informasi 2024 2
MODUL PRAKTIKUM ALGORITMA DAN STRUKTUR DATA
4. Successor dan Predecessor
Dalam graf berarah, jika simpul v bertetangga dengan simpul w, maka w adalah successor
v, dan v adalah predecessor dari w.
5. Path
Sebuah path adalah serangkaian simpul-simpul yang berbeda, yang adjacentsecara
berturut-turut dari simpul satu ke simpul berikutnya.
C. Contoh Implementasi Garph dalam Python
"""
A Python program to demonstrate the adjacency
list representation of the graph
"""
# A class to represent the adjacency list of the node
class AdjNode:
def init (self, data):
[Link] = data
[Link] = None
# A class to represent a graph. A graph
# is the list of the adjacency lists.
# Size of the array will be the no. of the
# vertices "V"
class Graph:
def init (self, vertices):
self.V = vertices
[Link] = [None] * self.V
# Function to add an edge in an undirected graph
def add_edge(self, src, dest):
# Adding the node to the source node
node = AdjNode(dest)
[Link] = [Link][src]
[Link][src] = node
# Adding the source node to the destination as
# it is the undirected graph
node = AdjNode(src)
[Link] = [Link][dest]
[Link][dest] = node
# Function to print the graph
def print_graph(self):
for i in range(self.V):
print("Adjacency list of vertex {}\n head".format(i), end="")
temp = [Link][i]
while temp:
print(" -> {}".format([Link]), end="")
temp = [Link]
Praktikum Sistem Informasi 2024 3
MODUL PRAKTIKUM ALGORITMA DAN STRUKTUR DATA
print(" \n")
# Driver program to the above graph class
if name == " main ":
V = 5
graph = Graph(V)
graph.add_edge(0, 1)
graph.add_edge(0, 4)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(1, 4)
graph.add_edge(2, 3)
graph.add_edge(3, 4)
graph.print_graph()
Praktikum Sistem Informasi 2024 4