Polito DSA'da graph sorusunu görünce hemen BFS, DFS veya Dijkstra kodunu yazmaya başlamak cazip gelebilir. Fakat “yol bulmak” tek bir problem değildir. En az kenarla ulaşmak, toplam maliyeti en küçük yapmak ve bütün vertex'leri en ucuz ağla bağlamak farklı hedeflerdir. Yanlış hedefe doğru algoritma uygulamak, çalışan fakat soruyu çözmeyen bir program üretir.
Bu rehberde aynı açık veri sözleşmesini kullanan üç özgün C17 programı var: BFS/DFS traversal, Dijkstra ile tek kaynaktan shortest path ve Prim ile minimum spanning tree. Her dosya bağımsız derlenir. Önce sonucu neyin doğru yapacağını belirleyecek, sonra temsil, invariant, sınır durumları ve başarısız işlemde çıktı korunmasını inceleyeceğiz.
Ders bağlamı: 'da kontrol edilen 01URN Algorithms and Data Structures 2026/27 resmî kılavuzu, graph temsilleri, DFS/BFS, shortest path ve minimum spanning tree konularını içerir. Kendi ders kodunuzu ve grubunuzu Polito DSA ders rehberiyle karşılaştırın. Buradaki örnekler bağımsız çalışmadır; resmî sınav sorusu, öğrencinin yerine hazırlanmış teslim veya evrensel sınav formatı değildir.
1. Önce yol sorusunu seçin
Bir kampüsteki noktaları vertex, aralarındaki bağlantıları edge olarak düşünün. “En az kaç bağlantı geçerim?” sorusu kenar sayısını ölçer. “Yolculuk maliyeti kaç?” sorusu ağırlıkları toplar. “Bütün noktaları bağlayan ağın toplam kurulum maliyeti kaç?” sorusu ise tek bir başlangıçtan gidilen yolları değil, seçilen ağdaki kenarların toplamını en aza indirir.
BFS, kenar sayısı bakımından kısa yolları bulur; DFS, bir dalı derinlemesine araştırıp ziyaret sırası üretir. Dijkstra, negatif olmayan ağırlıklarla kaynaktan minimum maliyetleri hesaplar. MST bütün vertex'leri döngüsüz bağlayan minimum toplam ağırlıklı ağacı ister. DFS sırasını mesafe, MST'yi shortest-path tree olarak yorumlamak bu ayrımları kaybettirir.
Önce beklenen çıktının türünü yazın: erişilebilirlik, mesafe array'i, parent ilişkisi veya ağaç toplamı. “Algoritma doğru mu?” sorusunu bu çıktı sözleşmesine bağlayın. Aynı graph üzerinde birden fazla doğru ziyaret sırası veya eşit maliyetli ağaç bulunabilir; tek bir çizimin farklı olması her zaman hata değildir.
2. Tek graph modeli ve giriş sözleşmesi kullanın
Üç programda da yönsüz, self-loop ve paralel kenar içermeyen bir graph kullanıyoruz. n, 1–6 arasında; geçerli vertex indeksleri [0,n). Sabit boyutlu weight matrix'inin yalnız aktif n × n bölgesi okunur. Bu bölgedeki bütün hücreler başlatılmış olmalıdır. A, B, C, D, E ve F adları sırasıyla 0–5 indeksleridir.
-1 kenar yok demektir; 0 geçerli kenar maliyetidir. Köşegen -1 olmalı, matrix simetrik olmalı ve mevcut kenarlar 0–1000 aralığında kalmalıdır. Bu, bütün graph algoritmalarının zorunlu temsili değil, bu projelerin ortak sözleşmesidir. Özellikle sıfırı “kenar yok” sanan kontrol, bedelsiz bağlantıyı yanlışlıkla siler.
Fonksiyonlar NULL parametreyi, geçersiz n/kaynağı ve hatalı aktif hücreleri çıktı değişmeden reddeder. Graph geçerli, okunabilir nesne; out, doğru türde ayrı ve yazılabilir nesne olmalıdır. Bu nesneler çakışmamalıdır. NULL denetimi sarkan pointer'ı veya yanlış nesne adresini doğrulamaz. Bütün sonuç önce yerel struct'ta hazırlanır, yalnız başarıda out'a kopyalanır.
3. BFS mesafesini DFS ziyaret sırasından ayırın
İlk örnekte A–B maliyeti sıfır, A–C yedi, B–D iki ve D–E birdir; F izoledir. Traversal programı ağırlık büyüklüklerini değil, kenarın varlığını kullanır. A'dan C'ye yedi maliyetli tek kenar hâlâ bir hop'tur. Komşuları artan indeksle tarıyoruz; DFS önce B dalını tamamlayıp sonra C'ye döner.
#include <stdbool.h>#include <stddef.h>#include <stdio.h>enum { MAX_VERTICES = 6, NO_EDGE = -1, MAX_WEIGHT = 1000, INF = MAX_VERTICES * MAX_WEIGHT + 1};typedef struct { size_t n; int weight[MAX_VERTICES][MAX_VERTICES];} Graph;typedef struct { size_t bfs_order[MAX_VERTICES]; size_t dfs_order[MAX_VERTICES]; size_t bfs_count; size_t dfs_count; int distance[MAX_VERTICES];} Traversal;static bool graph_valid(const Graph *graph){ if (graph == NULL || graph->n == 0 || graph->n > MAX_VERTICES) { return false; } for (size_t u = 0; u < graph->n; ++u) { for (size_t v = 0; v < graph->n; ++v) { int weight = graph->weight[u][v]; if (weight < NO_EDGE || weight > MAX_WEIGHT || (u == v && weight != NO_EDGE) || weight != graph->weight[v][u]) { return false; } } } return true;}static void dfs_visit(const Graph *graph, size_t u, bool seen[], Traversal *result){ seen[u] = true; result->dfs_order[result->dfs_count++] = u; for (size_t v = 0; v < graph->n; ++v) { if (graph->weight[u][v] != NO_EDGE && !seen[v]) { dfs_visit(graph, v, seen, result); } }}bool graph_traverse(const Graph *graph, size_t source, Traversal *out){ if (out == NULL || !graph_valid(graph) || source >= graph->n) { return false; } Traversal result = {0}; for (size_t v = 0; v < MAX_VERTICES; ++v) { result.bfs_order[v] = MAX_VERTICES; result.dfs_order[v] = MAX_VERTICES; result.distance[v] = -1; } size_t queue[MAX_VERTICES]; size_t head = 0; size_t tail = 0; result.distance[source] = 0; queue[tail++] = source; while (head < tail) { size_t u = queue[head++]; result.bfs_order[result.bfs_count++] = u; for (size_t v = 0; v < graph->n; ++v) { if (graph->weight[u][v] != NO_EDGE && result.distance[v] == -1) { result.distance[v] = result.distance[u] + 1; queue[tail++] = v; } } } bool seen[MAX_VERTICES] = {false}; dfs_visit(graph, source, seen, &result); *out = result; return true;}int main(void){ const Graph graph = {6, { {-1, 0, 7, -1, -1, -1}, {0, -1, -1, 2, -1, -1}, {7, -1, -1, -1, -1, -1}, {-1, 2, -1, -1, 1, -1}, {-1, -1, -1, 1, -1, -1}, {-1, -1, -1, -1, -1, -1} }}; Traversal result; if (!graph_traverse(&graph, 0, &result)) { return 1; } printf("bfs:"); for (size_t i = 0; i < result.bfs_count; ++i) { printf(" %zu", result.bfs_order[i]); } printf("\ndfs:"); for (size_t i = 0; i < result.dfs_count; ++i) { printf(" %zu", result.dfs_order[i]); } printf("\ndistance:"); for (size_t v = 0; v < graph.n; ++v) { printf(" %d", result.distance[v]); } putchar('\n'); return 0;}BFS sırası 0 1 2 3 4, DFS sırası 0 1 3 4 2, BFS mesafeleri 0 1 1 2 3 -1'dir. F için -1, erişilemez demektir. DFS'nin C'yi en son ziyaret etmesi, A–C mesafesini dört yapmaz. İki traversal da yalnız kaynağın bağlı bileşenini gezer; bütün bileşenleri başlatan bir dış döngü eklenmemiştir.
4. Traversal invariant'ını ve sınırları kontrol edin
BFS'de keşfedilen vertex kuyruğa eklenmeden önce işaretlenir. Böylece birden fazla komşudan görülen aynı vertex tekrar tekrar kuyruğa girmez; altı elemanlık alan yeterli kalır. Kuyruktan çıkanlar mesafe katmanlarıyla ilerler. DFS'de de vertex, komşularına recursive çağrı yapmadan önce seen olur. Böylece cycle, aynı vertex için yeni bir çağrı zinciri başlatmaz.
Örnekte A işlendikten sonra kuyruk B,C taşır. B işlenince D sona eklenir; C henüz çıkmadan D işlenmez. C yeni vertex bulmaz, D ise E'yi ekler. Her adımda kuyruğun önünü, arkasını ve yeni keşfedilenleri ayrı yazın. DFS'nin B,D,E dalını önce tamamlamasıyla farkı böyle görünür kılabilirsiniz; yalnız son ziyaret listesini ezberlemeyin.
Tek vertex, izole kaynak, cycle, bağlantısı koparılmış F ve sıfır ağırlıklı kenar deneyin. Ziyaret sayıları yalnız erişilen vertex sayısıdır; order array'lerinin kullanılmayan sonu sentinel 6 taşır. Yalnız ilk count elemanını ziyaret sırası olarak okuyun. Parent veya mesafe üretmeyen bir DFS fonksiyonundan kendiliğinden shortest path sonucu çıkarmayın.
Algoritma ayrımını yazarların algs4 BreadthFirstPaths ve DepthFirstSearch kaynaklarıyla karşılaştırabilirsiniz. Bunlar Sedgewick ve Wayne'in Java uygulamalarıdır; buradaki bağımsız C17 programlarının API'si veya kopyası olarak sunulmuyor.
5. Dijkstra ile negatif olmayan yol maliyetlerini hesaplayın
İkinci graph beş vertex içerir: A–B:2, A–C:3, B–C:2, C–D:4, B–D:9, D–E:1, C–E:8 ve A–D:10. Kaynak A'dır. D'ye doğrudan gitmek on tutar; A–C–D yolu yedi tutar. BFS burada doğrudan kenarı bir hop sayabilir, fakat toplam maliyet için bu yeterli ölçüt değildir.
#include <stdbool.h>#include <stddef.h>#include <stdio.h>enum { MAX_VERTICES = 6, NO_EDGE = -1, MAX_WEIGHT = 1000, INF = MAX_VERTICES * MAX_WEIGHT + 1};typedef struct { size_t n; int weight[MAX_VERTICES][MAX_VERTICES];} Graph;typedef struct { int distance[MAX_VERTICES]; size_t parent[MAX_VERTICES];} ShortestPaths;static bool graph_valid(const Graph *graph){ if (graph == NULL || graph->n == 0 || graph->n > MAX_VERTICES) { return false; } for (size_t u = 0; u < graph->n; ++u) { for (size_t v = 0; v < graph->n; ++v) { int weight = graph->weight[u][v]; if (weight < NO_EDGE || weight > MAX_WEIGHT || (u == v && weight != NO_EDGE) || weight != graph->weight[v][u]) { return false; } } } return true;}bool graph_dijkstra(const Graph *graph, size_t source, ShortestPaths *out){ if (out == NULL || !graph_valid(graph) || source >= graph->n) { return false; } ShortestPaths result; bool settled[MAX_VERTICES] = {false}; for (size_t v = 0; v < MAX_VERTICES; ++v) { result.distance[v] = INF; result.parent[v] = MAX_VERTICES; } result.distance[source] = 0; for (size_t step = 0; step < graph->n; ++step) { size_t u = MAX_VERTICES; int best = INF; for (size_t v = 0; v < graph->n; ++v) { if (!settled[v] && result.distance[v] < best) { best = result.distance[v]; u = v; } } if (u == MAX_VERTICES) { break; } settled[u] = true; for (size_t v = 0; v < graph->n; ++v) { int weight = graph->weight[u][v]; if (weight != NO_EDGE && !settled[v]) { int candidate = result.distance[u] + weight; if (candidate < result.distance[v]) { result.distance[v] = candidate; result.parent[v] = u; } } } } *out = result; return true;}int main(void){ const Graph graph = {5, { {-1, 2, 3, 10, -1}, {2, -1, 2, 9, -1}, {3, 2, -1, 4, 8}, {10, 9, 4, -1, 1}, {-1, -1, 8, 1, -1} }}; ShortestPaths result; if (!graph_dijkstra(&graph, 0, &result)) { return 1; } printf("distance:"); for (size_t v = 0; v < graph.n; ++v) { printf(" %d", result.distance[v]); } printf("\nparent:"); int tree_weight = 0; for (size_t v = 0; v < graph.n; ++v) { printf(" %zu", result.parent[v]); if (result.parent[v] != MAX_VERTICES) { tree_weight += graph.weight[result.parent[v]][v]; } } printf("\nspt_weight: %d\n", tree_weight); return 0;}Mesafeler 0 2 3 7 8, parent array'i 6 0 0 2 3'tür. Root'un parent'ı yoktur: 6 geçerli vertex değildir, sentinel'dir. Dijkstra, henüz kesinleşmemiş en düşük geçici mesafeyi seçer ve komşulara daha ucuz yol sunup sunmadığını kontrol eder. Bu güncellemeye relaxation denir.
Elle izlerken A'dan sonra B için iki, C için üç ve D için on yazın. B kesinleştiğinde C'ye dört, D'ye on bir maliyetli adaylar gelir; ikisi de mevcut değeri iyileştirmez. C kesinleşince D yediye, E on bire iner. D'nin işlenmesi E'yi sekize indirir. Her adayın bir yol toplamı olduğunu ve yalnız karşılaştırma kazanırsa saklandığını açıklayın.
Negatif olmayan maliyetler, seçilen minimum mesafenin kesinleştirilmesini destekler. Sıfır maliyet kabul edilir; “pozitif olmalı” diye ek koşul koymuyoruz. Negatif kenar ise bu ortak veri sözleşmesinde reddedilir. Yazarların algs4 DijkstraSP kaynağı da negatif olmayan ağırlık ön koşulunu açıklar; onların heap tabanlı Java sürümüyle bizim matrix taramasının maliyetini aynı saymayın.
6. Erişilemeyen vertex, eşitlik ve overflow politikasını belirleyin
Dijkstra bağlantısız graph'ı hata saymaz: erişilemeyen mesafe INF=6001, parent ise 6 kalır. INF normal bir maliyet veya vertex indeksi değildir. Kaynak dışındaki bir hedefe parent zinciriyle gitmeden önce mesafesini kontrol edin. Bu program, olmayan yolu sıfır maliyetliymiş gibi göstermemelidir.
Eşit geçici mesafede küçük indeks önce seçilir. Relaxation yalnız kesin iyileşmede parent'ı değiştirir; eşit maliyetli aday eski parent'ı korur. Bu deterministik politika, tek mümkün shortest-path tree olduğu anlamına gelmez. Sıfır ağırlıklı cycle testinde parent zincirinin kaynakta bittiğini de doğrulayın; yalnız mesafe array'inin doğru görünmesi yeterli değildir.
En fazla altı vertex ve kenar başına en fazla 1000 maliyetle basit bir yol beş kenar, yani en fazla 5000 tutar. Relaxation'da bir kenar daha ekleyen hesap için 6000 güvenli üst sınırdır; 6001 bunun üstünde ayrılmış sentineldir. Bu küçük sayılar int aralığına sığar. Boyut veya ağırlık sınırını büyütürseniz aynı INF'yi koruyup taşma olmadığını varsaymayın.
7. Prim ile minimum spanning tree kurun
Şimdi ikinci graph'ın bütün vertex'lerini minimum toplam kenar maliyetiyle bağlayalım. Aynı veri, farklı amaçtır. Prim'de key, kaynaktan birikmiş yol maliyeti değil, mevcut ağaçtan ilgili vertex'e ulaşan en ucuz tek bağlantıdır. Güncellemede mesafeye ağırlık eklemek, bu iki algoritmayı yanlışlıkla karıştırır.
#include <stdbool.h>#include <stddef.h>#include <stdio.h>enum { MAX_VERTICES = 6, NO_EDGE = -1, MAX_WEIGHT = 1000, INF = MAX_VERTICES * MAX_WEIGHT + 1};typedef struct { size_t n; int weight[MAX_VERTICES][MAX_VERTICES];} Graph;typedef struct { size_t parent[MAX_VERTICES]; int total_weight;} SpanningTree;static bool graph_valid(const Graph *graph){ if (graph == NULL || graph->n == 0 || graph->n > MAX_VERTICES) { return false; } for (size_t u = 0; u < graph->n; ++u) { for (size_t v = 0; v < graph->n; ++v) { int weight = graph->weight[u][v]; if (weight < NO_EDGE || weight > MAX_WEIGHT || (u == v && weight != NO_EDGE) || weight != graph->weight[v][u]) { return false; } } } return true;}bool graph_prim(const Graph *graph, size_t source, SpanningTree *out){ if (out == NULL || !graph_valid(graph) || source >= graph->n) { return false; } SpanningTree result; int key[MAX_VERTICES]; bool in_tree[MAX_VERTICES] = {false}; result.total_weight = 0; for (size_t v = 0; v < MAX_VERTICES; ++v) { key[v] = INF; result.parent[v] = MAX_VERTICES; } key[source] = 0; for (size_t step = 0; step < graph->n; ++step) { size_t u = MAX_VERTICES; int best = INF; for (size_t v = 0; v < graph->n; ++v) { if (!in_tree[v] && key[v] < best) { best = key[v]; u = v; } } if (u == MAX_VERTICES) { return false; } in_tree[u] = true; result.total_weight += best; for (size_t v = 0; v < graph->n; ++v) { int weight = graph->weight[u][v]; if (weight != NO_EDGE && !in_tree[v] && weight < key[v]) { key[v] = weight; result.parent[v] = u; } } } *out = result; return true;}int main(void){ const Graph graph = {5, { {-1, 2, 3, 10, -1}, {2, -1, 2, 9, -1}, {3, 2, -1, 4, 8}, {10, 9, 4, -1, 1}, {-1, -1, 8, 1, -1} }}; SpanningTree result; if (!graph_prim(&graph, 0, &result)) { return 1; } printf("parent:"); for (size_t v = 0; v < graph.n; ++v) { printf(" %zu", result.parent[v]); } printf("\nmst_weight: %d\n", result.total_weight); int path_weight = 0; size_t vertex = 2; while (vertex != 0) { size_t parent = result.parent[vertex]; if (parent == MAX_VERTICES) { return 1; } path_weight += graph.weight[parent][vertex]; vertex = parent; } printf("mst_path_A_C: %d\n", path_weight); return 0;}Parent'lar 6 0 1 2 3, seçilen kenarlar A–B, B–C, C–D ve D–E'dir. Toplam 2+2+4+1=9 olur. Başlangıç vertex'i ağacın parent yönünü belirler; amaç tek bir kaynaktan mesafeleri en aza indirmek değildir. Eşit key durumunda yine küçük indeks önce seçilir.
Graph bağlantısızsa bu arayüz false döndürür ve önceki çıktının tamamını korur; sessizce kısmi ağacı başarı diye vermez. Tek vertex'te sıfır ağırlıklı boş kenar kümesi geçerlidir. Genel Prim negatif ağırlıklarla da çalışabilir; bu örneğin bunları reddetmesi algoritmanın zorunluluğu değil, üç dosyada ortak tuttuğumuz girdi politikasıdır. algs4 PrimMST, ayrıca bağlantısız girdide forest üreten farklı bir arayüz örneğidir.
8. MST'nin shortest-path tree olmadığını aynı veride gösterin
Dijkstra'nın parent kenarları A–B:2, A–C:3, C–D:4 ve D–E:1'dir; bu shortest-path tree'nin kenar toplamı ondur. Prim'in ağacı dokuz tutar. Buna rağmen MST üzerinde A'dan C'ye A–B–C yolu dört tutarken orijinal graph'ta A–C kenarı üçtür. Daha ucuz ağ kurmak, ağacın içindeki her yolu en kısa yapmaz.
Üç toplamı ayrı yazın: seçilen ağacın bütün kenarlarının toplamı, kaynak–hedef yolunun toplamı ve kaynaktan bütün vertex'lere mesafeler array'i. Bunları aynı değişkende tutmayın. Kapaktaki üç vertex'li mini örnek de A–B:2, B–C:2, A–C:3 ile bu farkı gösterir; kapak ağacı dört tutar, buradaki beş vertex'li MST ise dokuz.
9. Bağımsız oracle ve temsil maliyetiyle doğrulayın
Küçük graph'larda shortest path sonuçlarını ayrı bir Floyd–Warshall uygulamasıyla, MST toplamını uygun kenar alt kümelerini deneyen bağımsız yöntemle karşılaştırın. Yalnız toplamı değil parent kenarlarının varlığını, cycle oluşmadığını ve kapsanan vertex sayısını da sınayın. Traversal'da her erişilen vertex tam bir kez görünmeli; BFS katmanları kenar uzaklıklarını sağlamalıdır.
NULL çıktı, n=0/7, geçersiz kaynak, asimetri, köşegende sıfır, ağırlık -2/1001 ve bağlantısız Prim denemelerinde önceden hazırlanmış çıktının değişmediğini kontrol edin. Geçerli graph'ın da aynı kaldığını karşılaştırın. Bu kontroller nesnelerin geçerli ve çakışmayan alanlarda olması ön koşuluyla yapılır; rastgele adresleri güvenlik testi diye dereference etmeyin.
Bu matrix sürümlerinde doğrulama ve taramalar genellenmiş V modelinde O(V²) maliyetlidir; ek çalışma alanı O(V)'dir. Adjacency list için bilinen BFS/DFS O(V+E) sonucu doğrudan bu koda taşınmaz. Uygulamamız V'yi altıyla sınırlar; geniş veri için temsil ve algoritma sürümünü yeniden seçin. Her dosyayı ayrı derleyin: cc -std=c17 -Wall -Wextra -Wpedantic -Werror graph_traversal.c -o graph_traversal. Diğer dosyalarda adı değiştirin; üç main'i tek executable'da birleştirmeyin.
10. Polito DSA'da sonraki adımı sorunun amacına göre seçin
Graph Lab rehberinde temsil, frontier ve parent değişimlerini gözlemleyebilirsiniz. Buradaki üç C dosyasının Lab'de hazır olduğunu veya araca yapıştırılarak çalıştırılabildiğini iddia etmiyoruz. Bağımsız derleyici ve kendi testleriniz gerekir. Araç kataloğu Academy Lab sayfasında yer alır.
Kuyruk/sahiplik temeli için C ile ADT, Stack ve Queue rehberine; çağrı/dönüş kontrolü için Recursion ve Backtracking rehberine dönebilirsiniz. Hata kaydınız ve ders kodunuzla Polito DSA özel ders sürecini inceleyin. Hedef, öğrencinin doğru problemi seçip kendi çözümünü açıklayabilmesidir.
Websoftik Academy, Politecnico di Torino'dan bağımsızdır. Güncel değerlendirme kuralları için kendi grubunuzun duyuruları esas alınır. Bu özgün alıştırmalar not veya geçme garantisi vermez; değerlendirilecek ödev ya da sınav öğrenci yerine çözülmez.
