Part 2-4-3. 그래프 : DFS(깊이 우선 탐색)

 

 

 

DFS(깊이 우선 탐색)

 

 

[1. 배열로 구현된 그래프 DFS]

    class Graph
    {
        int[,] adj = new int[6, 6]
        {
            { 0, 1, 0, 1, 0, 0 },
            { 1, 0, 1, 1, 0, 0 },
            { 0, 1, 0, 0, 0, 0 },
            { 1, 1, 0, 0, 1, 0 },
            { 0, 0, 0, 1, 0, 1 },
            { 0, 0, 0, 0, 1, 0 },
        };

        bool[] visited = new bool[6]; // 방문 체크를 위해

        public void DFS(int now)  // 순회 시작 위치가 인수로 들어 옴
        {
            // 1) now 부터 방문 하고
            Console.WriteLine(now);
            visited[now] = true;

            // 2) now 와 연결된 정점들을 하나씩 확인해서, [ 아직 미 방문 상태라면 ] 방문한다.
            for (int next = 0; next < 6; next++)
            {
                if (adj[now, next] == 0)  // 연결 되어 있지 않으면 스킵
                    continue;
                if (visited[next])      // 이미 방문 했으면 스킵
                    continue;
                DFS(next);   // 재귀 (깊이 들어 감)
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Graph graph = new Graph();
            graph.DFS(3);  // 3 0 1 2 4 5
        }
    }

 

[순회방법]

1. 일단 방문 체크를 한다.
2. 연결이 되어 있으며, 아직 방문하지 않은 곳이라면 깊이 들어가 방문한다.
3. 배열은 연결 되어 있지 않은 정보도 포함되어 있기 때문에 (0) 연결 되어 있는지 즉 갈 수 있는지를 체크해주어야 한다.
4. 갈 수 있는 곳이라면 깊이 들어간다. 👉 재귀 함수 호출

 

DFS(3) 3 에서 DFS 순회를 시작했다면 3 0 1 2 4 5 순으로 방문하게 될 것이다.

 

---

 

[2. 리스트로 구현된 그래프 DFS]

    class Graph
    {
        List<int>[] adj2 = new List<int>[]
        {
            new List<int>() { 1, 3 },
            new List<int>() { 0, 2, 3 },
            new List<int>() { 1 },
            new List<int>() { 0, 1, 4 },
            new List<int>() { 3, 5 },
            new List<int>() { 4 },
        };

        bool[] visited = new bool[6];
        
        public void DFS2(int now)
        {
            // 1) now 부터 방문 하고
            Console.WriteLine(now);
            visited[now] = true;

            // 2) now 와 연결된 정점들을 하나씩 확인해서, [ 아직 미 방문 상태라면 ] 방문한다.
            foreach (int next in adj2[now])
            {
                if (visited[next])      // 이미 방문 했으면 스킵
                    continue;
                DFS2(next);
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Graph graph = new Graph();
            graph.DFS2(0);  // 0 1 2 3 4 5
        }
    }

 

 

[순회방법]

1. 아까와 같이 일단 방문 체크를 한다.
2. 아직 방문하지 않은 곳이라면 깊이 들어가 방문한다.
3. 리스트는 나와 연결 되어 있는 정보만 갖고 있기 때문에 연결되어 있는지를 체크할 필요가 없다.
4. 갈 수 있는 곳이라면 깊이 들어간다. 👉 재귀 함수 호출

 

DFS2(0) 3 에서 DFS 순회를 시작했다면 0 1 2 3 4 5 순으로 방문하게 될 것이다.

 

---

 

 

[3. 연결이 끊겨져 있는 그래프 DFS]

        public void SearchAll()
        {
            visited = new bool[6];  // 전부 false로 초기화

            for (int now = 0; now < 6; now++)
            {
                if (visited[now] == false)
                    DFS(now);
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Graph graph = new Graph();

            graph.SearchAll();  // 0 1 2 3 4 5
        }
    }

 

1. now = 0 👉 DFS(0)

• 이 호출 하나가 끝났을 땐, visited[0], visited[1], visited[2], visited[3] 의 값은 true로 바뀌어 있다. 0을 기준으로 시작하여 깊이 들어가 0, 1, 2, 3 정점을 모두 방문했기 때문이다.
• now 값이 1, 2, 3 일땐 if (visited[now] == false) 걸리지 않는다. (생각보다 if문이 자주 호출되진 않음. DFS(0) 호출 한번으로 0, 1, 2, 3 을 모두 방문하게 되기 때문이다.)
• 이처럼 연결만 되어 있다면 정점 하나로 연결된 모든 정점들을 DFS 순회법으로 전부 방문할 수 있다.

 

2. now = 4 👉 DFS(4)

• 이 호출 하나로 visited[4], visited[5] 방문

 

 

 이처럼 연결이 끊겨 있는 그래프를 전부 방문하기 위해 이와 같은 방법을 사용할 수 있다. 한번의 DFS 순회로 연결 되어 있는 노드는 다 방문할 수 있기 때문에 if (visited[now] == false) 방문 되지 않은 정점을 검사한다는 의미는, 연결이 끊겨 있는 곳이 있을 것을 대비해서다.