Graph Temelleri: Adjacency List, BFS ve DFS ile Gezinmek

Sürüm notu: Bu yazıdaki kodlar .NET 10 ve C# 14 ile derlenip xUnit v3 4.0.2 testleriyle doğrulanmıştır; ölçümler BenchmarkDotNet 0.15.8 ile alınmıştır.

Önce Tahmin Et

Bookstore'un okur topluluğunda kullanıcılar birbirini takip ediyor. Kampanya için uç bir test: 2.000 kullanıcının hepsi birbirini takip ediyor. Kullanıcı 0'dan başlayıp herkese kaç adımda ulaşıldığını BFS (Breadth-First Search) ile hesaplıyoruz. İki implementasyon var; tek farkları bir node'u "ziyaret edildi" diye ne zaman işaretledikleri:

long ListBfs(Graph<int> graph, bool markOnEnqueue)
{
    HashSet<int> visited = [];
    Queue<int> queue = new();
    queue.Enqueue(0);
    if (markOnEnqueue) visited.Add(0);
    long enqueues = 1;
    while (queue.Count > 0)
    {
        int v = queue.Dequeue();
        if (!markOnEnqueue && !visited.Add(v)) continue; // queue'dan çıkarken işaretle
        foreach (int next in graph.Neighbors(v))
        {
            if (visited.Contains(next)) continue;
            if (markOnEnqueue) visited.Add(next);            // queue'ya eklerken işaretle
            queue.Enqueue(next);
            enqueues++;
        }
    }

    return enqueues;
}

İkisi de doğru sonucu verir. Peki queue'ya toplam kaç kez eleman eklenir? İlki için cevap açık: her kullanıcı bir kez, 2.000. İkincisi için tahminin ne? 4.000 mü, 20.000 mi, yoksa çok daha fazla mı?

Graph Kavramları

Graph, vertex'ler (node) ve onları bağlayan edge'lerden oluşur. Tree'nin aksine bir vertex'in birden fazla "parent"ı olabilir, döngüler (cycle) olabilir ve graph birbirine bağlı olmayan parçalardan oluşabilir. Üç soru graph'ın türünü belirler. Edge'in yönü var mı? Takip ilişkisi directed'dır (Ada, Alan'ı takip ediyor olabilir ama tersi geçerli olmayabilir), iki şehir arasındaki karayolu undirected. Edge'in ağırlığı var mı? Takipte yok, yolda mesafe ya da maliyet var. Cycle var mı? Bağımlılık graph'larında cycle bir hatadır, sosyal graph'ta normaldir.

Bu yazıda ağırlıksız graph'larla çalışıyoruz: BFS ile en az adım, DFS (Depth-First Search) ile derinlemesine gezinme ve connected component'ler. Ağırlıklı en kısa yol serinin 17. yazısının, cycle'ların hata olduğu bağımlılık sırası 16. yazının konusu.

Adjacency List ve Adjacency Matrix

Graph'ı bellekte tutmanın iki klasik yolu var. Adjacency list'te her vertex komşularının listesini tutar:

public sealed class Graph<T> where T : notnull
{
    private readonly Dictionary<T, List<T>> _adjacency = [];

    public Graph(bool directed) => Directed = directed;

    public bool Directed { get; }
    public int VertexCount => _adjacency.Count;
    public int EdgeCount { get; private set; }
    public IEnumerable<T> Vertices => _adjacency.Keys;

    public void AddVertex(T vertex) => _adjacency.TryAdd(vertex, []);

    public void AddEdge(T from, T to)
    {
        AddVertex(from);
        AddVertex(to);
        _adjacency[from].Add(to);
        if (!Directed)
        {
            _adjacency[to].Add(from); // undirected: iki yönde de komşu
        }

        EdgeCount++;
    }

    public IReadOnlyList<T> Neighbors(T vertex) =>
        _adjacency.TryGetValue(vertex, out List<T>? list) ? list : [];
}

Adjacency matrix'te ise V × V boyutunda bir bool[,] vardır ve matrix[u, v] "u'dan v'ye edge var mı" sorusunu tek adımda cevaplar. Seçim graph'ın yoğunluğuna bağlı:

