[알고리즘] 그래프 순회

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# BFS
def iterative_bfs(start_v):
    discovered = [start_v]
    queue = [start_v]
    while queue:
        v = queue.pop(0)
        for w in graph[v]:
            if w is not in discovered:
                discovered.append(w)
                queue.append(w)
    return discovered

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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

from collections import deque

def bfs_min_distance(num_node, graph, start, end):
    q = deque([start])
    # 방문여부 체크
    visited = [False] * (num_node+1)
    visited[start] = True
    # 최단거리
    dist = [False] * (num_node+1)
    dist[start] = 0
    while q:
        v = q.popleft()
        for i in graph[v]:
            if not visited[i]:
                q.append(i)
                visited[i] = True
                dist[i] += dist[v]+1
    return dist[end]

print(bfs_min_distance(8, graph, 1, 5))

1
2
3
4
5
6
7

# DFS (재귀)
def recursive_dfs(v, visited=[]):
    visited.append(v)
    for w in graph[v]:
        if not w in visited:
            visited = recursive_dfs(w, visited)
    return visited