Pengurutan Topologis DFS Pascaurutan
Jalankan DFS dan dorong setiap simpul ke tumpukan setelah semua tetangganya selesai dijelajahi, lalu keluarkan tumpukan untuk memperoleh urutan topologis yang valid
Pengurutan Topologis DFS Pascaurutan adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 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.
Gagasan Pengurutan Topologis Berbasis DFS
Algoritme pengurutan topologis klasik kedua menggunakan DFS dengan pemrosesan pascapemesanan. Setelah menjelajahi sepenuhnya semua tetangga suatu simpul (beserta turunannya), dorong simpul tersebut ke dalam tumpukan. Setelah semua simpul diproses, keluarkan simpul dari tumpukan untuk membaca urutan topologis. Simpul yang didorong ke tumpukan setelah semua dependensinya berarti simpul tersebut muncul lebih dahulu dalam urutan—jadi urutan pascapemesanan yang dibalik adalah pengurutan topologis.
Intuisi di Balik Pascapemesanan
Perhatikan graf dependensi dengan kondisi bahwa mata kuliah A memerlukan mata kuliah B. Saat DFS mengunjungi A, DFS terlebih dahulu melakukan rekursi ke B. B tidak memiliki prasyarat, sehingga B selesai lebih dahulu dan didorong lebih dahulu. Kemudian A selesai dan didorong ke tumpukan. Mengeluarkan simpul dari tumpukan menghasilkan A sebelum B pada keluaran—tetapi kita membaliknya di akhir, sehingga B berada sebelum A: ambil B terlebih dahulu, kemudian A. Pascapemesanan mendorong dependensi sebelum simpul yang bergantung padanya, sehingga tumpukan yang dibalik merupakan urutan topologis yang valid.
DFS Tiga Warna untuk Deteksi Siklus
Gunakan tiga status untuk simpul yang dikunjungi: WHITE (0) = belum dikunjungi, GREY (1) = sedang diproses (berada dalam tumpukan pemanggilan DFS), BLACK (2) = telah diproses sepenuhnya. Sisi balik—sisi menuju simpul GREY—menunjukkan adanya siklus. Sisi menuju simpul BLACK aman (simpul tersebut sudah dijelajahi sepenuhnya). Skema tiga warna ini mendeteksi semua siklus dalam graf berarah dengan benar.
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n # n = number of nodes
# During DFS:
# color[node] = GREY (entering node)
# recurse into neighbours
# if neighbour is GREY: cycle found!
# color[node] = BLACK (leaving node, push to stack)Implementasi Pengurutan Topologis DFS Lengkap
Gunakan DFS rekursif yang memberi warna pada simpul, mendorong simpul ke tumpukan dalam urutan pascapemesanan, dan mengembalikan False saat mendeteksi siklus. Setelah semua simpul dikunjungi, tumpukan yang dibalik menghasilkan urutan topologis.
from collections import defaultdict
def dfs_topological_sort(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
stack = []
def dfs(node):
color[node] = GREY
for nxt in graph[node]:
if color[nxt] == GREY:
return False # cycle
if color[nxt] == WHITE:
if not dfs(nxt):
return False
color[node] = BLACK
stack.append(node)
return True
for i in range(n):
if color[i] == WHITE:
if not dfs(i):
return [] # cycle
return stack[::-1]
print(dfs_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))DFS Iteratif untuk Menghindari Luapan Tumpukan
Batas rekursi Python (nilai bawaan 1000) perlu diperhatikan untuk graf berukuran besar. DFS iteratif yang menggunakan tumpukan eksplisit dapat menghindari hal ini. Caranya: dorong (node, False) terlebih dahulu; saat dikeluarkan dengan False, dorong (node, True) (yang berarti 'Saya akan kembali ke sini setelah menjelajahinya') dan dorong semua tetangga yang belum dikunjungi dengan False. Saat dikeluarkan dengan True, beri warna BLACK pada simpul tersebut dan dorong ke tumpukan hasil.
from collections import defaultdict
def dfs_topo_iterative(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
result = []
for start in range(n):
if color[start] != WHITE:
continue
stack = [(start, False)]
while stack:
node, returning = stack.pop()
if returning:
color[node] = BLACK
result.append(node)
elif color[node] == WHITE:
color[node] = GREY
stack.append((node, True)) # will return here
for nxt in graph[node]:
if color[nxt] == WHITE:
stack.append((nxt, False))
return result[::-1]Perbandingan DFS dan Algoritme Kahn
Keduanya berjalan dalam O(V + E). Perbedaan utama: algoritme Kahn (BFS) secara alami menghasilkan simpul dalam urutan dependensi paling awal dan memiliki deteksi siklus yang lebih sederhana (pemeriksaan panjang). DFS pascapemesanan bekerja secara rekursif dan mendeteksi sisi balik secara eksplisit. Algoritme Kahn lebih disukai jika Anda menginginkan hasil dalam urutan maju tanpa membaliknya. DFS lebih disukai jika Anda memerlukan urutan pascapemesanan lengkap untuk keperluan lain (seperti deteksi SCC). Keduanya dapat diterima dalam wawancara.
Pascapemesanan pada Pohon dan DAG
Pada pohon, pascapemesanan mengunjungi subpohon kiri → subpohon kanan → akar. Pada DAG, DFS pascapemesanan mengunjungi semua dependensi suatu simpul sebelum memproses simpul itu sendiri—gagasan yang digeneralisasi untuk banyak pendahulu dan struktur graf arbitrer. Akar pohon DFS (simpul awal) didorong terakhir di antara turunannya, sehingga muncul pertama dalam tumpukan yang dibalik—posisi topologis yang benar bagi simpul tanpa pendahulu.
Kamus Alien (LeetCode 269)
Kamus Alien: diberikan daftar kata yang telah diurutkan dalam bahasa alien, tentukan urutan karakternya. Bandingkan kata-kata yang bersebelahan karakter demi karakter untuk menemukan perbedaan pertama—hal ini menghasilkan sisi c1 → c2 yang berarti c1 muncul sebelum c2. Kumpulkan semua sisi tersebut dan jalankan pengurutan topologis untuk menghasilkan urutan karakter alien. Jika terdapat siklus, urutan tersebut tidak valid.
from collections import defaultdict
def alienOrder(words):
graph = defaultdict(set)
all_chars = set(c for w in words for c in w)
for i in range(len(words)-1):
w1, w2 = words[i], words[i+1]
if len(w1) > len(w2) and w1.startswith(w2):
return '' # invalid (prefix comes after)
for c1, c2 in zip(w1, w2):
if c1 != c2:
graph[c1].add(c2)
break
# DFS topological sort on character graph
WHITE, GREY, BLACK = 0, 1, 2
color = {c: WHITE for c in all_chars}
result = []
def dfs(c):
color[c] = GREY
for nxt in graph[c]:
if color[nxt] == GREY: return False
if color[nxt] == WHITE and not dfs(nxt): return False
color[c] = BLACK
result.append(c)
return True
for c in all_chars:
if color[c] == WHITE:
if not dfs(c): return ''
return ''.join(result[::-1])
print(alienOrder(['wrt','wrf','er','ett','rftt'])) # 'wertf'Pengurutan Topologis dengan Batasan
Beberapa masalah meminta pengurutan topologis yang memenuhi batasan tambahan, seperti mempertahankan urutan relatif elemen dari daftar asli. Gabungkan algoritme Kahn dengan antrean prioritas khusus atau pengurutan awal: pertahankan urutan relatif asli elemen dengan menggunakan pengurutan stabil pada isi antrean di setiap langkah. Varian dengan batasan ini menguji pemahaman yang lebih mendalam tentang fleksibilitas algoritme.
Mengenali Masalah Pengurutan Topologis
Frasa petunjuk dalam masalah wawancara yang menunjukkan pengurutan topologis antara lain: 'diberikan dependensi', 'prasyarat', 'pengurutan tugas', 'urutan pembangunan', 'apakah semua tugas dapat diselesaikan?', 'temukan urutan yang valid'. Jika masalah melibatkan pengurutan berbagai elemen yang sebagian harus muncul sebelum elemen lainnya, bangun graf berarah dan terapkan pengurutan topologis Kahn atau DFS. Deteksi siklus sering kali menjadi persyaratan tambahan dalam masalah yang sama.
Membandingkan Keluaran DFS dan Algoritme Kahn
DFS dan algoritme Kahn dapat menghasilkan urutan topologis valid yang berbeda untuk graf yang sama. Keduanya benar—sebuah DAG dapat memiliki beberapa urutan topologis yang valid. Untuk memverifikasi kebenarannya, periksa bahwa untuk setiap sisi u → v dalam graf, u muncul sebelum v dalam urutan keluaran. Untuk masalah wawancara yang memerlukan urutan tertentu (misalnya, urutan terkecil secara leksikografis), gunakan algoritme Kahn dengan tumpukan-min—pascapemesanan DFS tidak secara alami menghasilkan urutan terkecil secara leksikografis.
Pemeriksaan Singkat
Ujilah pemahaman Anda tentang konsep Struktur Data & Algoritme — Persiapan Wawancara Pemrograman dari pelajaran ini.
Rangkuman Pelajaran
Dalam pelajaran ini Anda telah mempelajari: pengurutan topologis pascapemesanan DFS mendorong simpul setelah semua dependensinya dijelajahi, penandaan tiga warna (WHITE/GREY/BLACK) mendeteksi siklus melalui sisi balik menuju simpul GREY, dan pembalikan tumpukan pascapemesanan menghasilkan urutan topologis yang valid. Selanjutnya, kita akan menerapkan pengurutan topologis secara langsung pada masalah Jadwal Mata Kuliah I dan II.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Pengurutan Topologis DFS Pascaurutan” gratis?
Ya — teks lengkap “Pengurutan Topologis DFS Pascaurutan” 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 “Pengurutan Topologis DFS Pascaurutan”?
Jalankan DFS dan dorong setiap simpul ke tumpukan setelah semua tetangganya selesai dijelajahi, lalu keluarkan tumpukan untuk memperoleh urutan topologis yang valid 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 2 dari 4.
Berapa lama pelajaran “Pengurutan Topologis DFS Pascaurutan” 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
- Algoritma Kahn: Pengurutan Topologis BFS
- Pengurutan Topologis DFS Pascaurutan
- Course Schedule I dan II
- Komponen Terhubung Kuat dengan Kosaraju