Gerçek hayattaki graph'ların neredeyse hepsi seyrektir: bir kullanıcı milyonlarca kişiden birkaç yüzünü takip eder. 10.000 vertex'lik bir matrix, edge sayısı ne olursa olsun yer kaplar:

adjacency matrix bool[10000,10000]: 95.4 MB regardless of edge count

Generic T ile Dictionary kullanmak, vertex'lerin string kullanıcı adı ya da Guid olabilmesini sağlar. Performans kritikse vertex'leri 0..V-1 arası int id'lere eşleyip List<int>[] ve bool[] visited kullanmak hash maliyetini ortadan kaldırır; bu "id mapping" büyük graph kütüphanelerinin standart hilesidir.

BFS: En Az Adım

BFS, başlangıçtan katman katman yayılır: önce 1 adım uzaktakiler, sonra 2 adım uzaktakiler. Bunu bir queue sağlar; queue'ya önce giren önce işlenir, bu yüzden bir vertex'e ilk ulaştığımız an en kısa yoldan ulaşmış oluruz (ağırlıksız graph'ta):

public static Dictionary<T, int> Distances<T>(Graph<T> graph, T start) where T : notnull
{
    Dictionary<T, int> distance = new() { [start] = 0 };
    Queue<T> queue = new();
    queue.Enqueue(start);
    while (queue.Count > 0)
    {
        T current = queue.Dequeue();
        foreach (T next in graph.Neighbors(current))
        {
            // Queue'ya eklerken işaretlenir: hiçbir vertex queue'ya iki kez girmez
            if (distance.TryAdd(next, distance[current] + 1))
            {
                queue.Enqueue(next);
            }
        }
    }

    return distance;
}

distance dictionary'si hem "ziyaret edildi" kümesi hem de cevap. Takip graph'ımız:

Graph<string> follows = new(directed: true);
follows.AddEdge("ada", "alan");
follows.AddEdge("ada", "grace");
follows.AddEdge("alan", "edsger");
follows.AddEdge("grace", "edsger");
follows.AddEdge("edsger", "barbara");
follows.AddEdge("barbara", "ada");
follows.AddVertex("linus");

foreach ((string user, int hops) in GraphTraversal.Distances(follows, "ada"))
{
    Console.WriteLine($"{user,-8} {hops}");
}

ada      0
alan     1
grace    1
edsger   2
barbara  3

Linus listede yok, çünkü Ada'dan ona giden bir yol yok. "Edsger'e iki yoldan ulaşılıyor" bilgisi de kayboldu; BFS her vertex'i ilk ulaştığı yerden sayar. Yolun kendisini istiyorsak her vertex'e nereden geldiğimizi (parent) saklarız ve hedeften geriye yürürüz:

public static List<T>? ShortestPath<T>(Graph<T> graph, T start, T target) where T : notnull
{
    Dictionary<T, T> parent = [];
    HashSet<T> visited = [start];
    Queue<T> queue = new();
    queue.Enqueue(start);
    while (queue.Count > 0)
    {
        T current = queue.Dequeue();
        if (EqualityComparer<T>.Default.Equals(current, target))
        {
            List<T> path = [current];
            while (parent.TryGetValue(path[^1], out T? p)) path.Add(p);
            path.Reverse();
            return path;
        }

        foreach (T next in graph.Neighbors(current))
        {
            if (visited.Add(next))
            {
                parent[next] = current;
                queue.Enqueue(next);
            }
        }
    }

    return null;
}

grace -> edsger -> barbara -> ada -> alan

Grace, Alan'ı doğrudan takip etmiyor ve graph directed olduğu için Alan'dan Grace'e bakan edge'i geriye kullanamıyor; dört adımlık yol en kısası. Maliyet O(V + E): her vertex queue'ya bir kez girer, her edge bir kez incelenir. Bunun nasıl çıkarıldığı Big-O ve Complexity serisinin "Koddan Time Complexity Çıkarmak" yazısında.

DFS: Recursive ve Iterative

DFS bir yolu sonuna kadar takip eder, çıkmaza girince geri döner. Recursive yazımı çok doğal:

public static List<T> DepthFirstRecursive<T>(Graph<T> graph, T start) where T : notnull
{
    List<T> order = [];
    HashSet<T> visited = [];
    Visit(start);
    return order;

    void Visit(T vertex)
    {
        if (!visited.Add(vertex))
        {
            return;
        }

        order.Add(vertex);
        foreach (T next in graph.Neighbors(vertex))
        {
            Visit(next);
        }
    }
}

Ama recursion derinliği en uzun yol kadar olabilir; 100.000 vertex'lik bir zincirde StackOverflowException process'i öldürür (serinin 5. yazısı). Iterative versiyon call stack yerine explicit bir Stack<T> kullanır. Komşuları ters sırayla push edersek, recursive versiyonla aynı sırayı elde ederiz:

public static List<T> DepthFirstIterative<T>(Graph<T> graph, T start) where T : notnull
{
    List<T> order = [];
    HashSet<T> visited = [];
    Stack<T> stack = new();
    stack.Push(start);
    while (stack.Count > 0)
    {
        T vertex = stack.Pop();
        if (!visited.Add(vertex))
        {
            continue; // stack'te birden fazla kopyası olabilir
        }

        order.Add(vertex);
        IReadOnlyList<T> neighbors = graph.Neighbors(vertex);
        for (int i = neighbors.Count - 1; i >= 0; i--)
        {
            if (!visited.Contains(neighbors[i]))
            {
                stack.Push(neighbors[i]);
            }
        }
    }

    return order;
}

DFS: ada, alan, edsger, barbara, grace

BFS'te Grace ikinci sırada (1 adım) gelirken DFS'te en sonda: önce Alan'dan Edsger'e, oradan Barbara'ya kadar inip geri dönüyor. Buradaki bir incelik: DFS'te vertex'i stack'ten çıkarırken işaretliyoruz, BFS'te queue'ya eklerken. DFS'te sıranın recursive versiyonla aynı kalması için bu gerekli; bedeli, aynı vertex'in stack'te birden fazla kopyasının olabilmesi. Testte iki versiyonun aynı sırayı ürettiğini doğruluyoruz.

Connected Component'ler

Undirected bir graph'ta birbirine yolla bağlı vertex grupları connected component'tir. Henüz görülmemiş her vertex'ten bir BFS başlatırsak, her BFS bir component'i bulur:

public static List<List<T>> ConnectedComponents<T>(Graph<T> graph) where T : notnull
{
    List<List<T>> components = [];
    HashSet<T> seen = [];
    foreach (T vertex in graph.Vertices)
    {
        if (seen.Contains(vertex))
        {
            continue;
        }

        List<T> component = [.. Distances(graph, vertex).Keys];
        seen.UnionWith(component);
        components.Add(component);
    }

    return components;
}

Toplam maliyet yine O(V + E), çünkü her vertex tek bir BFS'e girer. Bookstore'da bu, "birlikte satın alınan kitaplar" graph'ında birbirinden kopuk okur gruplarını bulmak ya da bir veri göçünden önce tablolar arası ilişki graph'ında bağımsız parçaları ayırmak için kullanılabilir. Serinin 18. yazısında aynı soruyu, edge'ler tek tek gelirken cevaplayan Union-Find'ı göreceğiz.

Grid'i Implicit Graph Olarak Görmek

Her graph'ı açıkça kurmak gerekmez. Depo kat planı gibi bir grid'de her hücre bir vertex'tir ve komşuları dört yöndeki hücrelerdir; komşuluk listesini saklamak yerine hesaplarız. Klasik "ada sayma" problemi (raf bloklarını say) bir flood fill'dir:

private static readonly (int Dr, int Dc)[] Directions = [(-1, 0), (1, 0), (0, -1), (0, 1)];

public static int CountIslands(string[] map)
{
    int rows = map.Length, cols = map[0].Length, islands = 0;
    bool[,] visited = new bool[rows, cols];
    for (int r = 0; r < rows; r++)
    {
        for (int c = 0; c < cols; c++)
        {
            if (map[r][c] == '#' && !visited[r, c])
            {
                islands++;
                Fill(map, visited, r, c);
            }
        }
    }

    return islands;
}

public static int Fill(string[] map, bool[,] visited, int startRow, int startCol)
{
    char target = map[startRow][startCol];
    Queue<(int R, int C)> queue = new();
    queue.Enqueue((startRow, startCol));
    visited[startRow, startCol] = true;
    int size = 0;
    while (queue.Count > 0)
    {
        (int r, int c) = queue.Dequeue();
        size++;
        foreach ((int dr, int dc) in Directions)
        {
            int nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < map.Length && nc >= 0 && nc < map[0].Length
                && !visited[nr, nc] && map[nr][nc] == target)
            {
                visited[nr, nc] = true;
                queue.Enqueue((nr, nc));
            }
        }
    }

    return size;
}

