[자료구조] 그래프(Graph)

이전 포스트의 트리(Tree) 자료 구조는 그래프의 한 종류이다. 하지만 모든 그래프가 트리는 아니다. 

 

그래프(Graph)

- 노드와 그 노드를 연결하는 간선(edge)를 하나로 모아 놓은 것이다.

- 사이클(cycle)이 존재할 수도 있고 존재하지 않을 수도 있다. 사이클이 없는 그래프를 비순환 그래프(acyclic graph) 라고 부른다.

- 방향성이 있을 수도 있고 없을 수도 있다.

 

그래프 표현 방법

1. 인접 리스트(Adjacency list)

- 그래프를 표현할 때 사용되는 가장 일반적인 방법이다.

- 아래 그래프를 인접 리스트로 표현하면 다음과 같다.

adj[0]: 1

adj[1]: 2

adj[2]: 0, 3

adj[3]: 2

방향성이 있는 그래프

2. 인접 행렬(Adjacency matrix)

- N*N boolean matrix(2차원 배열) 로 matrix[i][j] 가 true 라면 i에서 j로의 간선이 있다는 뜻이다. (여기서 N 은 노드의 개수를 뜻한다.)

- 무방향 그래프를 인접 행렬로 표현한다면 대칭 행렬(symmetric matrix)이 된다.

- 인접 행렬에서 어떤 노드에 인접한 노드를 탐색하기 위해선 모든 노드를 전부 확인해야함으로 인접 리스트에 비해 효율이 떨어진다.

(다만, 노드 i에서 j로 연결되어 있는지 알고 싶다면 인접 행렬의 경우 matrix[i][j]로 확인 가능함으로 O(1)의 시간복잡도로 인접 리스트에 비해 효율적이다.)

위 그래프를 인접 행렬로 표현

---

그래프 탐색

깊이 우선 탐색(DFS: Depth-first search)

- 루트 노드에서 시작하여 다음 branch 로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. (깊게 탐색)

- 모든 노드를 방문(visit) 해야하는 경우 선호하는 방법이다. (BFS에 비해 간단)

- 모든 트리 순회는 DFS의 한 종류이다. (전위 순회, 중위 순회, 후위 순회)

(중요! 알고리즘 구현시 노드에 대한 방문 여부를 반드시 검사해야 한다. 아니면 무한루프에 빠질 위험이 있다.)

def dfs(node):
    if node is None:
        return
    
    visit(node)  # 로직 구현
    node.is_visited = True
    
    # 노드의 인접 리스트 확인
    for n in node.adjacent:
    	# 방문 여부 확인
        if not n.is_visited:
            dfs(n)

 

너비 우선 탐색(BFS: Breadth-first search)

- 루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법이다. (넓게 탐색) 

- 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을때 선호하는 방법이다.

- *재귀적으로 동작하지 않는다. (일반적으로 큐를 이용하여 반복적 형태로 구현한다.)

import collections

def bfs(node):
    queue = collections.deque()
    node.is_visited = True

    queue.append(node)  # 큐 끝에 노드 추가

    while len(queue) > 0:
        root = queue.popleft()  # 큐의 맨앞 요소 추출
        
        visit(root)
        
        for n in root.adjacent:
            if not n.is_visited:
                n.is_visited = True
                queue.append(n)

 

양방향 탐색(Bidirectional search)

- 출발지와 도착지 사이에 최단 경로를 찾을 때 사용되는 방법이다.

- 출발지와 도착지 두 노드에서 동시에 BFS 탐색을 수행한 뒤, 두 탐색 지점이 충돌하는 경우에 경로를 찾는 방식이다.

- 양방향 탐색은 너비 우선 탐색보다 k^(d/2) 만큼 더 빠르다.

 

참조: 파이썬 알고리즘 인터뷰 https://github.com/onlybooks/algorithm-interview