Sebuah graph itu direpresentasikan dengan dua buah himpunan, himpunan vertex (yang bulet”) sama edge (jalan dari 1 vertex ke vertex lain) G= (V,E)
Graph ada 2 jenis yaitu :
1.Undirected graph : graph yang edgenya tidak ada arah (1,3) dan (3,1) sama saja
2.Directed graph : graph yang edgenya ada arah <1,3> dan <3,1> berbeda
E(edge) Maximum bisa dicari dengan rumus dan tergantung dari jenis graph nya
1.Undirected graph : (N(N-1))/2
2.Directed graph : N(N-1)
Dimana N adalaj jumlah vertex
Contoh Undirected graph
Dari gambar diatas ada 4 vertex dan 6 edge
V = {0,1,2,3}
E = {(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}
Contoh Directed Graph
Dari gambar diatas ada 7 vertex dan 12 edge
V = {0,1,2,3,4,5,6,7,8,9}
E = {(0,1),(0,2),(1,4),(1,3),(3,0),(3,2),(3,5),(3,6),(4,3),(4,6),(5,2),(6,5)}
Terminologi
Simple path : Path yang verteks pertama dan terakhir berbeda
Cycle path : Simple path yang verteks pertama dan terakhir sama
Weighted graph : Graph yang setiap edgenya diberi bobot (nilai)
Degree (v) : Banyaknya edge yang berhubungan dengan verteks v
Indegree (v) : Banyaknya edge yang masuk (menuju) verteks v pada sebuah graph
Outdegree (V) : Banyaknya edge yang keluar dari verteks v pada sebuah graph
Adjacency List
adjacency list adalah jalan / path dari vertex X ke vertex Y
contoh (Unweighted Graph)
Ajdlist dari graph diatas (dari X bisa ke Y)
0 -> 1 1 -> 2 2 -> 3
0 -> 2 1 -> 3
0 -> 3
intinya adj list sama aja kyk edge (unweighted)
Misalkan graph diatas diberikan weight masing 2
adjlistnya menjadi (dari X bisa ke Y, dengan weight)
0 -> 1, 2 1 -> 2, 2 2 -> 3, 2
0 -> 2, 2 1 -> 3, 2
0 -> 3, 2
Transversal Graph
Mencari jalan atau transversal di graph ada 2 algoritma :
1.BFS (Breadth First Search)
2.DFS (Depth Fisrt Search)
BFS (Breadth First Search)
Di BFS intinya kita cari jalan menyebar, algoritma ini dibantu dengan menggunakan queue dan dilakukan sampai queue kosong
Contoh :
Misalkan kita mau tau path nya
proses nya (Visited = 0 belum pernah, visited = 1 sudah pernah d visited) dengan kondisi semua vertex visited = 0
Queue : 0
Visited[0] = 1
Selama Queue Tidak kosong
Dari 0 ternyata bisa ke 1 dan 2
Queue : 0 1 2
visited[1] = 1
visited[2] = 1
Printf : 0
Dequeue : 0
Queue : 1 2
Dari 1 ternyata bisa ke 3 dan 4
Queue : 1 2 3 4
visited[3] = 1
visited[4] = 1
printf : 1
Dequeue 1:
Queue : 2 3 4
Dari 2 ternyata bisa ke 5 dan 6
Queue 2 3 4 5 6
visited[5] = 1
visited[6] = 1
printf : 2
Dequeue : 2
Queue 3 4 5 6
dari 3 ternyata bisa ke 7
Queue 3 4 5 6 7
visited[7] = 1
printf : 3
Dequeue : 3
Queue 4 5 6 7
Dari 4 ternyata bisa ke 7, tapi visited[7] = 1 jadi
printf : 4
Dequeue : 4
Queue 5 6 7
Dari 5 ternyata bisa ke 7, tapi visited[7] = 1 jadi
printf : 5
Dequeue : 5
Queue : 6 7
Dari 6 ternyata bisa ke 7, tapi visited[7] = 1 jadi
printf : 6
Dequeue : 6
Queue : 7
Dari 7 g bisa kemana”
printf : 7
Dequeue : 7
Queue : Kosong
Program stop !
Path : 1 2 3 4 5 6 7
DFS (Depth Fisrt Search)
Depth Fisrt Search itu kita menelusuri sebuah graph sampe ke yang paling dalem baru telusuri yg lain, dibantu dengan stack atau bisa menggunakan rekursif. DFS dilakukan sampai stack kosong atau sampai semua vertex dikunjungi (jika menggunakan rekursif)
Contoh :
Misalkan kita mau tau path nya (cara berikut ini dibahas menggunakan rekursif)
proses nya (Visited = 0 belum pernah, visited = 1 sudah pernah d visited) dengan kondisi semua vertex visited = 0
visited[0] = 0 ?? Yes
printf : 0
visited[0] = 1
dari 0 ternyata bisa ke 1 dan 2
Menelusuri 1
visited[1] = 0 ?? Yes
printf : 1
visited[1] = 1
dari 1 ternyata bisa ke 3 dan 4
Menelusuri 3
visited[3] = 0 ?? Yes
printf : 3
visited[3] = 1
dari 3 ternyata bisa ke 7
Menelusuri 7
visited[7] = 0 ?? Yes
printf : 7
visited[7] = 1
dari 7 ternyata tidak bisa kemana – mana lagi, balik ke vertex sebelumnya
dari 3 ternyata tidak bisa kemana – mana lagi, balik ke vertex sebelumnya
dari 1 ternyata bisa ke 3 dan 4 tetapi visited[3] = 1 jadi tidak bisa dilalui
Menelusuri 4
visited[4] = 0 ?? Yes
printf : 4
visited[4] = 1
dari 4 ternyata bisa ke 7 tetapi visited[7] = 1 jadi tidak bisa dilalui, balik ke vertex sebelumnya
dari 1 ternyata bisa ke 3 dan 4 tetapi visited[3] = 1 dan visited[4] = 1 jadi tidak bisa dilalui, balik ke vertes sebelumnya
dari 0 ternyata bisa ke 1 dan 2 tetapi visited[1] = 1 jadi tidak bisa dilalui
Menelurusi 2
visited[2] = 0 ?? Yes
printf : 2
visited[2] = 1
dari 2 ternyata bisa ke 5 dan 6
menelusuri 5
visited[5] = 0 ?? Yes
printf : 5
visited[5] = 1
dari 5 ternyata bisa ke 7 tetapi visited[7] = 1 jadi tidak bisa dilalui, balik ke vertex sebelumnya
dari 2 ternyata bisa ke 5 dan 6 tetapi visited[6] = 1 jadi tidak bisa dilalui
Menelurusi 6
visited[6] = 0 ?? Yes
printf : 6
visited[6] = 1
dari 6 ternyata bisa ke 7 tetapi visited[7] = 1 jadi tidak bisa dilalui, balik ke vertex sebelumnya
dari 2 ternyata bisa ke 5 dan 6 tetapi visited[5] = 1 dan visited[6] = 1 jadi tidak bisa dilalui, balik ke vertes sebelumnya
dari 0 ternyata bisa ke 1 dan 2 tetapi visited[1] = 1 dan visited[2] = 1 jadi tidak bisa dilalui, balik ke vertes sebelumnya
Program Selesai !
Path : 0 1 3 7 4 2 5 6
Struktur Data 