⚙️ Погружение в Глубину

Алгоритм поиска в глубину (DFS) является одним из фундаментальных методов обхода графов. Он используется для решения множества задач, таких как поиск пути, обнаружение циклов и топологическая сортировка.

➖ Что такое DFS

DFS (Depth-First Search) — это алгоритм обхода графа, который начинает с начальной вершины и исследует как можно глубже вдоль каждого ветви, прежде чем возвращаться назад.

Алгоритм использует стек для отслеживания посещенных вершин. В рекурсивной реализации стек заменяется стеком вызовов функции.

Основные Шаги DFS

1️⃣ Начинаем с начальной вершины.

2️⃣ Помечаем текущую вершину как посещенную.

3️⃣ Исследуем все смежные вершины, которые еще не были посещены.

4️⃣ Повторяем процесс для каждой смежной вершины.

5️⃣ Если все смежные вершины посещены, возвращаемся назад.

Реализация DFS в C#:

class Graph {
    private int V;
    private List<int>[] adj;

    public Graph(int v) {
        V = v;
        adj = new List<int>[v];
        for (int i = 0; i < v; i++) 
            adj[i] = new List<int>();
    }

    public void AddEdge(int v, int w) {
        adj[v].Add(w);
    }

    public void DFS(int start) {
        bool[] visited = new bool[V];
        DFSUtil(start, visited);
    }

    private void DFSUtil(int v, bool[] visited) {
        visited[v] = true;
        Console.Write(v + " ");

        foreach (int n in adj[v]) {
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }
}

🐸Библиотека шарписта