BFS (Breadth First Search) 너비우선탐색 대해서

---

* 탐색

그래프의 모든 노드들을 방문하는 일

​

​

* 탐색의 두 가지 방법

1. BFS : Breadth First Search, 너비 우선 탐색

2. DFS : Depth First Search, 깊이 우선 탐색

​

​

* BFS

동심원 형태로 인접한 노드들을 차례대로 탐색 하는 방법 입니다.

너비를 중심으로 탐색 하는 방법 입니다.

BFS Example1                                                                                        BFS Example2

1. L0 = { S }, S는 출발 노드

2. L1 = L0 의 모든 이웃 노드들

3. L2 = L1의 이웃들 중 L0에 속하지 않는 노드들

.............

4. Li = Li-1의 이웃들 중 Li-2에 속하지 않는 노드들

​

​

* 큐를 이용한 BFS 구현

1. check the start node;

2. insert the start node into the queue;

3. while the queue is not empty do

3-1. remove a node v from queue;

3-2. for each unchecked neighbour w of v do

3-3. check and insert w into the queue;

노드 방문 순서 : 1, 2, 3, 4, 5, 7, 8, 6

​

​

* BFS   sudo 코드

// 그래프 G, 출발 노드 s
BFS(G, s) {
    Q ← ø;
    Enqueue( Q, s );
    while Q ≠ ø do {
        u ← Dequeue( Q );
        for each v adjacent to u do{
            if v is unvisited then{
                mark v as visited;
                Enqueue(Q, v);
            }
        }
    }
}

​

​

* BFS와 최단 경로

S에서 Li에 속한 노드 까지의 최단 경로의 길이는 i 이다.

여기서, 경로의 길이는 경로의 속한 에지의 개수를 의미 한다.

즉, BFS를 통하여 각 노드에 대한 최단 경로의 길이를 구할 수 있다.

d[ v ] = s로 부터 v까지의 최단 경로의 길이 (에지의 개수)

π[ v ] = s로 부터 v까지의 최단 경로상에서 v의 직전 노드(predecessor : 전임자)

라고 할때, 최단 경로를 구할수 있는 sudo 코드는 아래와 같습니다.

​

​

* 최단 경로를 구하기 위한 sudo 코드

// 그래프 G, 출발 노드 s
BFS(G, s) {
    Q ← ø;
    d[s] ← 0;    // s로 부터 s까지의 거리는 0
    π[s] ← null; // s의 직전 노드는 없다
    Enqueue( Q, s );
    while Q ≠ ø do {
        u ← Dequeue( Q );
        for each v adjacent to u do{
            if v is unvisited then{
                mark v as visited;
                d[v] ← d[u] + 1;    // v까지의 최단 거리
                π[v] ← u;           // u는 v의 직전 노드
                Enqueue(Q, v);
            }
        }
    }
}

​

​

* 마킹 하는 저장 공간을 줄이고 최단 경로를 구하기 위한 sudo 코드

// 그래프 G, 출발 노드 s
BFS(G, s) {
    Q ← ø;
    // 최단 거리가 입력될 배열에 0이 아닌 -1로 초기화 하여
    // -1인 노드는 아직 방문 하지 않았음을 알수 있다.
    for each node u do{
         d[u] ← -1;
         π[s] ← null;
    }
    d[s] ← 0;
    π[s] ← null;
    Enqueue( Q, s );
    while Q ≠ ø do {
        u ← Dequeue( Q );
        for each v adjacent to u do{
            if(d[v] == -1) then{
                d[v] ← d[u] + 1;
                π[v] ← u;
                Enqueue(Q, v);
            }
        }
    }
}

​

 

* BFS 시간 복잡도

BFS(G, s) {
    Q ← ø;
    for each node u do{
         d[u] ← -1;
         π[s] ← null;
    }
    d[s] ← 0;
    π[s] ← null;
    Enqueue( Q, s );
    while Q ≠ ø do {         // 이 while문이 시간 복잡도를 결정하는 부분!
        u ← Dequeue( Q );                  
        for each v adjacent to u do{
            if(d[v] == -1) then{
                d[v] ← d[u] + 1;
                π[v] ← u;
                Enqueue(Q, v);
            }
        }
    }
}

1. 인접리스트의 경우는 각각의 노드의 Edge의 갯수가 전체 노드 만큼 반복 되므로

아래와 같은 식이 되어 2M이 된다. (M은 엣지의 갯수)

(무방향 그래프일 경우이다, 만약 방향 그래프라면 시간 복잡도는 M이 된다.)

 

2. 인접행렬의 경우 while문이 node의 갯수 만큼 반복하고

인접 노드를 계산하는 for문 역시도 전체 노드 만큼 모두 방문 하게 되므로 node의 갯수 만큼 반복 하게 됩니다.

따라서 N(총 노드 갯수) * N(총 노드 갯수) = N2 만큼의 시간 복잡도가 걸림

​

​

* BFS Tree

각 노드 V와 π[ v ]를 연결하는 에지들로 구성된 트리,

어떤 Edge도 2개의 layer를 건너가지 않으므로,

BFS 트리에서 s에서 v까지의 경로는 s에서 v까지 가는 최단 경로를 의미 한다.

​

​

* 최단 경로 출력하기 sudo 코드

// 출발 노드 s에서 노드 v까지의 경로 출력 하기
PRINT_PATH(G, s, v) {
    if(v == s) then{                        // v가 s인 경우
        print s;
    } else if(π[ v ] == null) then{         // 연결 되어 있지 않은 노드인 경우
        print "no path from s to v exists";  
    } else {
        PRINT_PATH(G, s, π[ v ]);
        print v;
    }
}

​

 

* BFS를 반복하여 모든 노드를 방문 하는

sudo 코드 (disconnected node도 모두 방문)

BFS_ALL( G ){
    while there exists unvisited node v{
        BFS(G, v);
    }
}

 

 

* BFS 미로 탐색

 

 

* DFS 미로 탐색

 

 

* DFS 알고리즘에 대해서

DFS (깊이 우선 탐색)