Graflar: gösterim, BFS, DFS ve topolojik sıralama

Ağaçlarda her düğümün tek ebeveyni vardı. Graf (graph) bu kısıtı kaldırır: herhangi iki köşe arasında bağlantı olabilir, döngü olabilir, hiç bağlantı olmayabilir. Yol haritası, sosyal ağ, ders önkoşulları, internet bağlantıları hep graftır. Gelecek hafta bunların üzerinde en kısa yol algoritmalarını çalıştıracağız; bu hafta temeli kuruyoruz: grafı nasıl saklarız, nasıl gezeriz.

Sınavda bu haftadan gelecek sorular:

1. Gösterim: “Bu grafın komşuluk listesini/matrisini yaz”, “bellek ne kadar?”
2. Gezinme sırası: “0’dan BFS/DFS yap, ziyaret sırasını yaz.” Kural genelde “komşuları artan sırada gez”.
3. Topolojik sıralama: önkoşul grafında geçerli bir ders sırası.
4. Metot yazma: BFS, DFS ya da bileşen sayma.

Terimler

Yönsüz grafta her kenar iki köşenin derecesine katkı yapar, o yüzden derece toplamı = 2E. V köşeli bir grafta en fazla $V(V-1)/2$ kenar olur (yönlüde $V(V-1)$). E bu sınıra yakınsa graf yoğun (dense), V mertebesindeyse seyrek (sparse).

Örnek graf G

Bu sayfanın bütün gezinme örnekleri şu grafta:

  1 --- 3 --- 0
  |     |     |
  4 --- 6 --- 5 --- 2 --- 7

Kenarlar: 0-3, 0-5, 1-3, 1-4, 2-5, 2-7, 3-6, 4-6, 5-6. Toplam 9 kenar, derece toplamı 18.

Gösterim 1: komşuluk matrisi (adjacency matrix)

V×V boyutunda bir boolean ya da int dizi: a[u][v] = 1 ise kenar var. Yönsüz grafta matris simetriktir. Küçük bir örnek, kenarlar 0-1, 0-2, 1-2, 2-3:

     0  1  2  3
 0 [ 0, 1, 1, 0 ]
 1 [ 1, 0, 1, 0 ]
 2 [ 1, 1, 0, 1 ]
 3 [ 0, 0, 1, 0 ]

Ağırlıklı grafta 1 yerine ağırlık yazılır, kenar yoksa sonsuz (ya da 0) konur. Avantajı: “u ile v bağlı mı?” sorusu $O(1)$. Dezavantajı: kenar sayısından bağımsız olarak $V^2$ bellek. 1 milyon köşeli bir yol ağı için $10^{12}$ hücre olurdu.

Gösterim 2: komşuluk listesi (adjacency list)

Her köşe için komşularının listesi. Java’da en pratik hali List<List<Integer>>:

int n = 8;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
int[][] edges = {{0,3},{0,5},{3,1},{3,6},{5,6},{5,2},{1,4},{6,4},{2,7}};
for (int[] e : edges) {
    adj.get(e[0]).add(e[1]);   // yönsüz: iki yöne de ekle
    adj.get(e[1]).add(e[0]);
}
for (List<Integer> l : adj) Collections.sort(l);
System.out.println(adj);

[[3, 5], [3, 4], [5, 7], [0, 1, 6], [1, 6], [0, 2, 6], [3, 4, 5], [2]]

Listelerin toplam uzunluğu yönsüzde 2E, yönlüde E. Bellek $O(V + E)$.

Gerçek graflar neredeyse hep seyrek olduğu için varsayılan seçim listedir.

Genişlik öncelikli arama (BFS)

BFS (breadth-first search) başlangıçtan kat kat yayılır: önce 1 kenar uzaklıktakiler, sonra 2, sonra 3. Aracı kuyruktur.

static void bfs(List<List<Integer>> adj, int s) {
    int[] dist = new int[adj.size()];
    Arrays.fill(dist, -1);              // -1 = görülmedi
    Deque<Integer> q = new ArrayDeque<>();
    dist[s] = 0;
    q.add(s);
    while (!q.isEmpty()) {
        int v = q.poll();
        System.out.print(v + " ");
        for (int w : adj.get(v))
            if (dist[w] == -1) {        // ilk kez görülüyor
                dist[w] = dist[v] + 1;
                q.add(w);
            }
    }
}

G üzerinde 0’dan iz:

çıkan  eklenen    kuyruk
0      3, 5       [3, 5]
3      1, 6       [5, 1, 6]
5      2          [1, 6, 2]
1      4          [6, 2, 4]
6      -          [2, 4]
2      7          [4, 7]
4      -          [7]
7      -          []
sıra: 0 3 5 1 6 2 4 7
dist: 0:0 1:2 2:2 3:1 4:3 5:1 6:2 7:3

BFS’in süper gücü: ağırlıksız grafta dist dizisi tam olarak en kısa yolun kenar sayısıdır. Bir köşe kuyruğa ilk girdiğinde en kısa mesafesiyle girer, çünkü kuyruk mesafeleri sırayla işler. parent dizisi tutarsan yolun kendisini de geri çıkarabilirsin.

TUZAK · işaretlemeyi ne zaman yaparsın? Köşeyi kuyruğa eklerken görüldü olarak işaretle. Çıkarırken işaretlersen aynı köşe kuyruğa birden fazla kez girer: 6, hem 3’ten hem 5’ten eklenirdi. Sonuç sırası ve karmaşıklık bozulur.

Derinlik öncelikli arama (DFS)

