그래프
- 연결되어 있는 객체 간의 관계를 표현하는 자료구조
- 가장 일반적인 자료구조 형태
- 오일러 정리: 모든 정점에 연결된 간선의 수가 짝수이면 오일러 경로 존재함
그래프 정의
- 그래프 G는 (V, E)로 표시
- 정점(Vertices) 또는 노드(Node)
- 간선(Edge) 또는 링크(Link): 정점들 간의 관계 의미
- 시각적으로 달라 보여도 모든 정점 사이의 관계가 동일하다면 같은 그래프
그래프의 종류
- 무방향 그래프
- (A, B) = (B, A)
- V(G) = {A, B, C, D}
- E(G) = {(A, B), (A, C), (A, D), (B, C), (C, D)}
- 방향 그래프
- <A, B> ≠ <B, A>
- 가중치 그래프, 네트워크: 간선에 비용이나 가중치가 할당된 그래프
- 부분 그래프: 그래프의 일부만 포함된 그래프
그래프의 용어
- 인접 정점: 간선에 의해 직접 연결된 정점
- 차수: 정점에 연결된 간선의 수
- 무방향 그래프에서 차수의 합은 간선 수의 2배
- 방향 그래프에서 모든 진입(진출)차수의 합은 간선의 수
- 그래프의 경로: 한 정점에서 다른 정점까지의 경로
- 경로의 길이: 경로를 구성하는데 사용된 간선의 수
- 단순 경로: 경로 중에서 반복되는 간선이 없는 경로
- 사이클(순환): 시작 정점과 종료 정점이 동일한 경로
- 연결 그래프: 모든 정점들 사이에 경로가 존재하는 그래프
- 트리: 사이클을 가지지 않는 연결 그래프
- 완전 그래프: 모든 정점 간에 간선이 존재하는 그래프
- n개의 정점을 가진 무방향 완전 그래프의 간선의 수 = n × (n-1) ÷ 2
그래프 ADT
- isEmpty(): 그래프가 공백 상태인지 확인
- countVertex(): 정점의 수를 반환
- countEdge(): 간선의 수를 반환
- getEdge(u, v): 정점 u에서 정점 v로 연결된 간선을 반환
- degree(v): 정점 v의 차수를 반환
- adjacent(v): 정점 v에 인접한 모든 정점의 집합을 반환
- insertVertex(v): 그래프에 정점 v를 삽입
- insertEdge(u, v): 그래프에 간선 (u, v)를 삽입
- deleteVertex(v): 그래프의 정점 v를 삭제
- deleteEdge(u, v): 그래프의 간선 (u, v)를 삭제
그래프의 표현
인접 행렬을 이용한 표현
- 인접 행렬 M을 이용
- 간선 (i, j)가 있으면 M[i][j] = 1 or true, 없으면 M[i][j] = 0 or false
- 무방향 그래프는 인접 행렬이 대칭 ((A, B) = (B, A)이니까)
인접 리스트를 이용한 표현
- 각 정점마다 연결된 정점, 화살표가 없으면 None
인접 행렬과 인접 리스트의 복잡도 비교
- 정점의 수가 n이고 간선의 수가 e인 무방향 그래프
| 인접 행렬 | 인접 리스트 |
| 간선의 수에 무관하게 항상 n²개의 메모리 공간이 필요함 따라서 정점에 비해 간선의 수가 매우 많은 조밀 그래프에서 효과적 |
n개의 연결 리스트가 필요하고, 2e개의 노드가 필요함 즉 n+2e개의 메모리 고안이 필요함 따라서 정점에 비해 간선의 개수가 매우 적은 희소 그래프에서 효과적 |
| u와 v를 연결하는 간선의 유무는 M[u][v]를 조사하면 바로 알 수 있음 따라서 getEdge(u, v)의 시간 복잡도는 O(1) |
getEdge(u, v) 연산은 정점 u의 연결 리스트 전체를 조사해야 함 정점 u의 차수를 dᵤ라고 한다면 연산의 시간 복잡도는 O(dᵤ) |
| 정점의 차수를 구하는 degree(v)는 정점 v에 해당하는 행을 조사하면 되므로 시간 복잡도는 O(n) | 정점 v의 차수 degree(v)는 v의 연결 리스트의 길이를 반환하면 되므로 시간 복잡도는 O(dᵥ) |
| 정점 v의 인접 정점을 구하는 adjacent(v) 연산은 해당 행의 모든 요소를 검사하면 되므로 O(n)의 시간이 요구됨 | 정점 v에 간선으로 직접 연결된 모든 정점을 구하는 adjacent(v) 연산도 해당 연결 리스트의 모든 요소를 방문해야 되므로 O(dᵥ) |
| 그래프에 존재하는 모든 간선의 수를 알아내려면 인접 행렬 전체를 조사해야 하므로 O(n) | 전체 간선의 수를 알아내려면 헤더 노드를 포함하여 모든 인접 리스트를 조사해야 하므로 O(n+e)의 연산이 요구됨 |
그래프의 탐색
- 가장 기본적인 연산: 시작 정점부터 차례대로 모든 정점들을 한 번씩 방문
- 많은 문제들이 단순히 탐색만으로 해결됨
- 도로망 예: 특정 도시에서 다른 도시로 갈 수 있는지 여부
- 전자회로 예: 특정 단자와 다른 단자의 연결 여부
- 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)
깊이 우선 탐색(DFS)
- Depth-First Search
- 한 방향으로 끝까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색 진행
- 되돌아가기 위해서는 스택 필요 (순환함수 호출로 묵시적인 스택 이용)
def dfs(graph, start, visited = set()): # 처음 호출할 때 visited 공집합
if start not in visited: # start가 방문하지 않은 정점이면
visited.add(start) # start를 방문한 노드 집합에 추가
print(start, end='') # start를 방문했다고 출력
nbr = graph[start] - visited # nbr: 차집합 연산 이용
for v in nbr:
dfs(graph, v, visited)- 한 번 방문한 정점은 다시 탐색하지 않아야 하므로 방문한 정점을 고나리하는 집합(또는 리스트) 필요
- 탐색이 시작되면 시작 정점에서부터 임의의 인접한 정점으로 탐색을 진행, 한번 방문한 정점은 반드시 visited에 넣어야 함
- 한 정점에서의 탐색은 그 정점과 인접한 정점들 중에서 아직 방문하지 않은 정점으로만 가능
- 만약 어떤 정점에서 더 이상 방문하지 않은 인접 정점을 찾아 다시 동일한 방법으로 탐색을 진행
- 이 방법은 가장 최근에 만났던 갈림길로 되돌아가야 하므로 스택을 사용하여 구현
너비 우선 탐색(BFS)
- Breadth-First Search
- 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
- 큐를 사용하여 구현
def bfs(graph, start):
visited = set([start])
queue = collections.deque([start])
while queue:
vertex = queue.popleft()
print(vertex, end='')
nbr = graph[vertex] - visited
for v in nbr:
visited.add(v)
queue.append(v)- 가까운 정점들을 차례로 저장하고, 들어간 순서대로 꺼낼 수 있는 자료구조가 필요 (큐)
- 정점들이 방문될 때마다 큐에 인접 정점을 삽입하고, 더 이상 방문할 인접 정점이 없는 경우 큐의 맨 앞에서 정점을 꺼내 그 정점과 인접한 정점을 차례대로 방문
- 초기 상태의 큐에는 시작 정점만이 저장되어 있고, 너비 우선 탐색 과정은 큐가 공백 상태가 될 때까지 계속
탐색 알고리즘 성능
- 깊이 우선 탐색 / 너비 우선 탐색
- 인접 행렬 표현: O(n²)
- 인접 리스트로 표현: O(n+e)
- 완전 그래프와 같은 조밀 그래프 → 인접 행렬이 유리
- 희소 그래프 → 인접 리스트가 유리
신장 트리
- 그래프 내의 모든 정점을 포함하는 트리
- 사이클을 포함하면 안됨
- 간선의 수 = n-1
- 깊이 우선 신장 트리, 너비 우선 신장 트리
신장 트리 알고리즘
def bfsST(graph, start):
visited = set([start])
queue = collections.deque([start])
while queue:
v = queue.popleft()
nbr = graph[v] - visited # v의 인접 정점에서 방문 정점 제외
for u in nbr: # 갈 수 있는 모든 인접 정점에 대해
print("(", v, ",", u, ")", end='') # (v, u) 간선 추가
visited.add(u)
queue.append(u)위상 정렬
- 방향 그래프에 대해 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것
- 진입차수가 0인 정점을 선택하여 삭제하고, 간선으로 연결된 간선의 차수 변경
