DFS
Pelajaran 11 dari 14 dalam kursus Graf, Seri Struktur Data #9 di Coddy.
Depth-First Search menelusuri jauh sebelum melebar. Mulai dari sebuah vertex, algoritma ini mengikuti satu edge sejauh mungkin, lalu kembali ke titik sebelumnya dan mencoba edge berikutnya. Versi iteratif menggunakan stack: ambil sebuah vertex, catat, lalu masukkan kembali tetangga yang belum dikunjungi ke dalam stack.
Agar DFS menghasilkan urutan traversal yang deterministik dalam tantangan ini, masukkan tetangga dalam urutan terurut terbalik. Dengan begitu, tetangga terkecil berada di bagian teratas stack dan diproses lebih dahulu, sesuai dengan urutan yang dihasilkan oleh DFS rekursif atas tetangga dalam urutan menaik.
Perhatikan kemungkinan sebuah vertex dimasukkan ke stack dua kali (tetangga yang berbeda bisa sama-sama memilikinya). Periksa set yang sudah dikunjungi di bagian teratas perulangan, lalu lewati jika vertex tersebut sudah dikunjungi.
Tantangan
MudahBuat fungsi dfs yang menerima array int 2D adjacency (setiap baris adalah edge [u, v]) dan int start, lalu mengembalikan urutan kunjungan DFS dari start sebagai list int.
Bangun graph dengan menambahkan setiap edge. Gunakan DFS iteratif dengan stack: keluarkan satu vertex, jika belum dikunjungi, catat vertex itu dan masukkan tetangganya dalam urutan terurut terbalik agar yang terkecil diproses terlebih dahulu.
Kamu harus menggunakan class Graph (disediakan di graph), jangan gunakan bawaan bahasa (maps, sets) untuk memodelkan adjacency. Data tambahan untuk algoritma (visited sets, stacks) boleh menggunakan tipe dari stdlib.
Coba sendiri
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start;
if (scanf("%d %d %d", &n, &m, &start) != 3) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
int out[MAX_VERTICES];
int outn = dfs(adjacency, m, start, out);
for (int i = 0; i < outn; i++) {
if (i > 0) printf(" ");
printf("%d", out[i]);
}
printf("\n");
return 0;
}
Semua pelajaran di Graf, Seri Struktur Data #9
Latihan sendiri: Compiler C online