깊이 우선 탐색(Depth-first search, DFS)

깊이 우선 탐색이란?

• 분류 : 검색 알고리즘
• 자료 구조 : 그래프(Graph)

깊이 우선 탐색(Depth-first search, DFS)은 맹목적 탐색방법의 하나로 탐색트리의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표 도일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다.

 

의사 코드(Pseudo Code)

DFS(G, u)
    u.visited = true
    for each v ∈ G.Adj[u]
        if v.visited == false
            DFS(G,v)
     
init() {
    For each u ∈ G
        u.visited = false
     For each u ∈ G
       DFS(G, u)
}

 

C# 예제 코드

class Graph
{
    private bool[] visited;
    private int[,] adj;

    public Graph(int size)
    {
        visited = new bool[size];
        adj = new int[size, size];
    }

    public void AddEdge(int src, int dest)
    {
        adj[src, dest] = 1;
        adj[dest, src] = 1;
    }

    public void DFS(int now)
    {
        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);
        }
    }
}

public class Program
{
    public static void Main()
    {
        Graph graph = new Graph(7);
        graph.AddEdge(0, 1);
        graph.AddEdge(0, 3);
        graph.AddEdge(1, 2);
        graph.AddEdge(1, 3);
        graph.AddEdge(2, 6);
        graph.AddEdge(3, 4);
        graph.AddEdge(4, 5);

        graph.DFS(0);
    }
}

 

 

 

참고 사이트

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