0Pricing
DSA Interview Prep · Pelajaran

Algoritma Kahn: Pengurutan Topologis BFS

Hitung derajat masuk semua simpul, masukkan simpul berderajat masuk nol ke antrean, lalu proses antrean untuk menghasilkan urutan topologis sekaligus mendeteksi siklus

Algoritma Kahn: Pengurutan Topologis BFS adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.

Apa Itu Pengurutan Topologis?

Pengurutan topologis dari Graf Berarah Tanpa Siklus (DAG) adalah pengurutan simpul sedemikian rupa sehingga setiap sisi berarah u → v berarti u muncul sebelum v dalam pengurutan tersebut. Ini merepresentasikan urutan eksekusi yang valid untuk tugas-tugas dengan dependensi—seperti sistem pembangunan, penjadwalan mata kuliah, atau pengelolaan paket. Hanya DAG yang memiliki pengurutan topologis yang valid; siklus membuatnya mustahil.

Algoritme Kahn: Gagasan Inti

Algoritme Kahn adalah pendekatan berbasis BFS untuk pengurutan topologis. Gagasan utamanya: simpul dengan derajat masuk 0 (tanpa prasyarat) dapat ditempatkan pertama dalam pengurutan. Setelah menempatkannya, hapus simpul tersebut dan kurangi derajat masuk tetangganya. Simpul baru dengan derajat masuk nol menjadi tersedia. Ulangi hingga semua simpul ditempatkan atau siklus terdeteksi (masih ada simpul dengan derajat masuk bukan nol).

Penghitungan Derajat Masuk

Pertama, buat daftar ketetanggaan dan hitung derajat masuk (jumlah sisi yang masuk) untuk setiap simpul. Simpul dengan derajat masuk 0 adalah titik awal—simpul-simpul tersebut tidak memiliki dependensi. Untuk graf dengan sisi [(0,1),(0,2),(1,3),(2,3)], derajat masuknya adalah: 0→0, 1→1, 2→1, 3→2. Hanya simpul 0 yang memulai dengan derajat masuk 0.

from collections import deque, defaultdict

def compute_in_degree(n, edges):
    in_degree = [0] * n
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    return graph, in_degree

graph, ind = compute_in_degree(4, [(0,1),(0,2),(1,3),(2,3)])
print('In-degrees:', ind)  # [0, 1, 1, 2]

Implementasi Algoritme Kahn

Masukkan semua simpul dengan derajat masuk nol ke dalam antrean. Proses setiap simpul: tambahkan simpul tersebut ke hasil, lalu untuk setiap tetangga kurangi derajat masuknya dan masukkan ke antrean jika nilainya mencapai 0. Jika daftar hasil berisi lebih sedikit simpul daripada graf, berarti terdapat siklus—beberapa simpul tidak pernah dapat dikeluarkan dari antrean.

from collections import deque, defaultdict

def kahn_topological_sort(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    queue = deque(i for i in range(n) if in_degree[i] == 0)
    order = []
    
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    if len(order) == n:
        return order   # valid topological sort
    return []          # cycle detected

print(kahn_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))

Deteksi Siklus melalui Kahn

Algoritme Kahn menyediakan deteksi siklus tanpa biaya tambahan: jika len(order) < n, beberapa simpul tidak pernah ditambahkan ke antrean karena derajat masuknya tidak pernah mencapai 0—simpul-simpul tersebut merupakan bagian dari siklus. Cara ini lebih sederhana daripada mempertahankan larik kunjungan berkode warna. Kembalikan daftar kosong untuk menandakan adanya siklus.

# Cyclic graph: 0->1->2->0
edges_cycle = [(0,1),(1,2),(2,0)]
result = kahn_topological_sort(3, edges_cycle)
print(result)  # [] (cycle detected)

# Acyclic graph
edges_dag = [(0,1),(1,2)]
result = kahn_topological_sort(3, edges_dag)
print(result)  # [0, 1, 2]

Kompleksitas Waktu dan Ruang

Algoritme Kahn memproses setiap simpul sekali (dikeluarkan dari antrean sekali) dan setiap sisi sekali (derajat masuk dikurangi sekali). Kompleksitas waktu: O(V + E). Ruang: O(V + E) untuk daftar ketetanggaan dan larik derajat masuk, ditambah O(V) untuk antrean. Ini optimal—setidaknya Anda harus membaca semua simpul dan sisi untuk menghasilkan pengurutan yang valid.

Urutan Topologis Terkecil secara Leksikografis

Algoritme Kahn dengan heap minimum, bukan antrean, menghasilkan urutan topologis terkecil secara leksikografis. Ganti deque dengan heapq: masukkan (node) dan selalu proses simpul terkecil yang tersedia terlebih dahulu. Ini menjamin pengurutan valid yang paling kecil secara leksikografis di antara semua pengurutan topologis yang mungkin.

import heapq
from collections import defaultdict

