DFS & BFS

1. Introduction

1. Algoritma pengurutan topologikal (Versi DFS dan BFS/algoritma Kahn),
   
2. Algoritma pengecekan bipartit (Versi DFS dan BFS),
3. Algoritma pencari simpul artikulasi & jembatan,
4. Algoritma-algoritma pencari Strongly-Connected Component (SCC)
   (versi Kosaraju dan Tarjan), dan
5. Algoritma pengecek 2-SAT.

2. Visualisasi

Ketika algoritma penjelajahan graf yang terpilih sedang berjalan, animasinya akan ditampilkan di sini.

Seluruh algoritma-algoritma penjelajahan graf dapat dijalankan pada graf terarah (ini merupakan pengaturan default, di mana setiap sisi memiliki anak panah untuk menunjukkan arahnya), tetapi algoritma Pengecekan Graf Bipartit dan algoritma penemuan Simpul Potong & Jembatan memerlukan graf tak terarah (konversi dilakukan secara otomatis oleh visualisasi ini).

3. Spesifikasikan Graf Masukan

There are two different sources for specifying an input graph:

1. Edit Graph: You can draw a new graph or edit an example unweighted directed graph as the input graph (to draw bidirectional edge (u, v), you can draw two directed edges u → v and v → u).
2. Example Graphs: You can select from the list of our selected example graphs to get you started.

4. Rekap

Jika anda tiba di Kuliah Maya ini tanpa pertama mengjelajahi/menguasai konsep Tumpukan Biner dan terutama Pohon Biner Terurut, kami menyarankan agar anda mengeksplorasi mereka dulu, karena menjelajahi sebuah struktur Pohon (Biner) jauh lebih mudah daripada menjelajahi sebuah graf umum.

Quiz: Mini pre-requisite check. What are the Pre-/In-/Post-order traversal of the binary tree shown (root = vertex 0), left and right child are as drawn?

4-1. Penjelajahan Pohon Biner - Sumber = Akar

Kita biasanya mulai dari simpul yang paling penting dari sebuah pohon (biner): Simpul akar.

Jika pohon yang diberikan tidak 'berakar' (lihat gambar contoh), kita bisa ambil satu simpul apa saja (contohnya, simpul 0 di gambar contoh) dan menunjuknya sebagai akar. Jika kita membayangkan semua sisi-sisi adalah tali-tali dengan panjang yang sama, maka setelah "secara virtual mengangkat akar yang ditunjuk keatas" dan membiarkan gravitasi menarik sisanya kebawah, kita akan mendapat pohon berakar yang terarah (kebawah) — lihat slide berikutnya.

Catatan: Secara teknis, transformasi ini dilakukan dengan menjalankan DFS(0) yang akan kita eksplorasi segera.

4-2. Penjelajahan Pohon Biner - Pre-In-Post-order

Dalam sebuah pohon biner, kita hanya mempunyai paling banyak dua pilihan tetanga: Dari simpul sekarang, kita bisa pergi ke sub-pohon kiri dulu atau pergi ke sub-pohon kanan dulu. Kita juga mempunyai opsi untuk mengunjungi simpul sekarang sebelum atau sesudah mengunjungi satu (atau kedua) sub-pohon.

Ini menghasilkan beberapa penjelajahan klasik: pre-order (kunjungi simpul sekarang, kunjungi sub-pohon kirinya, kunjungi sub-pohon kanannya), in-order (kiri, sekarang, kanan), dan post-order (kiri, kanan, sekarang).

Diskusi: Apakah anda menyadari bahwa ada tiga lagi kombinasi penjelajahan pohon biner yang memungkinkan? Apa sajakah mereka?

4-3. Jawabannya

4-4. Penjelajahan Pohon Biner - Tidak-bersiklus

Didalam pohon biner, atau didalam struktur pohon pada umumnya, tidak ada siklus (tidak-trivial) yang berurusan dengan 3 atau lebih simpul yang berbeda yang perlu kita khawatirkan (kita tidak menganggap siklus trivial yang berurusan dengan sisi-sisi dua-arah yang bisa diurus dengan mudah — lihat tiga slide selanjutnya).

4-5. Isu-Isu di Graf Umum

Dalam graf umum, kita tidak memiliki gagasan tentang simpul akar. Melainkan, kita perlu memilih satu simpul yang dikhususkan untuk menjadi titik mula dari penjelajahan, yaitu simpul sumber s.

Kita juga mempunyai 0, 1, ..., k tetangga dari sebuah simpul daripada hanya ≤ 2.