[Fact]
public void CountIslands_CountsConnectedLandCells()
{
    string[] map =
    [
        "##..#",
        "#...#",
        "..#..",
        ".....",
        "##.##",
    ];
    Assert.Equal(5, GridGraph.CountIslands(map));
}

Test run summary: Passed!
  total: 5
  failed: 0
  succeeded: 5
  skipped: 0
  duration: 430ms

Grid'de HashSet yerine bool[,] visited kullanmak hem hızlı hem bellek dostu. Flood fill'i bilinçli olarak BFS ile yazdık: recursive DFS ile yazılmış bir flood fill, 1000 × 1000'lik tek parça bir alanda bir milyon frame derinliğe iner ve process'i çökertir.

Ölçüm: List ve Matrix ile BFS

5.000 vertex'lik seyrek bir graph kurdum (bir halka artı her vertex'ten iki rastgele edge, yaklaşık 15.000 edge) ve aynı BFS'i iki gösterimle çalıştırdım. Matrix versiyonu her vertex için satırın tamamını tarıyor:

[Benchmark]
public int AdjacencyMatrix()
{
    bool[] seen = new bool[V];
    Queue<int> queue = new();
    queue.Enqueue(0);
    seen[0] = true;
    int count = 0;
    while (queue.Count > 0)
    {
        int v = queue.Dequeue();
        count++;
        for (int u = 0; u < V; u++) // matrix bütün satırı taramak zorunda
        {
            if (_matrix[v, u] && !seen[u])
            {
                seen[u] = true;
                queue.Enqueue(u);
            }
        }
    }

    return count;
}

