C# DFS (깊이 우선 탐색) 알고리즘 예시 간단 구현

DFS 알고리즘

DFS는 그래프나 트리의 탐색 방법 중 하나로, 가능한 한 깊이 들어가서 노드를 탐색합니다.
시작 노드에서 다음 노드로 진행하고, 더 이상 진행할 수 없을 때 백트래킹(backtracking)하여 다른 경로를 탐색합니다.
스택(Stack) 자료구조 또는 재귀 함수를 사용하여 구현합니다.
DFS는 미로 찾기, 그래프 순회, 연결 요소 찾기 등 다양한 문제에 사용됩니다.

 

• 코드 예시

using System;
using System.Collections.Generic;

class Graph
{
    private int V; // 그래프의 노드(정점) 수
    private List<int>[] adjacencyList; // 그래프의 인접 리스트

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

    // 그래프에 간선을 추가합니다.
    public void AddEdge(int v, int w)
    {
        adjacencyList[v].Add(w);
    }

    // DFS로 그래프를 탐색하고 결과를 출력합니다.
    public void DFS(int startNode)
    {
        // 방문한 노드를 추적하기 위한 배열
        bool[] visited = new bool[V];

        // 시작 노드에서 DFS 탐색 시작
        DFSUtil(startNode, visited);
    }

    private void DFSUtil(int node, bool[] visited)
    {
        // 현재 노드를 방문한 것으로 표시하고 출력
        visited[node] = true;
        Console.Write(node + " ");

        // 현재 노드와 연결된 방문하지 않은 노드를 재귀적으로 탐색
        foreach (int adjacentNode in adjacencyList[node])
        {
            if (!visited[adjacentNode])
            {
                DFSUtil(adjacentNode, visited);
            }
        }
    }
}

class Program
{
    static void Main()
    {
        Graph graph = new Graph(7);
        graph.AddEdge(0, 1);
        graph.AddEdge(0, 2);
        graph.AddEdge(1, 3);
        graph.AddEdge(1, 4);
        graph.AddEdge(2, 5);
        graph.AddEdge(2, 6);

        Console.WriteLine("DFS 탐색 결과 (시작 노드: 0):");
        graph.DFS(0);
    }
}