그래프 - DFS 와 BFS

DFS( Depth-First Search / 깊이 우선 탐색)

• 해당 노드의 자식 노드들을 모두 탐색한 후 형제 노드를 탐색한다.
• 모든 노드를 방문하고자 할 때 사용
• 스택 또는 재귀 함수를 사용하여 구현한다.

 

출처 : 위키백과

 

DFS의 장점

• 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
• 목표 노드가 깊은 단계(트리의 레벨이 높은 곳)에 있을 경우 해를 빨리 구할 수 있다.

 

DFS의 단점

• 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 임의의 깊이까지만 탐색하고 목표 노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.
• 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리기 때문이다.
• 최악의 경우, 가능한 모든 경로를 탐험하고서야 해를 찾으므로, 해에 도달하는 데 가장 오랜 시간이 걸린다.

 

 

 

DFS 구현

1. 인접행렬로 구현

void dfs(int x) {
    check[x] = true; // 방문했음을 의미
    printf("%d ", x);
    for (int i=1; i<=V; i++) {
    	//간선이 존재하며 방문하지 않았을 경우
        if (a[x][i] == 1 && !check[i]) {
            dfs(i);
        }
    }
}

 

2. 인접 그래프로 구현

인접행렬과 저장방식만 다르다.(간선이 존재하는지 체크하지 않아도 된다)
void dfs(int x) {
    check[x] = true;
    printf("%d ", x);
    for (int i=0; i<a[x].size(); i++) { // x에 있는 정점의 개수만큼
        int next = a[x][i]; // 간선에 연결된 다음 정점을 찾는다.
        if (!check[next]) { // 방문하지 않았을경우
            dfs(next);
        }
    }
}

 

3. 시간 복잡도

 

여기서 그래프(G) = 정점 집합(V) + 간선 집합(E)으로, 수학적으로 그래프를 G = (V,E)와 같이 표현한다.

 

3_1 인접행렬로 구현

• DFS 하나에는 O(V) 시간이 필요하고, 정점을 방문할 때마다 DFS를 부르는데, V개의 정점을 모두 방문하므로 DFS의 전체 시간 복잡도는   V * O(V) = O(V^2)이다.

3_2 인접 그래프로 구현 

• 인접 행렬로 구현한 경우와 달리 인접 리스트로 구현한 DFS는 DFS 하나당 각 정점에 연결되어 있는 간선의 개수만큼 탐색한다.
• 모든 정점을 한 번씩 방문하고, 모든 간선을 한 번씩 검사하게 되므로 O(V+E)의 시간이 걸린다

 

 

 

 

BFS( Breadth-First Search / 너비 우선 탐색)

• 시작 정점에 인접한 모든 정점들을 우선 방문하는 한 후, 탐색한 정점들에서 인접한 모든 정점들을 방문한다.
• 큐를 사용하여 구현한다.
• DFS과는 다르게 무작정 막힐때까지 탐색을 진행하지 않고, 이곳저곳 살펴보면서 탐색을 진행한다.

 

출처 : 위키백과

 

BFS의 장점

• DFS와 다르게 출발노드에서 목표 노드까지의 최단 길이 경로를 보장한다.

 

 

BFS의 단점

• DFS와 달리 큐(queue)를 사용하기 때문에 노드의 수가 늘어나면 보다 많은 기억 공간을 필요로 하게 된다. 
• 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
• 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

 

 

BFS의 구현

1. 인접행렬로 구현

queue<int> q;
check[1] = true; q.push(1); 
while (!q.empty()) {
    int x = q.front(); q.pop(); // x는 현재 내가 방문하고 있는 정점을 의미한다.
    for (int i =1; i<=V; i++) { // 인접행렬에서는 1부터 정점 개수 n만큼 모두 살펴보아야 한다.
        if (a[x][i] == 1 && !check[1]) { // 간선이 있고 아직 방문하지 않았았을 경우
            check[i] = true; 
            q.push(i);
        }
    }
}

 

2. 인접 그래프로 구현

queue<int> q;
check[1] = true; q.push(1);
while (!q.empty()) {
    int x = q.front(); q.pop();
    for (int i=0; i<a[x].size(); i++;) {
        int y = a[x][i];
        if (check[y] == false) {
            cehck[y] = true; q.push(y);
        }
    }
}

 

3. 시간 복잡도

BFS 알고리즘의 시간 복잡도는 DFS 알고리즘의 시간 복잡도와 같다.

 

3_1 인접행렬로 구현

• O(V^2)

3_2인접 그래프로 구현 

• O(V+E)

 

 

 

++

 

정리해보면,

dfs(깊이우선탐색)은 모든 노드를 탐색할때 사용하기 좋고

bfs(너비우선탐색)은 최단 거리를 탐색할때 사용하기 좋다.

알고리즘 풀때 이러한 접근방식을 사용하기!

 

---

https://soobarkbar.tistory.com/61

DFS (Depth-First Search) & BFS (Breadth-First Search)

https://blog.hexabrain.net/268

알고리즘 4-1강. 깊이 우선 탐색(Depth First Search)

https://blog.hexabrain.net/269?category=431859 

알고리즘 4-2강. 너비 우선 탐색(Breadth First Search)

https://adela.love/posts/dfs-and-bfs

 

그래프 탐색을 위한 DFS와 BFS 알고리즘

https://velog.io/@kjh107704/%EA%B7%B8%EB%9E%98%ED%94%84-BFS%EC%99%80-DFS

[그래프] BFS와 DFS