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

인트로

그래프의 탐색 알고리즘인 DFS(Depth First Search, 깊이 우선 탐색)를 구현해보려 한다.

 

그래프라는 건 추상적인 개념이다. 0번 정점과 1번 정점이 연결되어 있다는 정보만 있을 뿐 실질적으로 그래프를 구현하는 자료구조는 배열이 될 수도 리스트가 될 수도 벡터가 될 수 있다. 어떤 자료구조를 사용할진 개발자의 선택이다.

 

본 포스팅에선 C# 기반 배열과 리스트(List)로 구현하는 간단한 코드를 소개하려 한다.

결론부터 말하면 재귀 함수를 사용해 DFS를 구현했다.

 

BFS가 궁금하다면?

[Algorithm] BFS (Breadth First Search, 너비 우선 탐색) 알고리즘

[Algorithm] BFS (Breadth First Search, 너비 우선 탐색) 알고리즘

 

DFS 이해하기

1) 아래와 같은 그래프가 있고 DFS를 "0"번 정점부터 시작한다고 가정해보자.

 

 

2) "0"번 정점을 방문하고 "0"번을 방문했다고 표시하자.

 

 

3) "0"번 정점에 인접한(연결된) 정점을 찾아보자.  "1"과 "3"이 연결된 정점이다.

1 시작

 

 

4) 둘 다 방문한 적 없으니 둘 중 숫자가 더 낮은 "1"번을 방문하고 "1"번 정점을 방문했다고 표시한다.

0 -> 1

 

 

5) 이제 "1"번 정점을 기준으로 인접한 정점을 찾아보자. "3"과 "2"가 인접한 정점이다.

인접 정점 찾기

.

 

6) 숫자가 더 낮은 "2"번을 방문하고 방문했다고 표시한다. 

"2"번에 인접한 정점 중 방문하지 않은 정점은 더 이상 없으니 다시 "1"번으로 돌아간다.

1 -> 2

 

 

7) "1"번과 인접한 정점 중 방문하지 않은 유일한 정점인 "3"번을 방문하고 방문했다고 표시한다.

1 - > 3

 

 

 

8) 마찬가지로 "3"번과 인접한 정점인 "4"번 정점을 방문하고 "4"번 정점과 인접한 "5"번 정점을 방문한다.

 

더 이상 방문할 정점이 없으니 DFS는 끝이 난다.

3 -> 4                 4 -> 5

DFS 코드 : 배열

using System.Collections.Generic;

namespace GraphEx
{
    class GraphArray
    {
        private bool[] _visited;
        private int[,] _adj;

        public GraphArray(int n)
        {
            _visited = new bool[n];
            _adj = new int[n, n];
        }

        public void AddEdge(int a, int b)
        {
            _adj[a, b] = 1;
            _adj[b, a] = 1;
        }

        // 1) now를 방문
        // 2) now와 연결된 정점을 확인해서 "방문안했다면" 방문하기
        public void DFS(int now)
        {
            System.Console.WriteLine(now);
            _visited[now] = true;

            for(int next = 0; next < _adj.GetLength(0); next++)
            {
                // 연결되었는가?
                if (_adj[now, next] == 0)
                    continue;
                
                // 이미 방문했는가?
                if (_visited[next])
                    continue;

                DFS(next);
            }
        }
    }
    
    class Program
    {
        static void Main(string[] args)
        {
            GraphArray g = new GraphArray(6);

            g.AddEdge(0, 1);
            g.AddEdge(0, 3);

            g.AddEdge(1, 2);
            g.AddEdge(1, 3);
            
            g.AddEdge(3, 4);

            g.AddEdge(4, 5);

            g.DFS(0);
        }
    }
}

 

DFS 코드 : 리스트(List)

using System.Collections.Generic;

namespace GraphEx
{
    class GraphList
    {
        private bool[] _visited;
        private List<int>[] _adj;

        public GraphList(int n)
        {
            _visited = new bool[n];
            _adj = new List<int>[n];

            for (int i = 0; i < n; i++)
                _adj[i] = new List<int>();
        }

        public void AddEdge(int a, int b)
        {
            _adj[a].Add(b);
            _adj[b].Add(a);
        }

        // 1) now를 방문
        // 2) now와 연결된 정점을 확인해서 "방문안했다면" 방문하기
        public void DFS(int now)
        {
            System.Console.WriteLine(now);
            _visited[now] = true;

            foreach (int next in _adj[now])
            {
                // 이미 방문했는가?
                if (_visited[next])
                    continue;

                DFS(next);
            }
        }
    }
    
    class Program
    {
        static void Main(string[] args)
        {
            GraphList g = new GraphList(6);

            g.AddEdge(0, 1);
            g.AddEdge(0, 3);

            g.AddEdge(1, 2);
            g.AddEdge(1, 3);
            
            g.AddEdge(3, 4);

            g.AddEdge(4, 5);

            g.DFS(0);
        }
    }
}

 

출력 결과

마치며

다음 글은 BFS가 될 것 같은 느낌적인 느낌