1. Pengertian Graph

Graph adalah struktur data matematika yang terdiri dari kumpulan simpul (node/vertex) yang terhubung oleh sisi (edge). Graf digunakan untuk merepresentasikan hubungan atau koneksi antara objek-objek dalam sebuah set.

Contoh sederhana untuk memahami konsep graf adalah dengan membayangkan sebuah jaringan sosial. Setiap orang dalam jaringan tersebut dapat direpresentasikan sebagai simpul, sedangkan hubungan antara mereka (misalnya pertemanan) dapat direpresentasikan sebagai sisi. Dengan graf, kita dapat melihat dan menganalisis hubungan antara orang-orang dalam jaringan tersebut.

2. ADT Graph

Graf merupakan kumpulan dari simpul (vertices) dan sisi-sisi (edges). Adapun terdapat beberapa istilah atau terminologi yang perlu dipahami mengenai graph yaitu:

1. Vertex/Simpul atau pada linked list biasa disebut node yang mana merupakan element atau object yang menyimpan data dan dapat saling terhubung satu sama lain.
2. Edge/Sisi, koneksi atau hubungan antar dua vertex dalam graph.
3. Directed Graph. jenis graph yang memiliki arah dalam edgenya.
4. Underected Graph, jenis graph yang tidak memiliki arah dalam edgenya.

Dapat dilihat perbedaan edge atau simpul dari kedua contoh graph di atas. Pada gambar sebelah kiri menunjukkan panah yang mana mengartikan edge dari vertex ke vertexnnya tetapi pada vertex sebelah kanan edge hanya berupa garis biasa yang menunjukkan bahwa tidak ada arah pada edgenya. Maksud dari arah disini adalah perpindahan vertex sebagai contoh:

• A -> B : Artinya dari vertex A dapat menelusuri atau mengakses ke vertex B tetapi tidak sebaliknya.
• A - B : Artinya dari vertex A dapat menelusuri atau mengakses ke vertex B dan sebaliknya.

3. Struktur Data untuk Grafik

Dalam representasi graf, terdapat empat struktur data yang umum digunakan.

3.1 Edge List

Edge List adalah representasi sederhana dari graf menggunakan daftar sisi. Setiap elemen dalam daftar ini adalah pasangan simpul yang saling terhubung.

Contoh kodingan Python untuk Edge List:

# Inisialisasi Edge List
edges = [(1, 2), (1, 3), (2, 3), (2, 4), (3, 4)]

# Contoh penggunaan Edge List untuk merepresentasikan graf
class Graph:
    def __init__(self, edges):
        self.edges = edges

    def display_edges(self):
        for edge in self.edges:
            print(edge)

graph = Graph(edges)
graph.display_edges()

3.2 Adjacency List

Adjacency List adalah representasi graf dengan menggunakan kamus (dictionary) di mana setiap simpul memiliki daftar simpul yang terhubung langsung dengannya.

Contoh kodingan Python untuk Adjacency List:

# Inisialisasi Adjacency List
adj_list = {
    1: [2, 3],
    2: [1, 3, 4],
    3: [1, 2, 4],
    4: [2, 3]
}

# Contoh penggunaan Adjacency List untuk merepresentasikan graf
class Graph:
    def __init__(self, adj_list):
        self.adj_list = adj_list

    def display_adj_list(self):
        for vertex, neighbors in self.adj_list.items():
            print(f"Vertex {vertex}: {neighbors}")

graph = Graph(adj_list)
graph.display_adj_list()

3.3 Adjacency Map

Adjacency Map adalah representasi graf dengan menggunakan kamus (dictionary) di mana setiap simpul memiliki kamus lain yang berisi informasi tentang sisi (edge) yang terhubung langsung dengan simpul tersebut dan atribut tambahan jika diperlukan.

Contoh kodingan Python untuk Adjacency Map:

# Inisialisasi Adjacency Map
adj_map = {
    1: {2: {'weight': 1}, 3: {'weight': 2}},
    2: {1: {'weight': 1}, 3: {'weight': 3}, 4: {'weight': 4}},
    3: {1: {'weight': 2}, 2: {'weight': 3}, 4: {'weight': 5}},
    4: {2: {'weight': 4}, 3: {'weight': 5}}
}

# Contoh penggunaan Adjacency Map untuk merepresentasikan graf
class Graph:
    def __init__(self, adj_map):
        self.adj_map = adj_map

    def display_adj_map(self):
        for vertex, edges in self.adj_map.items():
            print(f"Vertex {vertex}: {edges}")

graph = Graph(adj_map)
graph.display_adj_map()

4. Implementasi Graph

class Graph:
    def __init__(self, value):
        self.value = value
        self.destinations = []

    def add_destination(self, destination_node):
        self.destinations.append(destination_node)

    def find_all_paths(self, start, finish, path=None):
        if path is None:
            path = []

        path = path + [start]

        if start == finish:
            return [path]

        paths = []
        for node in start.destinations:
            if node not in path:
                found_paths = self.find_all_paths(node, finish, path)
                for found_path in found_paths:
                    paths.append(found_path)
        return paths

