그래프 - 인접 행렬과 인접 리스트

인접 행렬

정의

인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식.

 

adj[i][j]: 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0

 

간선에 방향이 있는 유향 그래프가 아닌, 간선에 방향이 없는 무향 그래프의 경우에는, 노드 i -> 노드 j가 존재하면 노드 j -> 노드 i도 존재하는 것이다. 따라서 대각 성분(adj[i][j]에서 i == j)을 기준으로 대칭인 성질을 가지게 된다.

 

장점

- 구현이 쉽다

- 노드 i와 노드 j가 연결되어 있는지 확인하고 싶을 때, indexing으로 접근하기 때문에 O(1)의 시간 복잡도를 가진다

 

단점

- 전체 노드의 개수를 V개, 간선의 개수를 E개라고 하면, 노드 i에 연결된 모든 노드들에 방문하고 싶은 경우 adj[i][1]부터 adj[i][V]를 모두 확인해봐야 하기 때문에 총 O(V)의 시간이 걸린다.

- 노드의 수에 비해 간선의 개수가 훨씬 적은 그래프면 적절하지 않다.

 

구현

그래프에 대한 정보는

- 노드의 개수(n)

- 간선의 개수(e)

- 각 간선의 양 끝 노드(nodes)

로 주어진다.

 

인접 행렬로 저장하기 위해서 작성해야 하는 코드

- 노드의 개수와 간선의 개수를 입력받은 후, 간선의 개수만큼 for문을 돌면서 양 끝 노드를 입력받으면 된다.

- 아래 예시는 방향이 없는 무향 그래프를 인접 행렬으로 구현하는 코드이다

n = 4
e = 5
nodes = [[1, 2], [1, 3], [1, 4], [2, 3], [3, 4]]

adj = [[0 for _ in range(n)] for _ in range(n)]

for src, dst in nodes:

    adj[src-1][dst-1] = 1

    adj[dst-1][src-1] = 1

 

 

인접 리스트

정의

각각의 노드에 연결된 노드들을 원소로 갖는 리스트들의 배열을 의미한다

 

adj[i]: i번째 노드에 연결된 노드들을 원소로 갖는 리스트

 

장점

- 실제 연결된 노드에 대한 정보만 저장하기 때문에, 모든 원소의 개수의 합이 간선의 개수와 동일하다

- 즉, 간선의 개수에 비례하는 메모리만 차지하여 구현이 가능하다

- 각 노드에 연결된 모든 노드들을 방문해 보아야 하는 경우, 인접 리스트로 연결 관계를 저장하는 것이 시간상 큰 이점을 가진다

 

단점

- 노드 i와 노드 j의 연결 여부를 알고 싶을 때, adj[i] 리스트를 순회하며 j 원소가 존재하는지 확인해야 한다 - 시간복잡도 O(V)

- 인접 행렬은 adj[i][j]가 1인지 0인지만 확인하면 i와 v 노드의 연결 여부를 O(1)로 확인 가능하다

 

구현

n = 4
e = 5
nodes = [[1, 2], [1, 3], [1, 4], [2, 3], [3, 4]]

adj = [[] for _ in range(n)]

for src, dst in nodes:
    adj[src-1].append(dst-1)
    adj[dst-1].append(src-1)

 

 

그래프 탐색하기

- 노드 개수에 비해 엣지 개수가 훨씬 적인 그래프라면 인접 행렬 < 인접 리스트 -> 전체 노드가 아닌 연결된 노드만 살펴보면 되기 때문이다

- 두 노드의 연결 관계를 알고싶을 때는 인접 행렬이 효율적이다

 

# undirected graph

graph = {'A': set(['B', 'C']), 
	'B': set(['A', 'D', 'E']), 
        'C': set(['A', 'F']), 
        'D': set(['B']), 
        'E': set(['B', 'F']), 
        'F': set(['C', 'E'])}

 

너비 우선 탐색(BFS)

- 그래프 내 모든 노드를 방문하고 싶을 때

- 찾는 것을 발견할 때까지 모든 노드를 적어도 한 번은 방문하고 싶을 때

- 시작 노드로부터 차례대로 인접 노드들을 queue에 추가하는 방식을 사용해 구현할 수 있다

 

def bfs(graph, start):
    visited = []
    queue = [start]
    
    while queue:
    	n = queue.pop(0)
        if n not in visited:
            visited.append(n)
            queue += graph[n] - set(visited)
    return visited

 

## result
> bfs(graph, 'A')
['A', 'B', 'C', 'D', 'E', 'F']

 

두 노드 간 경로 탐색

위의 코드를 조금 수정해 두 노드 간 가능한 모든 경로를 찾아보자

 

def bfs_paths(graph, start, end):
    queue = [(start, [start])]
    result = []
    
    while queue:
    	n, path = queue.pop(0)
        if n == end:
        	result.append(path)
        else:
        	for m in graph[n] - set(path):
            		queue.append((m, path + [m]))
    return result

 

너비 우선 경로 탐색을 진행하면 가장 먼저 찾은 경로가 최단 경로가 된다

 

>> bfs_paths(graph, 'A', 'F')
[['A', 'C', 'F'], ['A', 'B', 'E', 'F']]
>> bfs_paths(graph, 'D', 'F')
[['D', 'B', 'E', 'F'], ['D', 'B', 'A', 'C', 'F']]

 

깊이 우선 탐색(DFS)

- 매우 큰 그래프에서, 탐색을 시작한 노드로부터 너무 멀어지게 되면 즉시 그만두고 싶을 때 사용하면 효과적이다

- 트리 순회 기법은 전부 DFS이다

- 과거 위치의 인접 노드보다 현재 위치의 인접 노드를 먼저 방문한다는 특징을 가지므로, stack을 사용해 구현

 

def dfs(graph, start):
    visited = []
    stack = [start]
    
    while stack:
    	n = stack.pop()
        if n not in visited:
            visited.append(n)
            stack += graph[n] - set(visited)
    return visited

>> dfs(graph, 'A')
['A', 'B', 'E', 'F', 'C', 'D']

 

두 노드 간 경로 탐색

위의 코드를 조금 수정하여 두 노드 간 가능한 모든 경로를 찾아보자

 

def dfs_paths(graph, start, end):
    stack = [(start, [start])]
    result = []
    
    while stack:
        n, path = stack.pop()
        if n == end:
            result.append(path)
        else:
            for m in graph[n] - set(path):
                stack.append((m, path + [m]))
    return result

 

>> dfs_paths(graph, 'A', 'F')
[['A', 'C', 'F'], ['A', 'B', 'E', 'F']]
>> dfs_paths(graph, 'D', 'F')
[['D', 'B', 'A', 'C', 'F'], ['D', 'B', 'E', 'F']]

 

깊이 우선 탐색은 너비 우선 탐색과는 달리 최단 경로를 가장 먼저 찾지 못할 수 있다

 

 

 

출처: [그래프] 인접 행렬과 인접 리스트, [Python] 인접 행렬과 인접 리스트, 파이썬을 사용한 그래프의 너비 우선 탐색과 깊이 우선 탐색 구현