Ölçümler Apple M5 (10 çekirdek), macOS 27.0.1, .NET 10.0.13, BenchmarkDotNet 0.15.8 ile alındı. Benchmark'ları tek tek çalıştırdım ama makinede paralel işler vardı; mutlak sayılara değil oranlara bak.

| Method          | V    | Mean        | Ratio | Allocated |
|---------------- |----- |------------:|------:|----------:|
| AdjacencyList   | 5000 |    309.1 us |  1.00 | 542.67 KB |
| AdjacencyMatrix | 5000 | 14,364.1 us | 46.52 |  37.19 KB |

Matrix 46 kat yavaş: 5.000 × 5.000 = 25 milyon hücreye bakıyor, list ise yalnız gerçekten var olan yaklaşık 30.000 komşuluk kaydına (undirected, iki yön). List versiyonunun daha çok allocation yapması Distances'ın cevabı bir Dictionary içinde döndürmesinden; matrix'in kendisi ise ölçümün dışında 24 MB'lık bir array olarak bellekte duruyor.

Üretimde Dikkat

Graph veritabanında duruyorsa onu belleğe çekmeden önce düşün. "Bu kategorinin bütün alt kategorileri" gibi sorgular SQL'de (Structured Query Language) recursive CTE (Common Table Expression) ile veritabanında BFS'e benzer biçimde çalışır; EF (Entity Framework) Core ile bunu nasıl yazacağını EF Core serisinde gördük. Milyonlarca edge'lik bir takip graph'ını her request'te belleğe yüklemek ise hem yavaş hem pahalı.

Uçtan uca "kaç adım uzakta" soruları sosyal graph'ta hızla patlar: ortalama 200 takipli bir graph'ta 3 adım uzaklık 200³ = 8 milyon vertex'e kadar dokunabilir. Bidirectional BFS (iki uçtan aynı anda başlayıp ortada buluşmak) ya da derinliği sınırlamak (örneğin en fazla 3 adım) pratikte zorunludur. Graph'ın kendisi çok büyükse ve sorgular hep ilişki üzerineyse, ilişki odaklı bir graph veritabanı da değerlendirilebilir.