# Create a sample graph
graph_a = Graph("A")
graph_b = Graph("B")
graph_c = Graph("C")
graph_d = Graph("D")
graph_e = Graph("E")

graph_a.add_destination(graph_b)
graph_a.add_destination(graph_c)
graph_b.add_destination(graph_c)
graph_c.add_destination(graph_d)
graph_d.add_destination(graph_e)

print("\n# Find all paths from 'A' to 'E'")
all_paths_a_to_e = graph_a.find_all_paths(graph_a, graph_e)
if all_paths_a_to_e:
    for path in all_paths_a_to_e:
        print("\nPath Found:", " -> ".join(node.value for node in path))
else:
    print("No path from A to E")

print("\n# Find all paths from 'A' to 'D'")
all_paths_a_to_d = graph_a.find_all_paths(graph_a, graph_d)
if all_paths_a_to_d:
    for path in all_paths_a_to_d:
        print("Path Found:", " -> ".join(node.value for node in path))
else:
    print("No path from A to D")

print("\n# Find all paths from 'D' to 'A'")
all_paths_d_to_a = graph_d.find_all_paths(graph_d, graph_a)
if all_paths_d_to_a:
    for path in all_paths_d_to_a:
        print("Path Found:", " -> ".join(node.value for node in path))
else:
    print("No path from D to A")

Output Program:

# Find all paths from 'A' to 'E'
Path Found: A->B->C->D->E

# Find all paths from 'A' to 'D'
Path Found: A->C->D
Path Found: A->B->C->D

# Find all paths from 'D' to 'A'
No path from D to A

5. Traversal Graph

Pengertian Traversal Graph

Traversal Graph adalah proses mengunjungi setiap simpul (node/vertex) yang ada dalam graf dengan mengikuti hubungan atau sisi (edge) yang menghubungkannya dengan simpul lain. Tujuan dari traversal graf adalah untuk memeriksa, mencari, atau memanipulasi setiap simpul dalam graf secara sistematis, sehingga tidak ada simpul yang terlewatkan atau dikunjungi lebih dari sekali.

5.1 Implementasi Traversal Graph menggunakan BFS dan DFS

5.1.1 Breadth-First Search (BFS)

BFS adalah metode traversal yang mengunjungi semua simpul yang terhubung dengan simpul awal terlebih dahulu sebelum mengunjungi simpul-simpul yang lebih jauh.

Contoh kodingan Python untuk BFS:

from collections import deque

class Graph:
    def __init__(self, adj_list):
        self.adj_list = adj_list

    def bfs(self, start_vertex):
        visited = set()
        queue = deque([start_vertex])
        visited.add(start_vertex)

        while queue:
            vertex = queue.popleft()
            print(vertex, end=' ')

            for neighbor in self.adj_list[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)
                    visited.add(neighbor)

# Definisikan adjacency list untuk graf
adj_list = {
    1: [2, 3],
    2: [1, 3, 4],
    3: [1, 2, 4],
    4: [2, 3]
}

# Contoh penggunaan BFS pada graf dengan adjacency list
graph = Graph(adj_list)
print("BFS Traversal:")
graph.bfs(1)

Output dari contoh di atas akan mencetak hasil traversal BFS dari simpul '1' pada graf dengan adjacency list yang telah didefinisikan:

BFS Traversal:
1 2 3 4

5.1.2 Depth-First Search (DFS)

DFS adalah metode traversal yang mengunjungi simpul terdalam terlebih dahulu sebelum bergerak ke simpul yang lebih jauh.

Contoh kodingan Python untuk DFS:

class Graph:
    def __init__(self, adj_list):
        self.adj_list = adj_list

    def dfs(self, start_vertex, visited=None):
        if visited is None:
            visited = set()

        visited.add(start_vertex)
        print(start_vertex, end=' ')

        for neighbor in self.adj_list[start_vertex]:
            if neighbor not in visited:
                self.dfs(neighbor, visited)

# Definisikan adjacency list untuk graf dengan nilai yang lebih besar
adj_list = {
    1: [2, 3],
    2: [3, 4, 5],
    3: [4, 5, 6],
    4: [5, 6],
    5: [6]
}

# Contoh penggunaan DFS pada graf dengan adjacency list yang baru
graph = Graph(adj_list)
print("DFS Traversal:")
graph.dfs(1)

Output dari contoh di atas akan mencetak hasil traversal DFS dari simpul '1' pada graf dengan adjacency list yang nilai simpulnya lebih besar:

DFS Traversal:
1 2 3 4 5 6

Post Test Praktikum 13

Link Soal dan Post Test Praktikum 13: Klik di sini