그래프, DFS, BFS, 서로소 집합 (Disjoint set)
- 그래프
→ 데이터 간 관계를 표시하기 위해 노드 + 간선으로 이루어진 자료구조!
V개 정점을 가지는 그래프는 최대 V (V - 1) / 2 개의 간선이 가능하다.
선형 자료구조나 트리 자료구조로 표현하기 어려운 N:N 관계를 가지는 원소들을 표현 가능
⇒ 실생활에 복잡하게 얽힌 데이터를 표시하기 용이하다.
- 그래프의 유형
무향 그래프
유향 그래프
가중치 그래프
사이클 없는 방향 그래프
완전 그래프 : 정점들에 대해 가능한 모든 간선들을 가진 그래프
부분 그래프 : 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프
- ‘인접’
두 개의 정점에 간선이 존재(연결됨)하면 서로 인접해 있다고 한다.
→ 완전 그래프에 속한 임의의 두 정점은 모두 인접해 있다고 할 수 있다.
경로 : 간선들을 순서대로 나열한 것
단순 경로 : 경로 중 한 정점을 최대 한번만 지나는 경로
사이클 : 시작한 정점에서 끝나는 경로
- 그래프를 표현하는 방법
간선의 정보를 저장하는 방식, 메모리, 성능 등을 고려해서 결정한다.
- 인접 행렬 V * V 크기의 2차원 배열을 이용해서 간선 정보를 저장 (배열의 배열)
- 인접 리스트 각 정점마다 해당 정점으로 나가는 간선의 정보를 저장
- 간선의 배열 간선(시작 정점, 끝 정점)을 배열에 연속적으로 저장
- 인접 행렬
두 정점을 연결하는 간선의 유무를 V * V 정방 행렬로 표현
행 번호와 열 번호는 그래프의 정점에 대응
두 정점이 인접되어 있으면 1, 그렇지 않으면 0으로 표현
- 인접 리스트
각 정점에 대한 인접 정점들을 순차적으로 표현
하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결 리스트로 저장
- 그래프 순회(탐색)
비선형구조인 그래프로 표현된 모든 자료(정점)을 빠짐없이 탐색하는 것
ex) 깊이 우선 탐색, 너비 우선 탐색
- DFS (깊이우선탐색)
정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없으면, 마지막에 만났던 갈림길이 있는 정점으로 돌아와 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회 방법
마지막에 만났던 갈림길의 정점으로 돌아가서 탐색을 반복하므로 후입선출 구조의 자료구조인 스택을 사용한다.
- BFS (너비우선탐색)
인접한 정점들을 모두 방문한 후에, 방문했던 정점과 인접한 정점들을 차례로 방문하는 방식
인접한 정점들을 탐색한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 구조의 자료구조인 큐를 활용한다.
# 1. 그래프를 코드로 표현
# - 인접 행렬
# V * V 배열을 활용해서 표현
# 갈 수 없다면 0, 있다면 1(가중치)를 저장
# 장점 : 노드 간의 연결 정보를 한번에 확인 가능, 간선이 많을수록 유리함. 행렬곱을 이용해서 쉽게 탐색이 가능.
# 단점 : 노드 수가 많아지면 메모리 낭비가 발생한다. 연결이 안된 것도 저장하기 때문! 그래서 노드 수와 메모리 제한을 반드시 확인해야 한다.
graph = [ # graph[i][j] = 1 -> 정점 i와 j가 연결되어 있다.
[0, 1, 0, 1, 0],
[1, 0, 1, 0, 1],
[0, 1, 0, 0, 0],
[1, 0, 0, 0, 1],
[0, 1, 0, 1, 0],
]
# 특징 : 양방향 그래프는 중앙 우하단 대각선을 기준으로 대칭이다.
# - 인접 리스트
# V 개의 노드가 갈 수 있는 정보만 저장한다.
# 장점 : 메모리 사용량이 적다. 탐색 시 갈 수 있는 곳만 확인하기 때문에 탐색시간이 효율적이다.
# 단점 : 특정 노드 간 연결 여부를 확인할 때는 다소 시간이 걸린다.
graph = [ # 리스트 graph[i]의 원소들 = 정점 i와 인접한 정점들
[1, 3],
[0, 2, 4],
[1],
[0, 4],
[1, 3],
]
- 인접 행렬 DFS 코드
# 인접 행렬 DFS : 재귀
graph = [
[0, 1, 0, 1, 0],
[1, 0, 1, 0, 1],
[0, 1, 0, 0, 0],
[1, 0, 0, 0, 1],
[0, 1, 0, 1, 0],
]
visited = [0] * 5
def dfs(now):
# 기저 조건
# 다음 재귀함수 호출 전
visited[now] = 1
print(now, end=' ')
# 다음 재귀 호출
for to in range(5):
if graph[now][to] == 0:
continue # 갈 수 없는 노드면 pass
if visited[to]:
continue # 이미 방문했다면 pass
dfs(to)
# 돌아왔을 때 작업
dfs(0)
# 0 1 2 4 3
- 인접 리스트 DFS 코드
# 인접 리스트 DFS : 재귀
graph = [
[1, 3],
[0, 2, 4],
[1],
[0, 4],
[1, 3],
]
visited = [0] * 5
def dfs(now):
# 기저 조건
# 다음 재귀함수 호출 전
visited[now] = 1
print(now, end=' ')
# 다음 재귀 호출
# 인접 리스트에서는 갈 수 없는 곳 정보가 없기에 체크가 불필요
for to in graph[now]:
if visited[to]:
continue # 이미 방문했다면 pass
dfs(to)
# 돌아왔을 때 작업
dfs(0)
# 0 1 2 4 3
- 인접 행렬 BFS 코드
# BFS -> 갈 수 있는 곳을 처음에 다 가고 먼저 방문하면 먼저 다음 노드를 간다. 즉, 선입선출 구조를 가지고 있어서 Queue를 활용한다!
# list queue, deque queue 를 통해 구현할 수 있다.
# pop(0)로 맨 앞을 꺼낼 때 deque가 처리시간이 더 짧은 이점이 있다.
# 인접 행렬 BFS
graph = [
[0, 1, 0, 1, 0],
[1, 0, 1, 0, 1],
[0, 1, 0, 0, 0],
[1, 0, 0, 0, 1],
[0, 1, 0, 1, 0],
]
def bfs(start):
visited = [0] * 5 # bfs는 재귀가 아니기에 함수 안에서 규정함. 다만 다른 함수 호출이 병행하게 되면 그냥 평소대로 함수 밖에서 규정해도 무방하다.
# 시작 노드를 큐에 추가 + 방문 표시
queue = [start]
visited[start] = 1
while queue:
now = queue.pop(0)
print(now, end=' ')
# 갈 수 있는 곳을 체크
for to in range(5):
if graph[now][to] == 0:
continue
if visited[to]:
continue
visited[to] = 1
queue.append(to)
bfs(0)
# 0 1 3 2 4
- 인접 리스트 BFS 코드
# 인접 리스트 BFS
graph = [
[1, 3],
[0, 2, 4],
[1],
[0, 4],
[1, 3],
]
def bfs(start):
visited = [0] * 5 # bfs는 재귀가 아니기에 함수 안에서 규정함. 다만 다른 함수 호출이 병행하게 되면 그냥 평소대로 함수 밖에서 규정해도 무방하다.
# 시작 노드를 큐에 추가 + 방문 표시
queue = [start]
visited[start] = 1
while queue:
now = queue.pop(0)
print(now, end=' ')
# 갈 수 있는 곳을 체크
for to in graph[now]:
if visited[to]:
continue
visited[to] = 1
queue.append(to)
bfs(0)
# 0 1 3 2 4
- 서로소 집합 = Disjoint Set
서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다. 즉, 교집합이 없다.
집합에 속한 하나의 특정 멤버를 통해 각 집합을 구분하는데, 이를 대표자라고 한다.
→ 우리편, 너희편을 구분하는 셈인데, 각 편의 대표자를 통해 구분을 하는 것!
서로소 집합 또한 하나의 자료구조이고 보통 소속 집합이 자주 바뀌는 동적상황에서 사용한다.
데이터가 같은 집합에 속해있다 = 관계가 있다 = 그래프(트리)로 표현 가능
연결 컴포넌트를 하나의 집합으로 보는 셈이다.
상호배타 집합을 표현하는 방법
→ 연결 리스트, 트리
- 상호배타 집합 연산
Make-Set ( x ) : 집합 만들기. 처음엔 만든 자기자신이 대표자가 된다.
Find-Set ( x ) : 너네 대표 누구니? = 너는 어디 집합에 속해있니?
Union ( x , y ) : 같은 집합으로 합치기. 대표자가 누가 될 지는 조건에 따라 달라진다.
# 1~6번까지 노드가 존재.
# 1. make_set
def make_set(n):
return [i for i in range(n)] # 자기자신이 대표인 데이터 6개를 리스트로 생성
# [0,1,2,3,4,5] 숫자의 의미? -> 각 대표자 인덱스!
# 1~6번까지를 사용하기 위해 7개 생성 (0번은 안쓰고 버림)
parents = make_set(7)
# 2. find_set : 대표자를 찾아보자 -> 부모 노드를 확인하고 부모 노드도 부모(대표자)와 연결이 되어있으면 자기 자신이 대표인 데이터를 찾을 때까지 반복한다.
def find_set(x):
# 자기 자신이 대표자면 종료
if parents[x] == x:
return x
# 대표자가 따로 있으면
return find_set(parents[x])
# 3. union
def union(x, y):
x = find_set(x)
y = find_set(y)
# 이미 같은 집합에 속해있다면 continue
if x == y:
return
# 다른 집합이라면 합친다.
# 예) 더 작은 루트 노드에 합쳐야 하는 경우
if x < y:
parents[y] = x
else:
parents[x] = y
union(1, 3)
union(2, 3)
union(5, 6)
print(parents)
# [0, 1, 1, 1, 4, 5, 5]
- 간선 완화 = Edge Relaxation ( BFS로 최단 경로 구하기 )
V, E = map(int, input().split())
G = [[] for _ in range(V + 1)]
for _ in range(E):
# 간선정보 = 정점1, 정점2, 가중치
u, v, weight = map(int, input().split())
G[u].append((v, weight))
G[v].append((u, weight))
D = [1e9] * (V + 1) # 출발점에서 각정점까지 최단 거리
P = [i for i in range(V + 1)] # 최단 경로 트리
D[1] = 0
Q = [1] # 출발점 삽입
while Q:
u = Q.pop(0)
# 출발점 ---> u --> v 로 가는 경로를 확인
# u의 인접 정점(v)에 대해 작업 => (u, v) 간선 완화 작업
for v, weight in G[u]:
if D[v] > D[u] + weight:
D[v] = D[u] + weight
P[v] = u
Q.append(v)
print(D[1:])
print(P[1:])