Kita mungin (atau sebenarnya sangat mungkin) memiliki siklus(-siklus) dalam graf umum kita daripada pohon yang tidak-bersiklus,
baik itu adalah siklus yang trivial seperti u → v → u atau yang tidak-trivial seperti a → b → c → a.

Tetapi jangan takut, penjelajahan graf adalah masalah mudah dengan dua algoritma klasik: DFS dan BFS.

5. DFS

Salah satu algoritma penjelajahan graf yang paling dasar adalah O(V+E) Depth-First Search (DFS).

DFS membutuhkan satu parameter masukan: Vertex sumber s.

DFS adalah salah satu algoritma graf yang paling mendasar, jadi tolong gunakan waktu untuk mengerti semua langkah-langkah kunci dari algoritma ini.

5-1. Analogi

Analogi terdekat dengan perilaku DFS adalah untuk mengimaginasikan sebuah maze dengan hanya satu pintu masuk dan satu pitu keluar. Anda berada pada pintu masuk dan mau mengeksplorasi maze untuk mencapai pintu keluar. Tentu saja anda tidak bisa membelah diri anda menjadi lebih dari satu.

Tanya pertanyaan-pertanyaan reflektif ini sebelum melanjutkan: Apa yang akan anda lakukan jika ada opsi-opsi bercabang didepan anda? Bagaiamana untuk menghindari berjalan dalam siklus? Bagaimana cara menandai jalur anda sendiri? Petunjuk: Anda membutuhkan sebuah kapur, batu-batu (atau penanda lainnya) dan sebuah tali (yang panjang).

5-2. Mencoba Semua Opsi-Opsi

Seperti namanya, DFS dimulai dari sebuah simpul sumber s yang dibedakan dan menggunakan rekursi (sebuah tumpukan implisit) untuk mengatur urutan pengunjungan sedalam mungkin sebelum mundur (backtracking).

Jika DFS ada di simpul u dan DFS memiliki X tetangga, DFS akan memilih tetangga pertama V₁ (biasanya simpul dengan nomor simpul terkecil), secara rekursif mengeksplorasi semua simpul-simpul yang terjangkau dari simpul V₁, dan pada akhirnya mundur (backtrack) ke simpul u. DFS akan lalu melakukan hal yang sama ke tetanga-tetangga lainnya sampai DFS selesai menjelajahi tetangga terakhir V_X dan semua simpul-simpul yang terjangkau dari sana.

Penjelasan yang penuh teks ini akan lebih jelas dengan animasi DFS nantinya.

5-3. Menghindari Siklus

Jika grafnya bersiklus, strategi 'coba-semua' sebelumnya bisa membuat DFS berjalan dalam siklus.

Jadi bentuk dasar dari DFS menggunakan sebuah larik status[u] dengan ukuran V simpul untuk menentukan diantara dua kondisi biner: Apakah simpul u telah dikunjungi atau belum dikunjungi. Hanya jika simpul u masih belum dikunjungi, maka DFS bisa mengunjungi simpul u.

Ketika DFS kehabisan opsi, maka DFS mundur kembali (backtrack) ke simpul sebelumnya (p[u], lihat slide berikut) saat rekrusinya kembali (unwinds).

5-4. Mengingat Jalur

DFS uses another array p[u] of size V vertices to remember the parent/predecessor/previous of each vertex u along the DFS traversal path.

The predecessor of the source vertex, i.e., p[s] is set to -1 to say that the source vertex has no predecessor (as the lowest vertex number is vertex 0).

The sequence of vertices from a vertex u that is reachable from the source vertex s back to s forms the DFS spanning tree. We color these tree edges with red color.

5-5. Contoh Hands-on

Untuk saat ini, abaikan status[u] = explored ekstra di pseudocode yang sedang ditampilkan dan keberadaan sisi-sisi biru dan abu-abu dalam visualisasi (akan dijelaskan segera).

Tanpa basa-basi lagi, mari eksekusi DFS(0) pada graf contoh default untuk Kuliah Maya ini (CP3 Figure 4.1). Recap DFS Example

Versi dasar dari DFS yang dipresentasikan sejauh ini sudah cukup untuk kebanyakan kasus-kasus sederhana.

5-6. Kompleksitas Waktu O(V+E)

Kompleksitas waktu dari DFS adalah O(V+E) karena:

