DFS
Coddy'nin Graflar - Veri Yapıları Serisi #9 kursunda ders 11 / 14.
Derinlik Öncelikli Arama (Depth-First Search), genişlemeden önce derine iner. Bir köşeden başlayarak, bir kenarı mümkün olduğunca uzağa kadar takip eder, ardından geri döner ve bir sonrakini dener. Yinelemeli sürüm bir yığın (stack) kullanır: bir köşeyi yığından çıkarın (pop), kaydedin ve ziyaret edilmemiş komşularını tekrar yığına ekleyin (push).
Bu görevde DFS'nin belirlenmiş bir dolaşma sırası oluşturmasını sağlamak için komşuları ters sıralanmış düzende yığına ekleyin. Bu sayede en küçük komşu yığının en üstüne gelir ve ilk önce işlenir; bu da artan düzendeki komşular üzerinde çalışan özyinelemeli bir DFS'nin üreteceği sırayla eşleşir.
Bir köşenin iki kez yığına eklenmesine karşı dikkatli olun (farklı komşuların her ikisi de ona sahip olabilir). Döngünün başında ziyaret edilenler (visited) kümesini kontrol edin ve zaten ziyaret edilmişse atlayın.
Görev
KolayBir 2D tam sayı dizisi adjacency (her satır bir [u, v] kenarıdır) ve bir tam sayı start alan ve start düğümünden başlayarak DFS ziyaret sırasını bir tam sayı listesi olarak döndüren bir dfs fonksiyonu yazın.
Her bir kenarı ekleyerek grafı oluşturun. Bir yığın (stack) kullanarak yinelemeli (iterative) DFS uygulayın: bir düğümü yığından çıkarın, eğer ziyaret edilmemişse kaydedin ve komşularını ters sıralı (reverse-sorted) olarak yığına ekleyin; böylece en küçük olan ilk önce işlenir.
Graph sınıfını kullanmalısınız (graph içinde sağlanmıştır) - komşuluk yapısını modellemek için dilin yerleşik yapılarını (map'ler, set'ler) kullanmayın. Algoritma için yardımcı veriler (ziyaret edilenler set'i, yığınlar) standart kütüphane (stdlib) türlerini kullanabilir.
Kendin dene
#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;
}