Implementation (Part 2)
Coddy'nin Derinlik Öncelikli Arama - Graf Algoritmaları kursunda ders 6 / 9.
Şimdi tüm grafı bir yığın ile dolaşıyoruz.
Görev
OrtaŞimdi tam dolaşımı (traversal) oluşturun.
n, düz edges dizisi (yönsüz) ve bir start düğümü alan ve DFS'nin start düğümünden başlayarak düğümleri ziyaret etme sırasını döndüren dfs adında bir fonksiyon yazın.
Önce komşuluk listesini oluşturun (her düğümün komşularını artan sırada sıralayın). Ardından bir yığın (stack) kullanarak yinelemeli (iterative) bir DFS çalıştırın. Sadece start düğümünden ulaşılabilen düğümler ziyaret edilir.
Komşuları artan sırada ziyaret etmek için, onları yığına en büyükten en küçüğe doğru itin.
Kendin dene
#include <stdlib.h>
int* dfs(int n, int* edges, int edges_size, int start, int* returnSize) {
// Buraya kod yazın
*returnSize = 0;
return edges;
}
Kendini test etBu ders kısa bir quiz içerir. Soruları yanıtlamak ve ilerlemeni kaydetmek için derse başla.
Derinlik Öncelikli Arama - Graf Algoritmaları bölümündeki tüm dersler
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity