DFS (Depth-First Search)?

• 깊이 우선 탐색으로 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 입니다.

• 스택을 이용하여 구현할 수 있습니다.

• 동작 과정

  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다.
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리를 합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다.
  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.

• 예시

  

  1을 시작노드로 정하고 인접한 노드중에서는 번호가 작은 것부터 방문처리를 하겠습니다.

  

  먼저 시작 노드인 1을 스택에 넣고 방문처리 합니다.

  

  스택에서 최상단 노드였던 (1) 의 인접한 노드중 방문하지 않은 노드***(2,3,8)를 확인하고, 그중에서 제일 작은 노드(2)***를 스택에 넣고 방문처리 합니다.

  

  다시 가장 최상단인 (2) 의 인접한 노드중 방문하지 않은 노드를 확인합니다. ***(7)***밖에 없으므로 ***(7)***을 스택에 넣고 방문처리 합니다.

  

  최상단 노드인 (7) 의 인접한 노드중 방문하지 않은 노드***(6,8)를 확인하고, 그중에서 제일 작은 노드(6)***를 스택에 넣고 방문처리 합니다.

  

  최상단 노드인 (6) 은 인접한 노드가 없으므로 6을 스택에서 꺼냅니다.

  

  최상단인 (7 ) 의 인접한 노드중 방문하지 않은 노드를 확인합니다. ***(8)***밖에 없으므로 ***(8)***을 스택에 넣고 방문처리 합니다.

  

  이 과정을 반복하면 탐색순서는 다음과 같습니다.

  1 → 2→ 7 → 6 → 8 → 3→ 4→ 5

• 구현

graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = []

def dfs(node):
    if node in visited:
        return

    visited.append(node)

    for i in graph[node]:
        dfs(i)

BFS (Breadth-First Search )?

• 너비 우선 탐색이라고 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘 입니다.

• 큐를 이용하여 구현할 수 있습니다.

• 동작과정

  1. 탐색 시작 노드를 큐에 넣고 방문처리를 합니다.
  2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드중에서 방문하지 않은 노드를 모두 큐에 넣고 방문처리를 합니다.
  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.

• 예시

  

  1을 시작노드로 정하고 인접한 노드중에서는 번호가 작은 것부터 방문처리를 하겠습니다.

  

  먼저 시작 노드인 1을 큐에에 넣고 방문처리 합니다.

  

  큐에서 (1) 을 꺼내고 인접한 노드중 방문하지 않은 노드***(2,3,8)***를 큐에 넣고 방문 처리를 합니다.

  

  큐에서 (2) 를 꺼내고 인접한 노드중 방문하지 않은 노드를 확인합니다. ***(7)***밖에 없으므로 ***(7)***을 큐에 넣고 방문처리 합니다.

  

  그다음 (3) 을 꺼내고 ***인접한 노드중 방문하지 않은 노드(4,5)***를 큐에 넣고 방문처리 합니다.

  

  큐에서 (8) 을 꺼내고 인접한 노드가 없으므로 넘어갑니다.

  

  이 과정을 반복하면 탐색순서는 다음과 같습니다.

  1 → 2→ 3 → 8 → 7 → 4→ 5→ 6

• 구현

graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = []

def bfs(start):
    queue = []
    queue.append(start)
    visited.append(start)
    
    while queue:
        num = queue.pop(0)
        for i in graph[num]:
            if i not in visited:
                queue.append(i)
                visited.append(i)