Graflar
Gezinme ve en kısa yollar
Enlemesine Arama (BFS)
Bir kuyruk kullanarak grafı seviye seviye keşfeder — ağırlıksız graflarda en kısa yolların temelidir.
Süre O(V + E) · Alan O(V)
Derinlemesine Arama (DFS)
Geri izlemeden önce her dalda olabildiğince derine dalar — özyineleme veya yığınla gerçeklenir.
Süre O(V + E) · Alan O(V)
Dijkstra Algoritması
Negatif olmayan kenarlı ağırlıklı bir grafta kaynak düğümden diğer tüm düğümlere en kısa yolu bulur.
Süre O(V²) · Alan O(V)
Bellman-Ford
Her kenarı V−1 kez gevşeterek negatif kenar ağırlıklarında da çalışan, kaynaktan en kısa yollar.
Süre O(V · E) · Alan O(V)
Topolojik Sıralama
Bir YYG'nin düğümlerini her kenar ileri bakacak şekilde doğrusal sıralar — Kahn algoritması giriş derecesi 0 olan düğümleri ayıklar.
Süre O(V + E) · Alan O(V)
Prim MST
Bir başlangıç düğümünden minimum kapsayan ağacı büyütür; her zaman yeni bir düğüme ulaşan en ucuz kenarı ekler.
Süre O(V²) · Alan O(V)
Kruskal MST
Kenarları ağırlık sırasına göre ekleyerek minimum kapsayan ağaç kurar; döngü kenarlarını birleştir-bul ile reddeder.
Süre O(E log E) · Alan O(V)
A* Arama
Bir sezgiselle yönlendirilen en-iyi-öncelikli en kısa yol: en düşük g + düz-çizgi tahminine sahip düğümü genişletir.
Süre O(E) · Alan O(V)
Floyd-Warshall
Dinamik programlamayla tüm-çiftler en kısa yol: k turu her çifte, k düğümünde mola vermenin yolu kısaltıp kısaltmadığını sorar.
Süre O(V³) · Alan O(V²)