1. 너비 우선 탐색(BFS, Breadth-First Search)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

1. (1)번에서 루트노드에 방문하고,

2. (2)(3)(4)(5)에서 인접하고 방문된적 없으며 큐에 저장되지 않은 노드를 큐에 저장한다.

3. (6)에서 가장먼저 큐에 저장된 1번 노드로 이동해서 인접노드들의 조건을 확인한다.

4. 이 방식을 큐에 저장된 노드가 없을 때까지 반복한다.

특징

1. 두 노드사이의 최단경로를 탐색할때 활용하기 좋은 방식이다.

• 멀리떨어진 노드는 나중에 탐색하는 방식이기 때문!

2. 큐를 활용해서 탐색할 노드의 순서를 저장하고 큐에 저장된 순서대로 탐색한다.

• 선입선출의 방식을 활용해야 하기 때문에 큐를 활용한다.

2. 너비 우선 탐색 장단점

장점

1. 최적해를 찾음을 보장한다

단점

1. 최소 실행시간보다는 오래 걸린다는 것이 거의 확실하다.

2. 최악의 경우, 실행에 가장 긴 시간이 걸릴 수 있다.는 의미이다.

3. 너비 우선 탐색 구현

구현방법

• 자료 구조 큐(Queue)를 이용

깊이 우선 탐색(DFS)의 시간 복잡도

• 그래프를 인접 행렬(adjacency matrix)로 구현했는지, 인접 리스트(adjacency list)로 구현했는 지에 따라 구현방법이 달라진다.
  인접행렬과 인접 리스트의 차이

queue 자료구조, 인접행렬

from collections import deque
def bfs(matrix, i, visited):
  queue= deque()
  queue.append(i)
  while queue:
    value = queue.popleft()
    if not visited[value]:
      print(value, end=' ')
      visited[value] = True
      for c in range(len(matrix[value])):
        if matrix[value][c] == 1 and not visited[c]:
          queue.append(c)

BFS 하나당 N번의 loop를 돌게 되므로 O(n)의 시간복잡도를 가진다. 그런데 N개의 정점을 모두 방문 해야하므로
n*O(n)이므로 O(n^2)의 시간복잡도를 가지게 된다.

따라서 O(n^2)의 시간복잡도를 가지게 된다.

queue 자료구조, 인접리스트

from collections import deque
def bfs(graph, i, visited):
  queue= deque()
  queue.append(i)
  while queue:
    value = queue.popleft()
    if not visited[value]:
      print(value, end=' ')
      visited[value] = True
      for j in graph[value]:
        queue.append(j)

BFS가 총 N번 호출되긴 하지만 인접행렬과 달리 인접 리스트로 구현하게 되면 BFS하나당 각 정점에 연결되어 있는 간선의 개수만큼 탐색을 하게 되므로 예측이 불가능 하다. 하지만 BFS가 다 끝난 후를 생각하면, 모든 정점을 한번씩 다 방문하고, 모든 간선을 한번씩 모두 검사했다고 할 수 있으므로 O(n+e)의 시간이 걸렸다고 할 수 있다.

따라서 시간복잡도는 O(n+e)이다.

4. 참고문헌

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
https://velog.io/@sukong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%9C%EB%85%90-%EB%84%88%EB%B9%84%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89BFS-lp8zywtn
https://dad-rock.tistory.com/644
https://velog.io/@tks7205/dfs%EC%99%80-bfs%EB%A5%BC-%EA%B5%AC%ED%98%84%ED%95%98%EB%8A%94-%EC%97%AC%EB%9F%AC%EA%B0%80%EC%A7%80-%EB%B0%A9%EB%B2%95-in-python