그래프 (1) - 그래프의 구현, DFS와 BFS

그래프의 구현

그래프는 인접 리스트나 인접 행렬로 구현한다.

인접 리스트: 한 정점과 연결되어 있는 다른 정점들을 연결리스트로 표현

인접 행렬: $N \times N$ 행렬을 이용해 정점끼리 연결되어 있으면 1, 없으면 0으로 표현

간선 수가 적은(sqarse한) 경우에는 인접리스트가 더 유리하다.

​

아래는 노드 $N$개와 간선 $M$개가 주어질 때 인접 리스트로 무방향 그래프를 표현하는 코드이다.

N, M = map(int, input().split())
adj = defaultdict(list)
for _ in range(M):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)

 

인접 행렬은 2차원 배열을 이용해서 다음과 같이 표현해 주면 된다.

N, M = map(int, input().split())
adj = [[False]*(N+1) for _ in range(N+1)]

for _ in range(M):
    u, v = map(int, input().split())
    adj[u][v] = True
    adj[v][u] = True

 

 

DFS

DFS는 재귀나 스택을 이용해 구현한다.

 

1. 재귀 활용

재귀함수를 활용하여 한 정점과 연결된 정점을 순차적으로 방문하되, 방문한 정점은 목록을 만들어 배제하는 방식으로 간단히 구현 가능하다. 이때 visited는 $O(1)$에 방문 여부를 확인할 수 있도록 set이나 각 정점의 방문 여부를 담은 배열으로 구현한다.

def dfs(start):
    res = []
    visited = [False]*(N+1)

    def _search(u):
        visited[u] = True
        res.append(u)
        for v in adj[u]: 
            if visited[v]: continue
            _search(v)

    _search(start)
    return res

 

 

2. 스택 활용

스택을 작업 공간으로 활용하는 방식이다. 한 정점과 연결된 정점을 (방문한 정점을 제외하고) 일단 작업 슬롯에 다 넣어 놓고, 넣어 놓은 정점을 꺼내서 방문 처리한 다음 해당 정점과 연결된 정점들을 또 작업 공간에 넣는 방식이다. 이때 dfs가 되기 위해서는 후입선출 구조가 되어야 하므로 작업 슬롯을 stack으로 구현하면 된다.

아래 코드처럼, 하나의 정점과 연결된 정점을 방문하는 데 우선순위가 있는 경우에는(ex. 작은 번호의 정점부터 방문) 스택의 특성을 생각해서 거꾸로 정렬해서 넣어줘야 된다. 아무래도 재귀에 비해서는 다소 비직관적인 측면이 있지만, 함수 호출이 필요한 재귀보다 다소 빠르기 때문에 시간 제한이 강하게 걸리는 문제에서는 스택을 사용한다.

def dfs(start):
    res = []
    visited = [False]*(N+1)

    stack = [start]
    while stack:
        u = stack.pop()
        visited[u] = True
        res.append(u)
        for v in sorted(adj[u], reverse=True):
            if visited[v]: continue
            stack.append(v)
    return res

 

 

BFS

앞서 스택을 활용해 dfs를 구현한 것처럼 비슷하게 구현 가능하다. 이번에는 작업 슬롯이 선입선출 구조가 되어야 하므로 큐를 이용해서 구현한다. bfs의 경우 그래프의 모양에 따라 v가 visited 처리 되기 전에, 다른 정점에서 v를 추가로 방문하여 큐에 v를 중복해서 넣기 쉽다. 따라서 아래와 같이 큐에 넣자마자 방문 처리를 해주도록 할 수 있다.

def bfs(start):
    res = []
    visited = [False]*(N+1)

    queue = deque([start])
    while queue:
        u = queue.popleft()
        visited[u] = True
        res.append(u)

        for v in sorted(adj[u]):
            if visited[v]: continue
            visited[v] = True
            queue.append(v)
    return res

 

dfs와 bfs의 시간복잡도는 인접 리스트의 경우 $O(V+E)$, 인접 행렬의 경우 $O(V^2)$이다.