DFS (depth-first search) bir yolda gidebildiği kadar gider, çıkmaza girince geri döner (backtracking). Özyinelemeli yazımı ağacın preorder gezinmesine çok benzer; tek fark visited dizisi, çünkü grafta döngü var.

static void dfs(List<List<Integer>> adj, int v, boolean[] visited) {
    visited[v] = true;
    System.out.print(v + " ");
    for (int w : adj.get(v))
        if (!visited[w]) dfs(adj, w, visited);
}

G üzerinde 0’dan:

dfs(0) -> 3
  dfs(3) -> 0 görüldü, 1
    dfs(1) -> 3 görüldü, 4
      dfs(4) -> 1 görüldü, 6
        dfs(6) -> 3, 4 görüldü, 5
          dfs(5) -> 0 görüldü, 2
            dfs(2) -> 5 görüldü, 7
              dfs(7) -> geri dön
sıra: 0 3 1 4 6 5 2 7

Yığın ile DFS

Özyineleme yerine açık bir yığın (stack) da kullanılabilir: köşeyi çıkar, görülmüşse atla, değilse ziyaret et ve görülmemiş komşularını it. Burada sıra değişir:

komşuları ARTAN sırada it:  0 5 6 4 1 3 2 7
komşuları AZALAN sırada it: 0 3 1 4 6 5 2 7

Yığın son giren ilk çıkar mantığıyla çalıştığı için artan iterse en büyük komşu önce çıkar. Özyinelemeli DFS ile aynı sırayı istiyorsan komşuları ters sırada it. Sınavda “using a stack” yazıyorsa bu farkı mutlaka hesaba kat.

BFS ve DFS karşılaştırması

Bağlı bileşenler (connected components)

Graf bağlı değilse tek bir BFS/DFS her köşeye ulaşamaz. Çözüm: köşeleri sırayla dolaş, görülmemiş olan her köşeden yeni bir gezinme başlat. Her başlatma bir bileşen demektir.

Köşeler 0..8, kenarlar 0-1, 1-2, 3-4, 5-6, 6-7, 5-7:

0 - 1 - 2     3 - 4     5 - 6     8
                         \ /
                          7
bileşen etiketleri: [0,0,0,1,1,2,2,2,3]
bileşen sayısı: 4

Hiç kenarı olmayan 8 de tek başına bir bileşendir. Kodun tamamı soru bankasında.

Topolojik sıralama (topological sort)

Yönlü bir grafta her u→v kenarı için u’nun v’den önce geldiği bir köşe sırası. Klasik örnek ders önkoşulları: SEN2211 → SEN2212 ise önce 2211 alınır. Sadece DAG’da mümkündür; döngü varsa (A, B’nin önkoşulu ve B, A’nın) geçerli bir sıra yoktur.

Örnek DAG, kenarlar 4→2, 4→0, 6→0, 6→5, 2→1, 0→1, 0→3, 5→3:

4 ---> 2 ---> 1
 \            ^
  v           |
   0 ---------+
  ^ \
 /   v
6     3
 \    ^
  v   |
   5 -+

Kahn algoritması (giriş derecesi ile)

1. Her köşenin giriş derecesini (in-degree) hesapla.
2. Derecesi 0 olanları kuyruğa koy.
3. Kuyruktan çıkar, çıktıya yaz. Komşularının derecesini 1 azalt; 0’a düşeni kuyruğa ekle.

in-degree: 0:2 1:2 2:1 3:2 4:0 5:1 6:0
kuyruk [4, 6]
çık 4 -> 2 serbest        [6, 2]
çık 6 -> 0, 5 serbest     [2, 0, 5]
çık 2 -> (1 hâlâ 1)       [0, 5]
çık 0 -> 1 serbest        [5, 1]
çık 5 -> 3 serbest        [1, 3]
çık 1, çık 3
sıra: 4 6 2 0 5 1 3

Kuyruk yerine min-heap kullanıp her seferinde en küçük etiketi seçersen sıra 4 2 6 0 1 5 3 olur. İkisi de geçerli: topolojik sıra genelde tek değildir, sorudaki kural belirler.

Döngü tespiti bedava gelir: Kahn bittiğinde çıktıda V’den az köşe varsa grafta döngü vardır, çünkü döngüdeki köşelerin derecesi hiç 0’a düşmez. Kenarları 0→1, 1→2, 2→0, 2→3 olan grafta hiçbir köşenin giriş derecesi 0 değil; çıktı 0 köşe.

DFS ile topolojik sıra

DFS’te bir köşe bütün torunları bittikten sonra biter. O yüzden u→v kenarında v, u’dan önce biter. Bitiş sırasını ters çevirince topolojik sıra çıkar.

dfs(0): 1 biter, 3 biter, 0 biter
dfs(2): 2 biter        dfs(4): 4 biter
dfs(5): 5 biter        dfs(6): 6 biter
bitiş:  1 3 0 2 4 5 6
ters:   6 5 4 2 0 3 1

Kontrol: 6→0 (6 önce), 4→2, 2→1, 0→3, 5→3: hepsi doğru yönde. İki algoritma da $O(V + E)$.

Sık yapılan hatalar

static int countComponents(List<List<Integer>> adj) {
    int n = adj.size(), count = 0;
    boolean[] visited = new boolean[n];
    for (int v = 0; v < n; v++) {
        if (!visited[v]) {
            count++;
            dfs(adj, v, visited);
        }
    }
    return count;
}

static void dfs(List<List<Integer>> adj, int v, boolean[] visited) {
    visited[v] = true;
    for (int w : adj.get(v))
        if (!visited[w]) dfs(adj, w, visited);
}