(C#) DFS

📌DFS 깊이 우선 탐색

그래프/트리 탐색 기법중 하나이다.
한 정점(Vertext)에서 연결되어있는 다른 정점으로 갈 때 한 분기의 가장 깊숙한 곳 까지 탐색하고 다시 돌아와 다른 분기를 탐색하는 기법이다.

 

특징

• 자기 자신을 호출하는 순환 알고리즘 형태를 가지고 있다.
• 어떤 노드를 탐색했는지 검사를 반드시 해야한다.
  • 하지 않았을 때 무한 루프에 빠질 수 있다.

 

구현 코드

class Graph
{
    private int _nodeCount;
    private List<int>[] _adj;

    public Graph(int nodeCount)
    {
        _nodeCount = nodeCount;
        _adj = new List<int>[nodeCount];
        for (int i = 0; i < nodeCount; i++)
            _adj[i] = new List<int>();
    }

    public void AddEdge(int v, int edge)
    {
        _adj[v].Add(edge);
    }

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

    private void DFSUtil(int v, bool[] visited)
    {
        visited[v] = true;
        List<int> nodes = _adj[v];
        foreach (int i in nodes)
            if (!visited[i])
                DFSUtil(i, visited);
    }
}

 

 

위 그림과 같은 구조를 가지는 그래프에서 DFS를 구현하면 다음과 같이 된다.

 

static void Main()
{
    Graph graph = new Graph(6);

    graph.AddEdge(0, 1);
    graph.AddEdge(0, 3);
    graph.AddEdge(1, 0);
    graph.AddEdge(1, 2);
    graph.AddEdge(1, 3);
    graph.AddEdge(2, 1);
    graph.AddEdge(2, 4);
    graph.AddEdge(3, 0);
    graph.AddEdge(3, 1);
    graph.AddEdge(3, 5);
    graph.AddEdge(4, 2);
    graph.AddEdge(5, 3);
}

 

그리고 DFS 시작을 0번 정점부터 한다고 하면 

graph.DFS(0);

 

다음과 같은 순서로 진행이 된다.