Traversal sırasında graph'ı değiştirme. BFS çalışırken başka bir thread takip ekleyip çıkarırsa List<T> enumerator'ı exception fırlatır ya da tutarsız sonuç verir. Ya graph'ın değişmez bir snapshot'ı üzerinde gez, ya da okuma ve yazmayı senkronize et.

Recursion ve kullanıcı verisi. Graph'ın şeklini kullanıcı belirliyorsa (iç içe kategoriler, yorum zincirleri), recursive DFS bir saldırganın tek bir uzun zincirle process'i çökertmesine izin verir. Iterative yaz ya da derinlik sınırı koy.

Sık Düşülen Tuzaklar

Visited'ı queue'ya eklerken değil çıkarırken işaretlemek. Açılıştaki sorunun cevabı, aynı karşılaştırmanın grid üzerindeki versiyonuyla birlikte:

10x10 grid: mark on enqueue = 100 enqueues, mark on dequeue = 181 enqueues
100x100 grid: mark on enqueue = 10,000 enqueues, mark on dequeue = 19,801 enqueues
300x300 grid: mark on enqueue = 90,000 enqueues, mark on dequeue = 179,401 enqueues
complete graph, 2,000 users: mark on enqueue = 2,000 enqueues, mark on dequeue = 1,999,001 enqueues

Çıkarırken işaretlenince bir vertex, henüz işlenmediği için, ona komşu olan her vertex tarafından tekrar tekrar queue'ya eklenir. Grid'de bu iki kat iş, herkesin herkesi takip ettiği graph'ta ise 2.000 yerine yaklaşık 2 milyon ekleme: O(V) yerine O(E). Sonuç yine doğru çıktığı için bu hata testlerden geçer ve yalnız büyük veride bellek ve süre olarak ortaya çıkar. BFS'te kural: queue'ya eklerken işaretle.

Undirected edge'i tek yönlü eklemek. İki şehir arasındaki yolu yalnız adjacency[a].Add(b) ile eklersen b'den a'ya gidilemez ve BFS bazı vertex'leri "ulaşılamaz" sanır. AddEdge gibi tek bir method ve Directed bayrağı bu hatayı merkezileştirir.

Ulaşılamayan vertex'i unutmak. Distances yalnız ulaşılan vertex'leri döndürür; distance["linus"] KeyNotFoundException fırlatır. Çağıran kod TryGetValue kullanmalı ya da "sonsuz" için açık bir değer üretilmeli.

BFS'i ağırlıklı graph'ta kullanmak. BFS en az edge sayısını bulur, en düşük toplam maliyeti değil. Kargo maliyetleri farklıysa Dijkstra gerekir; serinin 17. yazısı.

Küçük Bir Deneme

★☆☆ Distances'ı bir maxDepth parametresi alacak şekilde değiştir ve "Ada'nın en fazla 2 adım uzağındaki kullanıcılar" listesini üret. Takip graph'ında Barbara listede olmamalı.

★★☆ Bidirectional BFS yaz: başlangıçtan ve hedeften aynı anda birer BFS başlat, her adımda küçük olan frontier'ı genişlet, iki taraf buluşunca dur. Rastgele, ortalama 50 komşulu 100.000 vertex'lik bir graph'ta incelenen vertex sayısını tek yönlü BFS ile karşılaştır.

★★★ Grid flood fill'i recursive DFS ile yaz ve 2000 × 2000'lik tek parça bir alanda çalıştır. Process'in nasıl sonlandığını gözle, sonra aynı işi new Thread(..., maxStackSize) ile büyük stack'li bir thread'de dene ve neden bunun bir çözüm değil bir erteleme olduğunu not et.

BFS ve DFS ile graph'ı gezmeyi öğrendik. Bir sonraki yazıda directed graph'larda cycle'ın hata olduğu bir probleme bakıyoruz: solution'daki project'leri hangi sırayla build etmeli, seed data'yı foreign key'lere göre hangi sırayla eklemeli? Cevap topological sort ve Kahn algoritması.