DFS, BFS (Graph)

  • 최초 작성일: 2023년 1월 6일(금)

목차

[TOC]

내용

DFS, BFS 개념

: 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동

image

출처 https://developer-mac.tistory.com/64


개념

  • 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방식

  • 위의 이미지 순서대로 탐색

    • 모든 노드를 방문할 때 이 방법을 사용함
    • 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
    • 스택(Stack) 또는 재귀함수(Recursion)로 구현함



: 최대한 넓게 이동한 뒤, 더 이상 갈 곳이 없을 경우 아래로 이동

image

출처 https://developer-mac.tistory.com/64


개념

  • 루트 노드에서 시작해서 인접한 노드를 먼저 탐색
  • 위의 이미지대로 시작점에서부터 가까운 정점을 먼저 방문하고 멀리 떨어진 순으로 방문하는 순회 방법
  • 큐(Queue)를 이용함



실습

DFS

using System;
using System.Collections.Generic;

namespace GraphProj
{
    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 },
        };

        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 },
        };

        // 1) 우선 now부터 방문하고,
        // 2) now와 연결된 정점들을 하나씩 확인해서, 아직 미발견(미방문) 상태라면 방문한다.
        public void DFS(int now, bool[] visited)
        {
            Console.WriteLine(now);
            visited[now] = true; // 1) 우선 now부터 방문하고,
            adj.GetLength(0);

            for (int next = 0; next < 6; next++)
            {
                if (adj[now, next] == 0)    // 연결되어 있지 않으면 스킵.
                    continue;
                if (visited[next])      // 이미 방문했으면 스킵
                    continue;
                DFS(next, visited);
            }
        }

        // 2) now와 연결된 정점들을 하나씩 확인해서, 아직 미발견(미방문) 상태라면 방문한다.
        public void DFS2(int now, bool[] visited)
        {
            Console.WriteLine(now);
            visited[now] = true; // 1) 우선 now부터 방문하고,

            foreach (int next in adj2[now])
            {
                if (visited[next])      // 이미 방문했으면 스킵
                    continue;
                DFS2(next, visited);
            }

        }

        public void SearchAll()
        {
            bool[] visited = new bool[6];
            for (int now = 0; now < 6; now++)
                if (visited[now] = false)
                    DFS(now, visited);
        }
    }
}


BFS 소스코드

using System;
using System.Collections.Generic;

namespace GraphProj
{
    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 },
        };

        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 },
        };

        public void BFS(int start)
        {
            bool[] found = new bool[6];
            int[] parent = new int[6];
            int[] distance = new int[6];

            Queue<int> q = new Queue<int>();
            q.Enqueue(start);
            found[start] = true;
            parent[start] = start;
            distance[start] = 0;

            while (q.Count > 0)
            {
                int now = q.Dequeue();
                Console.WriteLine(now);

                for (int next = 0; next < 6; next++) 
                {
                    if (adj[now, next] == 0)    // 인접하지 않았으면 스킵
                        continue;
                    if (found[next])    // 이미 발견한 애라면 스킵
                        continue;
                    q.Enqueue(next);
                    found[next] = true;
                    parent[next] = now;
                    distance[next] = distance[now] + 1;
                }
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            // DFS (Depth First Search 깊이 우선 탐색)
            // BFS (Breadth First Search 너비 우선 탐색)
            Graph graph = new Graph();
            graph.BFS(0);
            //graph.SearchAll();

        }
    }
}



BFS 소스처럼 중간 중간에 코드를 추가하여 각 그래프 간 거리 및 각 노드들의 부모 노드에 대한 정보를 얻을 수 있다.

image