[알고리즘] 깊이 우선 탐색, DFS(Deep-First Search) 코드 구현

깊이 우선 탐색에 대한 개념은 아래의 포스팅을 참조하면 된다.

[알고리즘] 깊이 우선 탐색 (DFS, Depth-First Search)

 

깊이 우선 탐색을 코드로 구현하는 방법은 2가지로 반복 구현, 재귀 구현이 있다.

 

C#코드를 통해 DFS를 구현해 보겠다.

그래프 예시

---

반복구현

반복 구현은 Stack을 이용한 구현 방법으로, 한 정점을 방문하면 인접한 정점들을 모두 Stack에 담고 Stack에서 하나씩 꺼내 인접한 노드를 Stack에 담으면서 Stack에 담긴 모든 노드를 방문할때 까지 반복하는 방법으로 구현한다.

// 인접 리스트를 이용한 방향성 있는 그래프
class Graph
{
    private int vertex; // 정점
    private List<int>[] adj; // adjacency, 그래프의 인접 목록

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

    // 간선 추가 (v → w)
    public void addEdge(int v, int w)
    {
        adj[v].Add(w);
    }

    // DFS에 사용되는 함수
    public void DFSUtill(int v, bool[] visited)
    {
        // 스택 생성
        Stack<int> stack = new Stack<int>();
        stack.Push(v);

        while(stack.Count > 0)
        {
            int vt = stack.Pop();

            // 방문 하고 출력
            visited[vt] = true;
            Console.Write(vt + " ");

            // 인접 노드 담기
            foreach(int neighbor in adj[vt])
            {
                if (!visited[neighbor])
                    stack.Push(neighbor);
            }
        }

    }

    // DFS 탐색
    public void DFS()
    {
        bool[] visited = new bool[vertex];

        // 모든 정점을 하나씩 방문
        for (int i = 0; i < vertex; i++)
        {
            if (!visited[i])
                DFSUtill(i, visited);
        }
    }

    // 시작점v에서 DFS 탐색
    public void DFS(int v)
    {
        // 노드 방문 여부
        bool[] visited = new bool[vertex];

        DFSUtill(v, visited);
    }

}

static void Main(string[] args)
{
    Graph g = new Graph(12);

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(0, 3);
    g.addEdge(1, 4);
    g.addEdge(1, 5);
    g.addEdge(2, 6);
    g.addEdge(3, 7);
    g.addEdge(3, 8);
    g.addEdge(4, 9);
    g.addEdge(6, 10);
    g.addEdge(8, 11);

    g.DFS(3); // 3 8 11 7

    g.DFS(); // 0 3 8 11 7 2 6 10 1 5 4 9
}

---

재귀구현

재귀 구현은 재귀 함수를 이용한 구현법으로, 현재 정점에서 인접한 정점들 중 방문하지 않은 정점들을 DFS함수를 적용한다. 재귀 귀현은 모든 노드를 방문할 때 유리한 구현법이다.

// 인접 리스트를 이용한 방향성 있는 그래프
class Graph
{
    private int vertex; // 정점
    private List<int>[] adj; // adjacency, 그래프의 인접 목록

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

    // 간선 추가 (v → w)
    public void addEdge(int v, int w)
    {
        adj[v].Add(w);
    }

    // DFS에 사용되는 함수
    public void DFSUtill(int v, bool[] visited)
    {
        // 방문 하고 출력
        visited[v] = true;
        Console.Write(v + " ");

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

    // DFS 탐색
    public void DFS()
    {
        bool[] visited = new bool[vertex];

        // 모든 정점을 하나씩 방문
        for (int i = 0; i < vertex; i++)
        {
            if (!visited[i])
                DFSUtill(i, visited);
        }
    }

    // 시작점v에서 DFS 탐색
    public void DFS(int v)
    {
        // 노드 방문 여부
        bool[] visited = new bool[vertex];

        DFSUtill(v, visited);
    }
}

static void Main(string[] args)
{
    Graph g = new Graph(12);

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(0, 3);
    g.addEdge(1, 4);
    g.addEdge(1, 5);
    g.addEdge(2, 6);
    g.addEdge(3, 7);
    g.addEdge(3, 8);
    g.addEdge(4, 9);
    g.addEdge(6, 10);
    g.addEdge(8, 11);

    g.DFS(3); // 3 7 8 11

    g.DFS(); // 0 1 4 9 5 2 6 10 3 7 8 11
}

 

---

관련 문제

[C#][프로그래머스] 타겟 넘버

[C#][프로그래머스] 무인도 여행

 

---

참고 사이트

https://olrlobt.tistory.com/35

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html