3-1. [그래프 탐색] BFS (전체탐색) Dijkstra (최단거리)

BFS

• 인접 정점 순서로 탐색한다 (결과값: 모든 정점)
  • 구현방법: 인접 정점을 큐에 추가... 반복
  • 자료구조: 큐와 visited 테이블

 

• 문제유형
  • 모든 정점 탐색 => 탐색된 모든 정점의 개수 , 정점의 리스트
  • 특정 정점 탐색 => 특정 정점에 도달하는 가장 빠른 탐색횟수, 가장 빠른 탐색경로

 

# [방법 1] 큐에서 꺼내고 방문처리

from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D"],
    "D": ["B", "C"],
}
S = 'A'

qu = deque([S])
visited = []

while qu:
    node = qu.popleft()

    if node not in visited:
        visited.append(node)
        for e in graph[node]:
            qu.append(e)

print(visited)  # ['A', 'B', 'C', 'D'] 탐색된 모든 정점의 리스트

 

# [방법 2] 큐에 추가할때 방문처리

from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D"],
    "D": ["B", "C"],
}
S = 'A'

qu = deque([S])
visited = [S]

while qu:
    node = qu.popleft()

    for e in graph[node]:
        if e not in visited:
            visited.append(e)
            qu.append(e)

print(visited)  # ['A', 'B', 'C', 'D'] 탐색된 모든 정점의 리스트

 

# 노드가 숫자일 때

import collections

N = 4
graph = [
    [],
    [2, 3],
    [1, 3, 4],
    [1, 2, 4],
    [2, 3]
]
S = 1

qu = collections.deque([S])
visited = [0] * (N + 1)  # 방문여부 테이블
visited[S] = 1

while qu:
    node = qu.popleft()
    print(node, end=' ')  # 탐색

    for e in graph[node]:
        if not visited[e]:
            visited[e] = 1
            qu.append(e)

 

DFS

 

# [방법 1] 재귀하고 방문체크

graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D"],
    "D": ["B", "C"],
}


def dfs(node):
    if node not in visited:
        visited.append(node)
        for e in graph[node]:
            dfs(e)


visited = []
dfs("A")
print(visited)  # ['A', 'B', 'C', 'D']

 

# [방법 2] 재귀 전에 방문체크

graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D"],
    "D": ["B", "C"],
}


def dfs(node):
    visited.append(node)
    for e in graph[node]:
        if e not in visited:
            dfs(e)


visited = []
dfs("A")
print(visited)  # ['A', 'B', 'C', 'D']

 

# 노드가 숫자일 때

N = 4
graph = [
    [],
    [2, 3],
    [1, 3, 4],
    [1, 2, 4],
    [2, 3]
]
S = 1


def dfs(node):
    visited[node] = 1
    print(node, end=' ')  # 탐색

    for e in graph[node]:
        if not visited[e]:
            dfs(e)


visited = [0] * (N + 1)
dfs(S)

 

 

 

다익스트라

• 빠른 정점 순서로 탐색한다 (결과값: 최단거리)
  • 구현방법: 인접 정점의 최단거리 업데이트하고 힙에 추가... 반복
  • 자료구조: 힙과 distances 테이블

 

• 문제유형
  • 모든 정점 탐색 => 탐색된 모든 정점의 최단거리 
  • 특정 정점 탐색 => 특정 정점에 도달하는 최단거리, 최단경로

 

# 다익스트라 (출발점 -> 모든점 최단거리)

import heapq

graph = {
    'A': [('B', 6), ('C', 3)],
    'B': [('A', 6), ('C', 2), ('D', 1)],
    'C': [('A', 3), ('B', 2), ('D', 9)],
    'D': [('B', 1), ('C', 9)],
}
S = 'A'

qu = []
heapq.heappush(qu, (0, S))
dist = {node: int(1e9) for node in graph}
dist[S] = 0

while qu:
    d, node = heapq.heappop(qu)
    if d > dist[node]:
        continue

    for e, w in graph[node]:
        nd = d + w
        if nd < dist[e]:
            dist[e] = nd
            heapq.heappush(qu, (nd, e))

print(dist)  # {'A': 0, 'B': 5, 'C': 3, 'D': 6}

 

# 노드가 숫자인 경우

import heapq

N = 4
graph = [
    [],
    [(2, 6), (3, 3)],
    [(1, 6), (3, 2), (4, 1)],
    [(1, 3), (2, 2), (4, 9)],
    [(2, 1), (3, 9)]
]
S = 1

qu = []
heapq.heappush(qu, (0, S))
dist = [int(1e9)] * (N + 1)
dist[S] = 0

while qu:
    d, node = heapq.heappop(qu)
    if d > dist[node]:
        continue

    for e, w in graph[node]:
        nd = d + w
        if nd < dist[e]:
            dist[e] = nd
            heapq.heappush(qu, (nd, e))

print(dist)  # [1000000000, 0, 5, 3, 6]