개발 공부 - [그래프 알고리즘] 순회 - 그래프에서의 BFS

 그래프 순회 (Graph Traversal)

순회

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

대표적 두 가지 방법

    BFS (Breadth - First Search (너비우선순회))

    DFS (Depth - First Search (깊이우선순회))

BFS는 동심원 형태로 노드를 방문하는 건데

    이거는 모든 노드를 결국 다 방문하기는 하는데,

    출발 노드를 주어지게 해 놓고 (없으면 임의 노드를 출발점으로 삼음)

    인접한 노드를 먼저 탐색하는 방법이다.

    출발노드 -> 모든 이웃 노드 -> 이웃 노드1의 모든 노드 .. -> 이웃노드 n의 모든 노드

    이런 식으로 방문하는데,

    속하지 않는 노드를 추가하는 방식으로 구현한다.

    큐를 이용해서 너비우선순회를 하려면,

    이미 방문한 노드를 check 하도록 해 놓고 (start 노드부터 check로)

    큐에다가 start 노드를 첫번째로 삽입하고, 

    아직 방문되지 않은 노드를 찾아서 check로 바꾸고 또 삽입하고 하는 방식으로

    루프를 돌려서 방문되지 않은 노드가 전체에 아무것도 없을 때까지 돌리면 됨

너비우선순회 수도코드는 도움을 받았음 (치기 귀찮았습니다...)

BFS pesudo code

• 그래프 G, 출발 노드 S

00 BFS(G, s)
01   Q <- null;
02   Enqueue(Q, s);
03   while Q != null do
04     u <- Dequeue(Q);
05     for each v adjacent to u do
06       if v is unvisited then
07         mark v as visited;
08         Enqueue(Q, v);

출처: https://ict-nroo.tistory.com/79?category=698685 [개발자의 기록습관]

이거 최단경로를 구하려면

위의 S에서 Li 에 속한 노드까지의 최단 경로의 길이는 i라는 것으로 두고 시작하는데,

여기서 경로의 길이는 경로에 속한 에지의 개수를 의미한다. (에지 의미는 이전 강좌에 참조)

BFS를 하면서, 각 노드에 대해서 최단 경로의 길이를 구할 수 있다.

* 이거 쥐가 치즈 물고 밖에 나가는 함수 구현할 때 적용하는 그거구나...

최단 경로

입력 : 방향 혹은 무방향 그래프 G = (V, E), 그리고 출발노드 s

출력 : 모든 노드 v에 대해서

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

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

• Pseudo code

  • 02 - 04 : 모든 노드 u에 대해서 d[], π[]를 초기화

  • 05 - 06 : 스타트 노드의 d[], π[]를 설정

  • 11 : d[v] 가 -1인가를 체크하여 unvisited 체크를 구현

  • 12 - 13 : unvisited 노드에 대하여 d[v], π[v]를 저장

    • 최단경로 길이 d[v]는 u까지의 최단경로길이 d[u]를 지나오는 것이므로 d[u] + 1이 될 것이고,

    • v노드의 최단경로상에서 v의 직전노드는 u가 된다.

  • 14 : unchecked 노드만 큐에 들어갈 수 있으므로 어떤 노드도 큐에 두번 들어가지는 않는다.

00 BFS(G, s)
01   Q <- null;
02   for each node u do
03     d[u] <- -1;
04     π[u] <- null;
05   d[s] <- 0;     //distance from s to s is 0
06   π[s] <- null;  //no predecessor of s
07   Enqueue(Q, s);
08   while Q != null do
09     u <- Dequeue(Q);
10     for each v adjacent to u do
11       if (d[v] == -1) then
12         d[v] <- d[u] + 1;    //distance to v
13         π[v] <- u;           //u is the predecessor of v
14         Enqueue(Q, v);

출처: https://ict-nroo.tistory.com/79?category=698685 [개발자의 기록습관]

이렇게 추가해서 모든 노드에 대해서 unvisited / visited에 대한 분기를 한다.

이거를 구현할 때 인접 리스트 방식으로 구현을 하면,

시간 복잡도는 

O(n+m)이 된다. (while문 한번 동작할 때마다 큐에서 하나를 꺼내니까 while문이 최대 n번 동작해야 하는데, 인접리스트로 구현시에 for이 또 각 노드 v에 대해서 degree(v)번 돌기 때문에 이것이 2m이 된다...)

BFS 트리는

각 노드 v와 파이[v]를 연결하는 에지들로 구성된 트리인데,

[BFS 트리에서 s에서 v까지의 경로는 s에서 v까지 가는 최단 경로]

어떤 엣지도 동심원의 2개의 layer(L0에서 L2로 가지 않는다)를 건너가지 않는다.(동일 레이어의 노드를 연결하거나, 혹은 1개의 layer를 건너간다.)

(왜냐면 코드상에서 봐도 checked이면 넘어가니까...)

그래프가 connected 라면 모든 노드를 방문하게 되지만, 그래프가 disconnected 이거나 혹은 방향 그래프라면 BFS에 의해서 모든 노드가 방문되지 않을 수도 있다.

disconnected 그래프의 모든 노드를 방문하려면 BFS를 반복하여 모든 노드 방문

전체 노드중 unvisited 노드가 없을 때까지 BFS를 반복한다.

= 이게 한번 더 방문하더라도 모든 unvisited를 없애려면 BFS를 여러번 하는 것이라는 말인데... (어...근데 그럼 방향 그래프면 굳이 BFS를 왜 쓰지... 하는 의문이 생기지만 DFS 이후에 생각해 보자)