C# DFS 깊이우선탐색

DFS(깊이우선탐색)

 

BFS는 인접해있는 정점을 하나씩 하나씩 방문을 한다면

DFS는 한 정점의 길을 끝까지 간선으로 연결되있는 정점을 방문하고  더이상 진행할수 없는

곳에 다다르면 다음 후보가 되는 정점의 간선을 따라간다.

 

DFS는 재귀함수방식으로 코드를 짠다.

 

그림으로 보면 더 쉬울것이다.

DFS는 BFS와 달리 길 한쪽을 끝까지 가기때문에 목표가 짧으면

BFS보다 처리속도가 엄청 빠르다.

하지만 탐색 영역이 엄청 넓어질수록 탐색 목표영역이 가까운곳이 아니라

맨 끝쪽에있다면 시간초과 아니면 엄청 느린 처리속도를 가질수있다.

 

한마디로 도박성이라고 할수있다.

 

DFS는 길찾기 등 다양한 방식으로 활용을 한다.

 

내가 짠 코드를 보겠다

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DFS깊이우선탐색
{
    class Graph
    {
        int[,] adj = new int[12, 12]
        {
            { 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0 },
            { 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0 },
            { 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 },
            { 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
            { 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
            { 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0 },
            { 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0 },
            { 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 },
            { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0 },
            { 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
            { 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1 },
            { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 }
        };

        bool[] check = new bool[12];


        public void DFS(int start)
        {
            int now = start;
            check[now] = true;
            Console.WriteLine(now);

            for (int next = 0; next < 12; next++)
            {
                if (adj[now, next] == 0)
                    continue;
                if (check[next])
                    continue;

                DFS(next);
            }
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            Graph graph = new Graph();
            graph.DFS(0);
        }
    }
}

제대로 출력 되는걸 볼수있다.

 

 

참고블로그(평생 공부 블로그 : Today I Learned‍ 🌙 )