정의와 표현법
그래프란 정점과 간선으로 이루어진 자료구조
각 정점에 대해 간선으로 연결된 이웃한 정점의 개수가 차수이다.
그래프는 네비게이션에서 최단경로 찾기 혹은 구글같은 검색엔진에서 랭킹 정하기와 같이 원소 사이의 연결관계를 설정해야하는 상황에서 유용하게 활용될 수 있는 자료구조
그래프는 방향성을 가질 수 있다.
- 무방향 그래프
- 방향이 없이 연결되어 있다.
- 방향 그래프
- 방향을 가지고 연결되어있음
- 자신을 기준으로 나가는 간선의 갯수는 outdgree
- 반대는 indegree이다.
임의의 한 점에서 출발해 자기 자신으로 돌아올 수 있는 경로를 사이클이라고 한다.
그래프 안에 사이클이 하나라도 있으면 순환그래프라고 하고 없다면 비순환그래프이다.
그래프는 꼭 연결되어 있을 필요도 없고 또 두 정점 사이의 간선이 반드시 1개 이하일 필요도 또 간선이 반드시 서로다른 두 정점을 연결해야할 필요도 없다.
문제에서 “그래프는 연결되어 있다 / 그래프는 연결그래프이다.” , “두 정점 사이의 간선은 최대 1개 존재한다 / 같은 간선은 한 번만 주어진다.” , “간선의 두 정점은 서로 다르다 / 간선은 서로 다른 두 정점을 연결한다.” 와 같이 조건을 엄밀하게 지정하는 경우가 많다.
만약 추가조건이 없다면 그래프가 분리되어 있거나 같은 간선이 여러개 있거나 혹은 자기로부터 출발해 자신에게 돌아오는 루프가 있는 형태에 대해서도 올바른 답을 낼 수 있게 코드를 작성해야 한다.
표현법
인접행렬
두 정점 사이의 간선이 1개 이하인 그래프라고 했을 때 연결된 두 정점에는 1을 연결되지 않은 두정점에는 0을 주면 그래프를 표현할 수 있다.
인접행렬로 그래프를 나타내면 정점이 V개고 간선이 E개 일 때 어떤 두 점이 연결되어 있는지 O(1)에 알 수 있다. 가로 세로가 각각 V인 2차원 배열이 필요하니 O(V**2)의 공간을 필요로 한다.
어떤 점에 연결된 모든 정점의 목록을 알고 싶을 때도 개수와 무관하게 O(V)의 시간이 걸린다.
만드는 방법은 이차원 배열을 미리 선언해두고 입력값을 start, end 형태로 받는다고 했을 때
adj_matrix[start][end] = 1 로 바꾸어주면 된다.
만약 무방향그래프라면 adj_matrix[start][end] = 1, adj_matrix[end][start] = 1 양 방향을 다 설정해준다.
인접리스트
인접행렬과 비교했을 때 정점이 많고 간선은 상대적으로 작은 상황에서 공간을 절약할 수 있는 방식이다.
경우에 따라 인접행렬로는 절대 저장이 불가능해 인접리스트를 써야하는 상황이 있기 때문에 반드시 익숙하게 사용할 수 있어야 한다.
V개의 리스트를 만들어 각 리스트에 자신과 연결된 정점을 넣으면 된다.
인접리스트로 그래프를 나타내면 O(V+E)의 공간이 필요하다.
| 인접행렬 | 인접리스트 | |
|---|---|---|
| 공간복잡도 | O(V**2) | O(V+E) |
| 정점 u, v가 연결되어 있는지 확인하는 시간복잡도 | O(1) | O(min(deg(u), deg(v)) |
deg(정점) → 정점의 차수를 의미
|
| 정점 v와 연결된 모든 정점을 확인하는 시간복잡도 | O(V) | O(deg(v)) |
| 효율적인상황 | 두 점의 연결여부를 자주 확인할 때 E가 V2에 가까울 때 | 특정 정점에 연결된 모든 정점을 자주 확인 할 때 E가 V2 보다 훨씬 작을때 |
256, 512mb 같은 일반적인 메모리 제한이 있는 상황에서는 V가 100,000이면 인접 행렬로 나타낼 수가 없다. 반대로 V가 100이고 E가 7000일 경우에는 인접행렬을 사용하는게 효율적이다.
그러나 일반적인 그래프 문제에서 정점 u,v가 연결되어 있는지 반복적으로 확인해야 하는 경우는 잘 없다.
그래프와 관련된 문제들은 전부 특정 정점에 연결된 모든 정점을 확인하는 작업이 반복적으로 등장한다. 인접행렬보다 인접 리스트를 사용할 일이 많을 것이다.
다만 입력 자체가 인접행렬 형태로 주어지거나 V가 많이 작아서 구현의 편의를 챙기고자 하거나 혹은 플로이드 알고리즘을 쓸 때에는 인접행렬로 그래프를 구현하는 경우도 있다.
연습문제
boj-11724
from collections import deque
import sys
input = sys.stdin.readline
def is_connected_component(start):
node_queue = deque()
node_queue.append(start)
visited[start] = 1
while node_queue:
cur_node = node_queue.popleft()
for next_node in graph[cur_node]:
if not visited[next_node]:
visited[next_node] = 1
node_queue.append(next_node)
return True
if __name__ == '__main__':
N, M = map(int, input().split())
graph = [[ ] for _ in range(N+1)]
visited = [0] * (N + 1)
for _ in range(M):
u_node, v_node = map(int, input().split())
graph[u_node].append(v_node)
graph[v_node].append(u_node)
cnt = 0
for i in range(1, N+1):
if not visited[i] and is_connected_component(i):
cnt+=1
print(cnt)boj-1260
from collections import deque
import sys
input = sys.stdin.readline
def dfs(node):
visited.append(node)
for next_node in sorted(graph[node]):
if next_node not in visited:
dfs(next_node)
def stack_dfs(node):
stack = []
stack.append(node)
while stack:
cur_node = stack.pop()
if cur_node in visited: continue
visited.append(cur_node)
for next_node in sorted(graph[cur_node], reverse=True):
if next_node not in visited:
stack.append(next_node)
def bfs(node):
queue = deque()
queue.append(node)
visited.append(node)
while queue:
cur_node = queue.popleft()
for next_node in sorted(graph[cur_node]):
if next_node not in visited:
visited.append(next_node)
queue.append(next_node)
if __name__ == '__main__':
N, M, start = map(int, input().split())
graph = [[ ] for _ in range(N+1)]
for _ in range(M):
u_node, v_node = map(int, input().split())
graph[u_node].append(v_node)
graph[v_node].append(u_node)
visited = []
stack_dfs(start)
print(*visited)
visited.clear()
bfs(start)
print(*visited)피드백
그래프에서 어렴풋이 알던 개념들을 좀 정리할 수 있었다.
연습문제 1260은 알고리즘을 공부한지 얼마 안 됐을 때 내 마음을 아프게 했던 문제인데 이 문제를 다시 보고 처음 겨우 겨우 풀었던 그 때 보다 속도를 2배 개선한 코드를 훨씬 빠른 시간안에 칠 수 있게 됐다. 나름 뿌듯하다.