1. Setiap simpul hanya dikunjungi sekali karena DFS hanya akan secara rekursif menjelajahi sebuah simpul u jika status[u] = unvisited — O(V)
2. Setiap kali sebuah simpul dikunjungi, semua k tetangganya akan dieksplorasi dan oleh karena itu setelah semua simpul-simpul dikunjungi, kita telah memeriksa semua E sisi-sisi — (O(E) karena jumlah total tetangga-tetangga dari setiap simpul sama dengan E).

5-7. Selalu O(V+E)?

Kompleksitas waktu O(V+E) dari DFS hanya bisa dicapai jika kita dapat mengunjungi semua k simpul-simpul tetangga dari sebuah simpul dalam waktu O(k).

Quiz: Which underlying graph data structure support that operation?

Diskusi: Kenapa?

5-8. Jawabannya

6. BFS

Algoritma penjelajahan graf dasar yang lain adalah O(V+E) Breadth-First Search (BFS).

Sama seperti DFS, BFS juga membutuhkan satu parameter masukan: Simpul sumber s.

DFS dan BFS memiliki kekuatan-kekuatan dan kelemahan-kelemahan masing-masing. Penting untuk mempelajari keduanya dan mengaplikasikan algoritma penjelajahan graf yang tepat pada situasi yang tepat.

6-1. Analogi

Bayangkan sebuah kumpulan air tenang dan anda melempar sebuah batu kedalamnya. Lokasi pertama dimana batu tersebut mengenai permukaan air adalah posisi dari simpul sumber dan efek riak sepanjang permukaan air seperti pola penjelajahan BFS.

6-2. Coba Semua, Hindari Siklus, Ingat Jalur

BFS sangat mirip dengan DFS yang sudah didiskusikan sebelumnya, tetapi dengan beberapa perbedaan.

BFS dimulai dari sebuah simpul sumber s tetapi BFS menggunakan sebuah antrean untuk mengatur urutan visitasi selebar mungkin sebelum masuk lebih dalam.

BFS juga menggunakan sebuah larik Boolean dengan ukuran V simpul-simpul untuk membedakan antara dua kondisi: simpul-simpul yang sudah dikunjungi dan yang belum dikunjungi (kita tidak akan menggunakan BFS untuk mendeteksi sisi(-sisi) belakang (back) seperti DFS).

Dalam visualisasi ini, kita juga menunjukkan bahwa dimulai dengan simpul sumber s yang sama dalam sebuah graf tidak-berbobot, pohon perentang (spanning tree) BFS dari grafnya sama dengan pohon perentang SSSPnya.

6-3. Contoh Hands-on

Tanpa basa-basi lagi, mari eksekusi BFS(5) pada graf contoh default untuk Kuliah Maya ini (CP3 Figure 4.3). Recap BFS Example.

Sadari bahwa penjelajahan Kesamping-dulu (Breadth-first) karena penggunaan struktur data FIFO: Antrean?

6-4. Kompleksitas Waktu O(V+E)

Kompleksitas waktu dari BFS adalah O(V+E) karena:

1. Setiap simpul hanya dikunjungi sekali karena setiap simpul cuma bisa masuk ke dalam antrean sekali — O(V)
2. Setiap kali sebuah simpul di dequeue dari antrean, semua k tetangganya akan dieksplorasi dan oleh karena itu setelah semua simpul-simpul dikunjungi, kita telah memeriksa semua E sisi-sisi — (O(E) karena jumlah total tetangga-tetangga dari setiap vertex sama dengan E).

Sama seperti DFS, kompleksitas waktu O(V+E) ini hanya mungkin jika kita menggunakan struktur data graf Daftar Adjacency (Adjacency List) — alasan yang sama dengan analisa DFS.

7. Aplikasi-Aplikasi Sederhana DFS/BFS

So far, we can use DFS/BFS to solve a few graph traversal problem variants:

1. Reachability test,
2. Actually printing the traversal path,
3. Identifying/Counting/Labeling Connected Components (CCs) of undirected graphs,
4. Detecting if a graph is cyclic,
5. Topological Sort (only on DAGs),

For most data structures and algorithms courses, the applications of DFS/BFS are up to these few basic ones only, although DFS/BFS can do much more...

7-1. Tes Reachability

If you are asked to test whether a vertex s and a (different) vertex t in a graph are reachable, i.e., connected directly (via a direct edge) or indirectly (via a simple, non cyclic, path), you can call the O(V+E) DFS(s) (or BFS(s)) and check if status[t] = visited.

Example 1: s = 0 and t = 4, run DFS(0) and notice that status[4] = visited.
Example 2: s = 0 and t = 7, run DFS(0) and notice that status[7] = unvisited.