def kahn_lex_order(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    heap = [i for i in range(n) if in_degree[i] == 0]
    heapq.heapify(heap)
    order = []
    
    while heap:
        node = heapq.heappop(heap)
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                heapq.heappush(heap, nxt)
    
    return order if len(order) == n else []

print(kahn_lex_order(6, [(5,2),(5,0),(4,0),(4,1),(2,3),(3,1)]))

Penerapan: Penjadwalan Mata Kuliah I

Penjadwalan Mata Kuliah (LeetCode 207): diberikan n mata kuliah dan prasyarat, apakah Anda dapat menyelesaikan semua mata kuliah? Modelkan prasyarat sebagai sisi berarah dan periksa apakah terdapat pengurutan topologis yang valid (yaitu, tidak ada siklus). Kembalikan Benar jika Algoritme Kahn menghasilkan pengurutan dengan panjang n, dan Salah jika siklus terdeteksi.

from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:   # b must be taken before a
        graph[b].append(a)
        in_degree[a] += 1
    
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    count = 0
    while queue:
        node = queue.popleft()
        count += 1
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    return count == numCourses

print(canFinish(2, [[1,0]]))       # True
print(canFinish(2, [[1,0],[0,1]])) # False (cycle)

Penerapan: Penjadwalan Mata Kuliah II

Penjadwalan Mata Kuliah II (LeetCode 210): kembalikan urutan sebenarnya untuk mengambil mata kuliah. Caranya sama seperti di atas, tetapi kembalikan daftar order, bukan nilai logika. Jika terdapat siklus, kembalikan daftar kosong. Keluaran Kahn ini dapat langsung digunakan sebagai jawaban.

from collections import deque, defaultdict

def findOrder(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    return order if len(order) == numCourses else []

print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))

Penjadwalan Tugas Paralel

Penggunaan yang lebih lanjut: diberikan tugas-tugas dengan dependensi, temukan jumlah minimum 'putaran' yang diperlukan jika tugas tanpa dependensi dapat berjalan secara paralel. Proses Kahn tingkat demi tingkat (mirip dengan penelusuran BFS berdasarkan tingkat): masukkan semua simpul dengan derajat masuk nol ke antrean, proses seluruh antrean saat ini sebagai satu putaran, lalu masukkan simpul yang baru terbebas sebagai putaran berikutnya. Hitung jumlah putaran.

from collections import deque, defaultdict

def min_rounds(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    queue = deque(i for i in range(n) if in_degree[i] == 0)
    rounds = 0
    while queue:
        rounds += 1
        for _ in range(len(queue)):  # process current level
            node = queue.popleft()
            for nxt in graph[node]:
                in_degree[nxt] -= 1
                if in_degree[nxt] == 0:
                    queue.append(nxt)
    return rounds

print(min_rounds(4, [(0,2),(1,2),(2,3)]))  # 3

Pengurutan Topologis dan DP pada DAG

Pengurutan topologis memungkinkan pemrograman dinamis pada DAG: proses simpul dalam urutan topologis, dan saat menghitung dp[v], semua dp[u] pendahulunya sudah final. Ini menggabungkan pengurutan topologis dengan DP untuk masalah seperti jalur terpanjang dalam DAG, biaya minimum untuk mencapai semua simpul, atau keuntungan maksimum dari rantai dependensi. Pengurutan tersebut menjamin bahwa nilai DP setiap simpul dihitung tepat satu kali setelah semua dependensinya.

from collections import deque, defaultdict

def longest_path_dag(V, edges):
    graph = defaultdict(list)
    in_degree = [0] * V
    for u, v, w in edges:
        graph[u].append((v, w))
        in_degree[v] += 1
    queue = deque(i for i in range(V) if in_degree[i] == 0)
    dp = [0] * V
    while queue:
        u = queue.popleft()
        for v, w in graph[u]:
            dp[v] = max(dp[v], dp[u] + w)
            in_degree[v] -= 1
            if in_degree[v] == 0: queue.append(v)
    return max(dp)

print(longest_path_dag(4, [(0,1,3),(0,2,2),(1,3,4),(2,3,1)]))  # 7

Uji Cepat

Uji pemahaman Anda tentang konsep Struktur Data & Algoritme — Persiapan Wawancara Pemrograman dari pelajaran ini.

Rangkuman Pelajaran

Dalam pelajaran ini Anda mempelajari: Algoritme Kahn menghitung pengurutan topologis dengan menghapus secara iteratif simpul dengan derajat masuk nol menggunakan BFS, deteksi siklus tidak memerlukan biaya tambahan—jika len(order) < n, terdapat siklus, dan mengganti antrean dengan heap minimum menghasilkan urutan topologis terkecil secara leksikografis. Selanjutnya, kita mengeksplorasi pengurutan topologis pascakunjungan berbasis DFS sebagai alternatif bagi Algoritme Kahn.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Algoritma Kahn: Pengurutan Topologis BFS” gratis?

Ya — teks lengkap “Algoritma Kahn: Pengurutan Topologis BFS” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Algoritma Kahn: Pengurutan Topologis BFS”?

Hitung derajat masuk semua simpul, masukkan simpul berderajat masuk nol ke antrean, lalu proses antrean untuk menghasilkan urutan topologis sekaligus mendeteksi siklus Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?

Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.

Berapa lama pelajaran “Algoritma Kahn: Pengurutan Topologis BFS” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?

Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. Algoritma Kahn: Pengurutan Topologis BFS
  2. Pengurutan Topologis DFS Pascaurutan
  3. Course Schedule I dan II
  4. Komponen Terhubung Kuat dengan Kosaraju
← Kembali ke DSA Interview Prep