Mendeteksi Siklus dalam Graf Berarah
Mewarnai node untuk menemukan sisi balik
Mendeteksi Siklus dalam Graf Berarah adalah pelajaran Coding 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 Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Mengapa Siklus Penting
Siklus berarah berarti dependensi kembali mengarah ke dirinya sendiri. Menemukannya memberi tahu Anda bahwa tidak mungkin ada urutan topologis atau jadwal yang sah.
Graf Tak Berarah Berbeda
Deteksi siklus di sini berkaitan dengan arah. Mengikuti sisi ke arah yang salah tidak dihitung, jadi trik untuk graf tak berarah tidak berlaku.
Gagasan Tiga Warna
Beri setiap simpul salah satu dari tiga warna: putih berarti belum dikunjungi, abu-abu berarti sedang diproses, dan hitam berarti sudah selesai sepenuhnya.
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * nAbu-Abu Berarti Ada di Tumpukan
Simpul abu-abu berada pada jalur DFS yang sedang Anda telusuri. Anda telah memasukinya, tetapi belum selesai menjelajahi semua turunannya.
Masuki Sebuah Simpul
Ketika DFS mencapai sebuah simpul, warnai simpul itu menjadi abu-abu sebelum menjelajah. Ini menandainya sebagai bagian dari jalur aktif.
def dfs(u):
color[u] = GRAYSinyal Sisi Mundur
Jika Anda mencapai tetangga yang sudah abu-abu, berarti Anda menemukan sisi mundur menuju jalur saat ini. Itulah sebuah siklus.
for v in adj[u]:
if color[v] == GRAY:
return True # cycleLakukan Rekursi ke Simpul Putih
Tetangga putih masih baru, jadi lakukan rekursi ke dalamnya. Teruskan nilai True segera setelah pemanggilan yang lebih dalam melaporkan adanya siklus.
elif color[v] == WHITE and dfs(v):
return TrueHitam Berarti Aman
Tetangga hitam sudah selesai dijelajahi dan dipastikan bebas siklus, jadi Anda dapat mengabaikannya. Mengunjunginya kembali hanya membuang waktu.
Selesaikan Sebuah Simpul
Setelah semua tetangga ditangani, warnai simpul tersebut menjadi hitam. Simpul itu keluar dari jalur aktif dan ditandai sebagai selesai.
color[u] = BLACK
return FalseCakup Semua Komponen
Graf dapat bersifat tidak terhubung, jadi mulai DFS dari setiap simpul yang masih putih untuk memastikan seluruh graf diperiksa.
if any(color[u]==WHITE and dfs(u) for u in range(n)):
print('cycle')Perhatikan Batas Rekursi
Graf yang dalam dapat menyebabkan tumpukan rekursi Python meluap. Naikkan batas tersebut atau tulis ulang DFS menggunakan tumpukan eksplisit.
import sys
sys.setrecursionlimit(300000)Uji Cepat
Saat menjalankan DFS, Anda mencapai tetangga yang saat ini berwarna abu-abu. Apa yang baru saja Anda temukan?
Rangkuman: Deteksi Siklus
Warnai simpul menjadi putih, abu-abu, lalu hitam. Tetangga abu-abu selama DFS adalah sisi mundur, yang membuktikan adanya siklus berarah. 🔁
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Mendeteksi Siklus dalam Graf Berarah” gratis?
Ya — teks lengkap “Mendeteksi Siklus dalam Graf Berarah” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Mendeteksi Siklus dalam Graf Berarah”?
Mewarnai node untuk menemukan sisi balik Kamu berlatih Coding 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 Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding 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 “Mendeteksi Siklus dalam Graf Berarah” 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 Coding Interview Prep ini?
Ya. Setiap pelajaran Coding 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
- Pengurutan Topologis dengan Algoritma Kahn
- Mendeteksi Siklus dalam Graf Berarah
- Komponen Terhubung Kuat
- Jembatan & Titik Artikulasi