7-2. Cetak Jalur Penjelajahan

Remember that we set p[v] = u every time we manage to extend DFS/BFS traversal from vertex u to vertex v — a tree edge in the DFS/BFS spanning tree. Thus, we can use following simple recursive function to print out the path stored in array p. Possible follow-up discussion: Can you write this in iterative form? (trivial)

method backtrack(u)
  if (u == -1) stop
  backtrack(p[u]);
  output vertex u

To print out the path from a source vertex s to a target vertex t in a graph, you can call O(V+E) DFS(s) (or BFS(s)) and then O(V) backtrack(t). Example: s = 0 and t = 4, you can call DFS(0) and then backtrack(4). Elaborate

7-3. Mengidentifikasikan sebuah Komponen Terhubung (Connected Component, CC)

We can enumerate all vertices that are reachable from a vertex s in an undirected graph (as the example graph shown above) by simply calling O(V+E) DFS(s) (or BFS(s)) and enumerate all vertex v that has status[v] = visited.

Example: s = 0, run DFS(0) and notice that status[{0,1,2,3,4}] = visited so they are all reachable vertices from vertex 0, i.e., they form one Connected Component (CC).

7-4. Menghitung Jumlah dari/Melabel CCs

We can use the following pseudo-code to count the number of CCs:

CC = 0
for all u in V, set status[u] = unvisited
for all u in V
  if (status[u] == unvisited)
    ++CC // we can use CC counter number as the CC label
    DFS(u) // or BFS(u), that will flag its members as visited
output CC // the answer is 3 for the example graph above, i.e.
// CC 0 = {0,1,2,3,4}, CC 1 = {5}, CC 2 = {6,7,8}

You can modify the DFS(u)/BFS(u) code a bit if you want to use it to label each CC with the identifier of that CC.

7-5. Tunggu, Apa Kompleksitas Waktunya?

Quiz: What is the time complexity of Counting the Number of CCs algorithm?

Diskusi: Kenapa?

7-6. Jawabannya

7-7. Pendeteksian Siklus - Bagian 1

Kita sebenarnya bisa meng-augmentasi DFS dasar lebih jauh untuk memberikan wawasan lebih tentang graf yang sedang dibahas.

Dalam visualisasi ini, kami menggunakan warna biru untuk menyorot sisi(-sisi) kembali (back edge) dari pohon perentang DFS. Keberadaan satu saja sisi kembali menunjukkan bahwa (komponen) graf yang sedang dieksplorasi adalah bersiklus ketika ketidakadaannya menunjukkan bahwa setidaknya komponen yang terhubung dengan vertex sumber dari graf yang sedang dijelajahi adalah tidak-bersiklus.

7-8. Pendeteksian Siklus - Bagian 2

Sisi belakang (Back edge) bisa dideteksi dengan memodifikasi larik status[u] untuk menyimpan tiga keadaan berbeda:

1. belum dikunjungi: sama seperti sebelumnya, DFS belum mencapai simpul u sebelumnya,
2. dieksplorasi: DFS telah mengunjungi simpul u, tetapi setidaknya satu tetangga dari simpul u belum dikunjungi (DFS akan pergi kedalam-dulu ke tetangga itu terlebih dahulu),
3. sudah dikunjungi: sekarang definisi yang lebih kuat: semua tetangga dari simpul u juga sudah dikunjungi dan DFS baru mau mundur (backtrack) dari simpul u ke simpul p[u].

Jika DFS sekarang berada di simpul x dan mengeksplorasi sisi x → y dan menjumpai status[y] = dieksplorasi, kita bisa mendeklarasikan x → y sebagai sisi belakang (back edge) (sebuah siklus ditemukan karena kita sebelumnya ada di simpul y (maka status[y] = dieksplorasi), pergi ke dalam ke tetangga dari y dan selanjutnya, tetapi sekarang kita ada di simpul x yang terjangkau dari y tetapi simpul x kembali menunjuk ke simpul y).

7-9. Contoh Hands-on (Dengan Detil)

The edges in the graph that are not tree edge(s) nor back edge(s) are colored grey. They are called forward or cross edge(s) and currently have limited use (not elaborated).

