En Kısa Yol
Coddy'nin Graflar - Veri Yapıları Serisi #9 kursunda ders 12 / 14.
start noktasından end noktasına gitmek için en az kaç kenar gerekir? Ağırlıksız bir grafikte (her kenarın maliyeti eşittir), cevap tam olarak BFS'nin hesapladığı şeydir. BFS, köşeleri başlangıçtan itibaren artan mesafelerde ziyaret ettiği için, end noktasına ilk ulaştığımızda bu en kısa yol üzerindedir.
İşin püf noktası, her köşeyi o ana kadarki mesafesiyle birlikte kuyruğa eklemektir. (start, 0) ile başlayın. d mesafesindeki bir köşeden yeni bir komşu v keşfettiğiniz her seferde, (v, d + 1) değerini kuyruğa ekleyin. v == end olduğunda, d + 1 değerini döndürün.
İki uç durum. Eğer start == end ise, cevap 0'dır. Eğer BFS, end noktasına hiç ulaşmadan biterse, bu ikisi farklı bağlı bileşenlerdedir ve cevap -1'dir.
Görev
KolayBir 2D tam sayı dizisi adjacency, bir tam sayı start ve bir tam sayı end alan ve start noktasından end noktasına olan en kısa mesafeyi (kenar sayısı) döndüren bir shortestPath fonksiyonu yazın.
- Eğer
start == endise,0döndürün. - Eğer
endnoktasınastartnoktasından ulaşılamıyorsa,-1döndürün. - Aksi takdirde, aralarındaki minimum kenar sayısını döndürün.
Graph sınıfını kullanmalısınız (graph içinde sağlanmıştır) - komşuluk modellemesi için dilin yerleşik yapılarını (map'ler, set'ler) kullanmayın. Algoritma için yardımcı veriler (ziyaret edilenler set'leri, kuyruklar) standart kütüphane tiplerini kullanabilir.
Kendin dene
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start, end;
if (scanf("%d %d %d %d", &n, &m, &start, &end) != 4) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%d\n", shortestPath(adjacency, m, start, end));
return 0;
}