Графи — обхождане (BFS и DFS)

Имайки граф, често искаме да отговорим на въпроси като:

• До кои върхове мога да стигна, ако тръгна от връх X?
• Кой е най-късият път (брой стъпки) от A до B?
• Колко „групи приятели" има (свързани компоненти)?
• Има ли цикъл в графа?

Всички тези въпроси се решават с обхождане на графа — систематично посещение на върховете. Има два класически алгоритъма: BFS и DFS.

И при двата алгоритъма ни трябва множество visited, в което пазим вече посетените върхове. Без него ще обикаляме безкрайно в кръг (при графи с цикли).

var visited = new HashSet<int>();
// преди да посетим връх:
if (visited.Contains(v)) continue;
visited.Add(v);
// ... обработваме v

BFS (обхождане в ширина) посещава върховете „пласт по пласт" — първо стартовия връх, после всичките му съседи, после техните съседи и т.н. Идеално за намиране на най-къс път в нетегловен граф (по брой стъпки).

Реализира се с опашка (Queue) — точно затова в предишния урок казахме „опашката е важна за обхождане в ширина".

using System.Collections.Generic;

static void BFS(
    Dictionary<int, HashSet<int>> graph,
    int start)
{
    var visited = new HashSet<int> { start };
    var queue = new Queue<int>();
    queue.Enqueue(start);

    while (queue.Count > 0)
    {
        int v = queue.Dequeue();
        Console.Write(v + " ");

        foreach (var neighbor in graph[v])
        {
            if (!visited.Contains(neighbor))
            {
                visited.Add(neighbor);
                queue.Enqueue(neighbor);
            }
        }
    }
}

static int ShortestPath(
    Dictionary<int, HashSet<int>> graph,
    int from, int to)
{
    if (from == to) return 0;
    var distance = new Dictionary<int, int> { [from] = 0 };
    var queue = new Queue<int>();
    queue.Enqueue(from);

    while (queue.Count > 0)
    {
        int v = queue.Dequeue();
        foreach (var n in graph[v])
        {
            if (distance.ContainsKey(n)) continue;
            distance[n] = distance[v] + 1;
            if (n == to) return distance[n];
            queue.Enqueue(n);
        }
    }
    return -1;   // няма път
}

DFS (обхождане в дълбочина) тръгва от стартовия връх и върви „навътре", докато може. Когато стигне до връх без непосетени съседи — връща се назад и опитва друг път.

Реализира се с стек (Stack) — или още по-естествено, с рекурсия (която ползва стека на извикванията).

static void DFS(
    Dictionary<int, HashSet<int>> graph,
    int v,
    HashSet<int> visited)
{
    if (visited.Contains(v)) return;
    visited.Add(v);
    Console.Write(v + " ");

    foreach (var neighbor in graph[v])
        DFS(graph, neighbor, visited);
}

// Извикване:
DFS(graph, 1, new HashSet<int>());

static void DFSIter(
    Dictionary<int, HashSet<int>> graph,
    int start)
{
    var visited = new HashSet<int>();
    var stack = new Stack<int>();
    stack.Push(start);

    while (stack.Count > 0)
    {
        int v = stack.Pop();
        if (visited.Contains(v)) continue;
        visited.Add(v);
        Console.Write(v + " ");

        foreach (var n in graph[v])
            if (!visited.Contains(n))
                stack.Push(n);
    }
}

Най-нагледното приложение на BFS: намери най-краткия път през лабиринт. Решетката е граф — всяка свободна клетка е връх, а съседните свободни клетки (горе/долу/ляво/дясно) са свързани с ребро.

Не строим граф изрично — ползваме координатите (ред, колона) направо. Съседите се намират чрез четирите посоки:

static int MazeShortestPath(string[] maze)
{
    int rows = maze.Length, cols = maze[0].Length;
    // намери S и E
    (int r, int c) start = (0, 0), end = (0, 0);
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
        {
            if (maze[r][c] == 'S') start = (r, c);
            if (maze[r][c] == 'E') end = (r, c);
        }

    var queue = new Queue<(int r, int c, int dist)>();
    var visited = new HashSet<(int, int)> { start };
    queue.Enqueue((start.r, start.c, 0));

    int[] dr = { -1, 1, 0, 0 };   // горе, долу
    int[] dc = { 0, 0, -1, 1 };   // ляво, дясно

    while (queue.Count > 0)
    {
        var (r, c, dist) = queue.Dequeue();
        if ((r, c) == end) return dist;

        for (int k = 0; k < 4; k++)
        {
            int nr = r + dr[k], nc = c + dc[k];
            // в границите? не е стена? непосетен?
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
            if (maze[nr][nc] == '#') continue;
            if (visited.Contains((nr, nc))) continue;

            visited.Add((nr, nc));
            queue.Enqueue((nr, nc, dist + 1));
        }
    }
    return -1;   // няма път
}

Граф има цикъл, ако по време на DFS стигнем до връх, който вече е посетен — и той не е родителят, от който току-що дойдохме.

static bool HasCycle(
    Dictionary<int, HashSet<int>> graph,
    int v, int parent,
    HashSet<int> visited)
{
    visited.Add(v);
    foreach (var n in graph[v])
    {
        if (!visited.Contains(n))
        {
            if (HasCycle(graph, n, v, visited)) return true;
        }
        else if (n != parent)
        {
            return true;   // стигнахме до посетен връх, който не е родителят → цикъл
        }
    }
    return false;
}

// За несвързан граф — проверяваме от всеки непосетен връх.

Свързан компонент е максимална група върхове, между които има пътища. Например в граф „приятелства" — различни групи ученици, които не се познават помежду си.

Алгоритъм: за всеки непосетен връх → стартирай BFS/DFS от него → всичко, до което стигне = един компонент → повтори.

static List<List<int>> ConnectedComponents(
    Dictionary<int, HashSet<int>> graph)
{
    var components = new List<List<int>>();
    var visited = new HashSet<int>();

    foreach (var start in graph.Keys)
    {
        if (visited.Contains(start)) continue;

        // BFS от start, събираме всичко в текущия компонент
        var component = new List<int>();
        var queue = new Queue<int>();
        queue.Enqueue(start);
        visited.Add(start);
        while (queue.Count > 0)
        {
            int v = queue.Dequeue();
            component.Add(v);
            foreach (var n in graph[v])
                if (!visited.Contains(n))
                {
                    visited.Add(n);
                    queue.Enqueue(n);
                }
        }
        components.Add(component);
    }
    return components;
}

• Без visited — алгоритъмът цикли безкрайно при цикличен граф. Винаги имай HashSet<int> visited.
• Маркиране в грешния момент — при BFS маркирай върха когато го добавиш в опашката, не когато го извадиш. Иначе може да го сложиш няколко пъти и да го броиш многократно.
• BFS за най-къс път, но в тегловен граф — не работи! BFS брои стъпки, не теглá. За тегловен граф трябва Dijkstra (по-сложен алгоритъм).
• Дълбока рекурсивна DFS на голям граф — рискуваш StackOverflowException. За > 10 000 върха ползвай итеративен вариант със собствен Stack.

• BFS = ширина = Queue = намира най-къс път (по брой стъпки).
• DFS = дълбочина = Stack или рекурсия = удобно за откриване на цикли и компоненти.
• И двата алгоритъма са почти едни и същи — единствената разлика е дали ползваш Queue или Stack.
• Винаги пази HashSet<int> visited.
• Свързани компоненти = повтаряй BFS/DFS от всеки непосетен връх.