Now try DFS(0) on the example graph above with this new understanding, especially about the 3 possible status of a vertex (unvisited/normal black circle, explored/blue circle, visited/orange circle) and back edge. Edge 2 → 1 will be discovered as a back edge as it is part of cycle 1 → 3 → 2 → 1 (as vertex 2 is `explored' to vertex 1 which is currently `explored') (similarly with Edge 6 → 4 as part of cycle 4 → 5 → 7 → 6 → 4).

Note that if edges 2 → 1 and 6 → 4 are reversed to 1 → 2 and 4 → 6, then the graph is correctly classified as acyclic as edge 3 → 2 and 4 → 6 go from `explored' to `fully visited'. If we only use binary states: `unvisited' vs `visited', we cannot distinguish these two cases.

7-10. Pengurutan Topologis - Definisi

There is another DFS (and also BFS) application that can be treated as 'simple': Performing Topological Sort(ing) of a Directed Acyclic Graph (DAG) — see example above.

Topological sort of a DAG is a linear ordering of the DAG's vertices in which each vertex comes before all vertices to which it has outbound edges.

Every DAG (can be checked with DFS earlier) has at least one but possibly more topological sorts/ordering.

One of the main purpose of (at least one) topological sort of a DAG is for Dynamic Programming (DP) technique. For example, this topological sorting process is used internally in DP solution for SSSP on DAG.

7-11. Pengurutan Topologis

Kita dapat menggunakan antara O(V+E) DFS atau BFS untuk melakukan Pengurutan Topologis dari sebuah Graf Terarah Tidak-bersiklus (Directed Acyclic Graph, DAG).

Versi DFS membutuhkan hanya satu baris tambahan dibandingkan dengan DFS normal dan pada dasarnya adalah penjelajahan post-order dari graf tersebut. Coba Toposort (DFS) pada DAG contoh.

Versi BFS berdasarkan ide simpul-simpul tanpa sisi masuk (incoming edge) dan juga disebut sebagai algoritma Kahn. Coba Toposort (BFS/Kahn's) pada DAG contoh.

8. Aplikasi-Aplikasi DFS/BFS Lebih Lanjut

Pada saat ini, anda telah melihat DFS/BFS dan apa yang DFS/BFS bisa selesaikan (dengan hanya perubahan-perubahan kecil). Ada beberapa aplikasi-aplikasi tingkat lanjut yang membutuhkan lebih banyak perubahan-perubahan dan kami akan membiarkan murid-murid tingkat lanjut untuk mengeksplorasi mereka sendiri:

1. Pengecekan Graf Bipartit (varian DFS dan BFS),
2. Menemukan Articulation Points (Cut Vertices) dan Bridges dari sebuah Graf Tidak-terarah (DFS saja),
3. Menemukan Strongly Connected Components (SCCs) dari sebuah Graf Terarah (algoritma Tarjan dan Kosaraju), dan
4. Algoritma Pengecekan 2-SAT(isfiability).

Iklan: Detil-detilnya sudah ditulis di buku Competitive Programming.

9. Pengecekan Graf Bipartit

Kita bisa menggunakan O(V+E) DFS atau BFS (keduanya bekerja dengan mirip) untuk mengecek apakah sebuah graf yang diberikan adalah graf bipartit dengan memberi warna secara selang-seling (oranye dan biru dalam visualisasi ini) pada simpul-simpul yang berhubungan dan melaporkan 'non-bipartit' apabila kita terpaksa memberi warna yang sama pada dua simpul yang berhubungan atau 'bipartit' bila kita berhasil memberi melakukan proses 'pewarnaan dengan 2 warna saja'. Coba DFS_Checker atau BFS_Checker pada Graf Bipartit contoh.

Graf Bipartit memiliki aplikasi-aplikasi yang berguna di (masalah Pencocok Graf (Bipartit).

Perlu dicatat bahwa Graf-Graf Bipartit biasanya hanya didefinisikan untuk graf tak terarah dan visualisasi di halaman ini akan mengubah graf terarah masukan menjadi graf tak terarah secara otomatis sebelum melanjutkan. Langkah ini bersifat permanen dan tidak dapat dibatalkan, sehingga anda harus menggambar ulang graf terarah masukkan anda untuk hal-hal lainnya.

10. Cari Simpul Artikulasi dan Jembatan

Kita dapat memodifikasi (tetapi sayangnya, tidak dengan mudah) algoritma DFS O(V+E) menjadi algoritma untuk mencari simpul-simpul artikulasi & jembatan dari sebuah graf tak terarah.

Sebuah Simpul Potong (Cut Vertex), atau Titik Artikulasi (Articulation Point), adalah simpul dari sebuah graf tak terarah yang apabila simpul tersebut dihapuskan dari graf yang ada akan mengakibatkan graf tersebut menjadi tak terhubung. Demikian pula, sebuah jembatan (bridge) adalah sebuah sisi dari graf tak terarah yang kalau dihapus akan mengakibatkan graf tersebut menjadi tak terhubung.

Perlu dicatat bahwa algoritma pencari Simpul Potong & Jembatan ini hanya bekerja untuk graf-graf tak berarah dan visualisasi di halaman ini akan mengubah graf terarah masukan menjadi graf tak terarah secara otomatis sebelum melanjutkan. Langkah ini bersifat permanen dan tidak dapat dibatalkan, sehingga anda harus menggambar ulang graf terarah masukkan anda untuk hal-hal lainnya. Anda bisa mencoba Find Cut Vertices & Bridges pada graf contoh diatas.

11. Cari Strongly Connected Components (SCC)

Kita dapat memodifikasi (tetapi sayangnya, tidak dengan mudah) algoritma O(V+E) DFS menjadi algoritma untuk mencari Komponen-komponen yang Terhubung Kuat (Strongly Connected Components, SCCs) dari sebuah graf terarah G.

Sebuah SCC dari graf terarah G didefinisikan sebagai sub-graf S dari G dimana untuk tiap dua simpul u dan v dalam S, simpul u dapat mengunjungi simpul v secara langsung atau melalui sebuah jalur, dan vertex v juga bisa mengunjungi simpul u secara langsung atau melalui sebuah jalur.

Ada dua algoritma yang diketahui bisa menemukan SCCs dari sebuah Graf Terarah: Kosaraju dan Tarjan. Keduanya tersedia di visualisasi ini. Coba Kosaraju's Algorithm dan/atau Tarjan's Algorithm pada graf terarah contoh diatas.

12. Algoritma Pengecekan 2-SAT

Kami juga memiliki algoritma pengecekan 2-SAT. Diberikan sebuah instance dari masalah 2-Satisfiability (2-SAT) dalam bentuk konjungsi klausa-klausa: (klausa₁) ^ (klausa₂) ^ ... ^ (klausa_n) dan setiap klausa ditulis dalam bentuk disjungtif (maksimal 2 variabel var_a v var_b), tentukan apakah kita bisa memberikan nilai True (Benar)/False (Salah) ke variabel-variabel tersebut sehingga instance 2-SAT tersebut dapat menjadi true (benar), atau dengan kata lain dapat dipenuhi (satisfiable).

Ternyata, setiap klausa (a v b) dapat diubah menjadi empat simpul a, bukan a, b, dan bukan b dengan dua sisi (not a → b) dan (not b → a). Maka kita memiliki graf berarah. Jika ada setidaknya satu variabel dan negasinya dalam sebuah SCC (Strongly Connected Component) dari graf tersebut, kita tahu bahwa tidaklah mungkin untuk memenuhi instance 2-SAT ini.

Setelah pemodelan graf tersebut, kita dapat menjalankan algoritma pencarian SCC (Algoritma Kosaraju atau Tarjan) untuk menentukan apakah instance 2-SAT tersebut dapat dipenuhi.

13. Mana yang Lebih Baik?

Quiz: Which Graph Traversal Algorithm is Better?

Diskusi: Kenapa?

13-1. Jawabannya

14. Tambahan-Tambahan

Ada banyak hal yang masih bisa kita lakukan dengan hanya DFS dan/atau BFS...

14-1. Kuis Online

Ada pertanyaan-pertanyaan menarik tentang dua algoritma penjelajahan graf: DFS+BFS dan varian-varian dari masalah-masalah penjelajahan graf, silahkan latihan pada modul Penjelajahan Graf (tidak perlu login).

Tetapi, untuk pengguna yang teregistrasi, anda sebaiknya login dan pergi ke Halaman Latihan Utama untuk secara resmi menyelesaikan modul ini dan prestasi tersebut akan disimpan di akun pengguna anda.

14-2. Latihan-Latihan Online Judge

We also have a few programming problems that somewhat requires the usage of DFS and/or BFS: Kattis - reachableroads and Kattis - breakingbad.

Try to solve them and then try the many more interesting twists/variants of this simple graph traversal problem and/or algorithm.

You are allowed to use/modify our implementation code for DFS/BFS Algorithms:
dfs_cc.cpp/bfs.cpp
dfs_cc.java/bfs.java
dfs_cc.py/bfs.py
dfs_cc.ml/bfs.ml

14-3. Diskusi