DFS/BFS에 대하여

출처 나무위키 http://blog.hackerearth.com/wp-content/uploads/2015/05/dfsbfs_animation_final.gif

 

DFS(Depth-First Search)는 그래프 탐색 알고리즘의 하나로,

그래프의 한 노드를 시작으로 깊이 우선 탐색을 수행하는 알고리즘이다.

 

깊이 우선 탐색은 스택(Stack)이나 재귀 호출을 이용하여 구현할 수 있다.

스택을 사용하는 경우, 각 노드를 방문하기 전에 스택에 삽입하고,

 

해당 노드의 자식 노드들을 순서대로 스택에 삽입한다.

재귀 호출을 사용하는 경우에는 각 노드를 방문할 때마다 재귀 호출을 수행하여

해당 노드의 자식 노드들을 순서대로 탐색한다.

 

DFS는 깊이 우선 탐색을 수행하기 때문에 깊이가 깊어질수록 우선적으로 탐색하기 때문에 스택 오버플로우가 발생할 수 있다. 또한, DFS는 그래프가 커질수록 성능이 저하될 수 있다. 

 

예시 코드 1 (스택)

public void DFS(int start)
{
    // 스택 생성
    Stack<int> stack = new Stack<int>();
 
    // 시작 노드를 스택에 삽입
    stack.Push(start);
 
    // 스택이 빌 때까지 반복
    while (stack.Count > 0)
    {
        // 스택의 제일 위에 있는 노드를 꺼내고, 스택에서 제거
        int current = stack.Pop();
 
        // 해당 노드가 아직 방문하지 않은 노드인 경우
        if (!visited[current])
        {
            // 방문 처리
            visited[current] = true;
            Console.Write(current + " ");
 
            // 해당 노드의 자식 노드들을 스택에 삽입
            for (int i = 0; i < adjacencyList[current].Count; i++)
            {
                int next = adjacencyList[current][i];
                if (!visited[next])
                {
                    stack.Push(next);
                }
            }
        }
    }
}

이 코드에서 adjacencyList는 그래프의 인접 리스트를 저장하는 배열이며, visited 배열은 각 노드가 방문된 적이 있는지 여부를 저장합니다. 이 코드는 주어진 시작 노드를 시작으로 DFS를 수행하며, 각 노드를 재귀 호출하여 순서대로 탐색합니다.

 

예시코드2 (재귀)

public void DFS(int current)
{
    // 해당 노드가 아직 방문하지 않은 노드인 경우
    if (!visited[current])
    {
        // 방문 처리
        visited[current] = true;
        Console.Write(current + " ");
 
        // 해당 노드의 자식 노드들을 순서대로 재귀 호출
        for (int i = 0; i < adjacencyList[current].Count; i++)
        {
            int next = adjacencyList[current][i];
            DFS(next);
        }
    }
}

 

 

 

 

 

BFS(Breadth-First Search)는 그래프 탐색 알고리즘의 하나로,

그래프의 한 노드를 시작으로 깊이가 아닌 너비 우선 탐색을 수행하는 알고리즘이다.

 

BFS는 큐(Queue)를 이용하여 구현할 수 있다. 시작 노드를 큐에 삽입한 후, 큐가 빌 때까지 반복한다.

각 반복마다 큐의 제일 앞에 있는 노드를 꺼내고, 해당 노드의 자식 노드들을 순서대로 큐에 삽입한다.

 

BFS는 깊이 우선 탐색과 달리 시작 노드에서 가까운 정점부터 차례대로 탐색하기 때문에 최단 경로를 찾을 때 유용하게

사용된다. 그러나 BFS는 깊이 우선 탐색보다 시간이 소요되는 경우가 많다.

 

BFS의 단점은 다음과 같은 점들이 있다:

1. 저장 공간이 많이 필요하다: BFS는 깊이가 깊어질수록 계속해서 정점을 추가해야 하기 때문에, 저장 공간이 많이 필요하다. DFS는 재귀 호출을 이용하기 때문에, 재귀 호출이 종료될 때까지만 정점을 저장하기 때문에 저장 공간이 효율적으로 사용된다.
2. 속도가 느리다: BFS는 깊이가 작은 정점부터 탐색을 시작하기 때문에, 깊이가 깊어질수록 정점을 탐색하는 속도가 느려진다. DFS는 깊이가 깊어질수록 빠르게 탐색을 진행할 수 있다.

 

public class Node
{
    public string Value { get; set; }
    public List<Node> Children { get; set; }

    public Node(string value)
    {
        Value = value;
        Children = new List<Node>();
    }
}

public static List<string> BreadthFirstSearch(Node root)
{
    var result = new List<string>();
    var queue = new Queue<Node>();
    queue.Enqueue(root);

    while (queue.Count > 0)
    {
        var currentNode = queue.Dequeue();
        result.Add(currentNode.Value);
        foreach (var child in currentNode.Children)
        {
            queue.Enqueue(child);
        }
    }

    return result;
}

 

 

DFS와 BFS는 각 장단이 다르다.

그렇기 때문에 모든 노드를 방문하고자 하는 경우에는 DFS를

가까운 노드부터 탐색하기 위해서는 BFS를 사용한다.

 

검색 속도 자체는 BFS가 빠르지만 DFS가 더 간단하다.

검색 대상 그래프가 크거나 경로의 특징을 저장해둬야 하는 문제는 DFS를,

검색 대상의 규모가 크지 않고 최단거리를 구해야 하는 문제는 BFS가 유리하다.

 

DFS는 스택 또는 재귀함수로 구현하고 BFS는 큐를 이용해서 구현한다.

 

 

참고 

https://devuna.tistory.com/32