BFS
Coddy'nin Graflar - Veri Yapıları Serisi #9 kursunda ders 10 / 14.
Sıradaki zorluklar, az önce oluşturduğunuz Graph sınıfını kullanmak üzere tasarlanmıştır.
Her zorluk size kilitli bir graph dosyası (önceki bölümdeki son Graph hali) ve içinde Graph yapısını kullanan bir fonksiyon yazacağınız yeni bir solution dosyası ile birlikte gelir.
İlk algoritmamız: Breadth-First Search (Genişlik Öncelikli Arama). Bir köşeden başlayarak, BFS ulaşılabilir tüm köşeleri dalgalar halinde ziyaret eder: önce başlangıç, sonra bir kenar uzaklıktaki her şey, sonra iki kenar uzaklıktaki her şey ve bu şekilde devam eder. Klasik uygulama bir queue (kuyruk) kullanır: başlangıcı kuyruğa ekle (enqueue), ardından tekrar tekrar kuyruktan çıkar (dequeue), köşeyi ziyaret edildi olarak kaydet ve ziyaret edilmemiş komşuları kuyruğa ekle.
Komşu listelerinin sabit bir sırası olmadığı için, iki doğru BFS çalışması farklı gezinme sıraları üretebilir. Bu zorlukta cevabı deterministik hale getirmek için, her köşenin komşularını kuyruğa eklemeden önce artan sırada sıralayı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 itibaren BFS ziyaret sırasını bir tam sayı listesi olarak döndüren bir bfs fonksiyonu yazın.
Grafı oluşturun: adjacency içindeki her [u, v] için g.addEdge(u, v) fonksiyonunu çağırın. Ardından bir kuyruk (queue) kullanarak start düğümünden BFS yapın. Bir düğümün komşularını işlerken, çıktının deterministik olması için onları artan düzende sıralayın.
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, kuyruklar) standart kütüphane tiplerini 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 = bfs(adjacency, m, start, out);
for (int i = 0; i < outn; i++) {
if (i > 0) printf(" ");
printf("%d", out[i]);
}
printf("\n");
return 0;
}