Belajar Algoritm - BFS & DFS Lanjut: Aplikasi

#Pendahuluan

Setelah di episode 17 kita menutup FASE 4 dengan DP on trees & graphs, pada episode ini kita memulai FASE 5: GRAPH ALGORITHMS dengan aplikasi BFS & DFS yang lebih canggih. BFS dan DFS bukan sekadar traverse graph — mereka adalah fondasi untuk mendeteksi struktur internal graph: connected components, bipartiteness, strongly connected components, articulation points, dan bridges.

Memahami aplikasi lanjutan BFS & DFS penting karena banyak masalah graph bisa diselesaikan dengan hanya satu atau kedua traversal ini — tanpa perlu algoritma yang lebih kompleks seperti Dijkstra atau Floyd-Warshall.

#BFS Lanjut

#Bipartiteness Check

Graph bipartite: graph di mana setiap edge menghubungkan dua set vertex yang berbeda — bisa diwarnai dengan dua warna tanpa ada edge yang menghubungkan vertex warna yang sama.

BFS: warnai root dengan warna A, semua neighbor dengan warna B, neighbor dari neighbor dengan warna A, dan seterusnya. Jika ada edge yang menghubungkan vertex warna yang sama → tidak bipartite.

python

from collections import deque
 
def is_bipartite(graph, n):
    color = [-1] * n
    for start in range(n):
        if color[start] != -1:
            continue
        color[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if color[neighbor] == -1:
                    color[neighbor] = 1 - color[node]
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:
                    return False
    return True

#Connected Components

Connected components: jumlah komponen terpisah di graph tidak berarah. BFS/DFS dari setiap node yang belum dikunjungi = satu komponen.

python

def count_components(graph, n):
    visited = [False] * n
    count = 0
    for i in range(n):
        if not visited[i]:
            bfs(graph, i, visited)
            count += 1
    return count

#Shortest Path Unweighted

BFS secara natural menghitung shortest path di graph tidak berarah tanpa bobot — setiap level BFS = satu edge lebih jauh dari source.

python

def shortest_path_bfs(graph, source, n):
    dist = [-1] * n
    dist[source] = 0
    queue = deque([source])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if dist[neighbor] == -1:
                dist[neighbor] = dist[node] + 1
                queue.append(neighbor)
    return dist

Note

BFS shortest path hanya berlaku untuk graph tanpa bobot atau dengan bobot uniform. Untuk graph berbobot, gunakan Dijkstra (episode 19). Jika ada bobot negatif, gunakan Bellman-Ford.

#DFS Lanjut

#Tarjan's Algorithm: Strongly Connected Components

Strongly Connected Component (SCC): subset vertex di directed graph di mana setiap vertex bisa dicapai dari setiap vertex lain di subset yang sama.

Tarjan's algorithm menemukan semua SCC dalam O(V + E) menggunakan satu DFS:

python

def tarjan_scc(graph, n):
    index_counter = [0]
    index = [-1] * n
    lowlink = [-1] * n
    on_stack = [False] * n
    stack = []
    sccs = []
    
    def strongconnect(v):
        index[v] = index_counter[0]
        lowlink[v] = index_counter[0]
        index_counter[0] += 1
        stack.append(v)
        on_stack[v] = True
        
        for w in graph[v]:
            if index[w] == -1:
                strongconnect(w)
                lowlink[v] = min(lowlink[v], lowlink[w])
            elif on_stack[w]:
                lowlink[v] = min(lowlink[v], index[w])
        
        # v adalah root dari SCC
        if lowlink[v] == index[v]:
            scc = []
            while True:
                w = stack.pop()
                on_stack[w] = False
                scc.append(w)
                if w == v:
                    break
            sccs.append(scc)
    
    for v in range(n):
        if index[v] == -1:
            strongconnect(v)
    
    return sccs

#Articulation Points & Bridges

Articulation point: vertex yang jika dihapus, disconnect graph. Bridge: edge yang jika dihapus, disconnect graph.

DFS tree bisa mendeteksinya menggunakan low value: low[v] = indeks minimum yang bisa dicapai dari subtree v tanpa melewati edge ke parent.

python

def find_bridges(graph, n):
    index = [-1] * n
    low = [-1] * n
    timer = [0]
    bridges = []
    
    def dfs(v, parent):
        index[v] = low[v] = timer[0]
        timer[0] += 1
        for to in graph[v]:
            if to == parent:
                continue
            if index[to] == -1:
                dfs(to, v)
                low[v] = min(low[v], low[to])
                if low[to] > index[v]:
                    bridges.append((v, to))
            else:
                low[v] = min(low[v], index[to])
    
    for i in range(n):
        if index[i] == -1:
            dfs(i, -1)
    
    return bridges

Bridge condition: low[to] > index[v] — subtree to tidak bisa mencapai v atau ancestor v tanpa melewati edge (v, to).

#Aplikasi di Dunia Nyata

Teknik	Aplikasi
Bipartiteness	Task scheduling, graph coloring
Connected components	Network reachability, clustering
BFS shortest path	Solved puzzle, social network degrees
Tarjan's SCC	Compiler optimization, dependency analysis
Bridges	Network vulnerability analysis, critical links

Tip

Ketika menghadapi masalah graph, mulai dari pertanyaan: "Apakah saya perlu BFS atau DFS?" BFS untuk shortest path unweighted dan level-order. DFS untuk deteksi struktur (SCC, bridges, articulation points) dan eksplorasi depth-first.

#Penutup

Pada episode 18 ini, kalian telah memahami:

BFS: bipartiteness check (2-coloring), connected components, shortest path unweighted.
Tarjan's SCC: satu DFS untuk menemukan semua SCC dalam O(V+E).
Articulation points & bridges: low value dari DFS tree mendeteksi critical nodes/edges.
BFS dan DFS lebih dari sekadar traversal — mereka adalah fondasi analisis graph.

Di episode 19 selanjutnya kita akan membahas Shortest Path Lanjut: Dijkstra, Bellman-Ford & Floyd-Warshall — tiga algoritma shortest path berbobot dengan trade-off yang berbeda. Sampai jumpa di episode 19!