Belajar Data Structure - Topological Sort & Cycle Detection

#Pendahuluan

Setelah di episode 16 kita memahami BFS dan DFS — dua metode traversal fundamental — pada episode ini kita mempelajari topological sort dan cycle detection secara mendalam. Topological sort mengurutkan node dalam directed graph berdasarkan dependency: jika ada edge A → B, maka A harus muncul sebelum B. Ini hanya bisa dilakukan pada DAG (Directed Acyclic Graph) — graph tanpa cycle.

Topological sort bukan hanya konsep teori — ia adalah solusi untuk masalah nyata: build order dalam dependency management, course prerequisite di universitas, dan task scheduling dalam pipeline. Memahami kedua algoritma (DFS-based dan Kahn's) memberi kalian fleksibilitas untuk memilih yang paling cocok.

#Topological Sort

#DFS-Based (Post-Order Reverse)

Topological sort dengan DFS: jalankan DFS, catat urutan selesai (post-order), lalu reverse urutan tersebut.

Topological sort dengan DFS

def topological_sort_dfs(graph):
    visited = set()
    stack = []
 
    def dfs(node):
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(node)
 
    for node in graph:
        if node not in visited:
            dfs(node)
 
    return stack[::-1]

#Kahn's Algorithm (In-Degree)

Kahn's algorithm menggunakan in-degree (jumlah edge yang masuk ke node). Node dengan in-degree 0 bisa diproses duluan karena tidak ada dependency.

Kahn's algorithm

from collections import deque
 
def topological_sort_kahn(graph):
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] = in_degree.get(neighbor, 0) + 1
 
    queue = deque([node for node in graph if in_degree[node] == 0])
    result = []
 
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph.get(node, []):
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
 
    if len(result) != len(graph):
        return None  # Cycle terdeteksi
 
    return result

#Perbandingan

#Cycle Detection

#DFS Coloring

DFS coloring menggunakan tiga warna:

• White (0): belum dikunjungi
• Gray (1): sedang diproses (di recursion stack)
• Black (2): selesai diproses

Jika DFS menemui node gray, berarti ada back edge → cycle terdeteksi.

DFS coloring cycle detection

def has_cycle_dfs(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}
 
    def dfs(node):
        color[node] = GRAY
        for neighbor in graph.get(node, []):
            if color[neighbor] == GRAY:
                return True
            if color[neighbor] == WHITE and dfs(neighbor):
                return True
        color[node] = BLACK
        return False
 
    return any(dfs(n) for n in graph if color[n] == WHITE)

#Visited Array (Simpler)

Untuk undirected graph, cycle detection lebih sederhana: jika DFS menemui neighbor yang sudah dikunjungi dan bukan parent, ada cycle.

Cycle detection undirected graph

def has_cycle_undirected(graph):
    visited = set()
 
    def dfs(node, parent):
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True
        return False
 
    return any(dfs(n, None) for n in graph if n not in visited)

#Aplikasi

• Build order: menentukan urutan kompilasi package berdasarkan dependency
• Course prerequisite: menentukan urutan mengambil mata kuliah
• Task scheduler: menentukan urutan eksekusi task berdasarkan dependency
• Dependency resolution: npm install, pip install

#Praktik: Course Schedule

Course schedule dengan topological sort

def can_finish(num_courses, prerequisites):
    graph = {i: [] for i in range(num_courses)}
    for course, prereq in prerequisites:
        graph[prereq].append(course)
 
    return topological_sort_kahn(graph) is not None
 
print(can_finish(2, [[1, 0]]))
print(can_finish(2, [[1, 0], [0, 1]]))

#Penutup

Inti yang harus dibawa pulang:

• Topological sort: urutkan node berdasarkan dependency; hanya untuk DAG.
• DFS-based: post-order reverse. Kahn's: in-degree processing.
• Kahn's otomatis mendeteksi cycle (hasil != len(graph)).
• DFS coloring: white → gray → black; gray kembali = cycle.
• Aplikasi: build order, course prerequisite, task scheduling.

Di episode 18 selanjutnya kita akan membahas shortest path (Dijkstra & Bellman-Ford) — dua algoritma fundamental untuk menemukan jalur terpendek. Dijkstra menggunakan greedy + priority queue untuk graph tanpa edge negatif, Bellman-Ford menggunakan dynamic programming untuk graph dengan edge negatif. Pastikan kalian sudah paham topological sort karena Dijkstra menggunakan priority queue yang kita bahas di episode 8!