그래프 기본
-
그래프
: 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료구조 (선형 자료구조나 트리 자료구조로 표현하기 어려운 N:N 관계를 가지는 원소들을 표현하기에 용이) -
그래프 유형
무향 그래프
유향 그래프
가중치 그래프
사이클 없는 방향 그래프
완전 그래프: 정점들에 대해 가능한 모든 간선들을 가진 그래프
부분 그래프: 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프 -
인접 정점
인접(Adjacency): 두 개의 정점에 간선이 존재(연결됨)하면 서로 인접해 있다고 한다. 완전 그래프에 속한 임의의 두 정점들은 모두 인접해 있다. -
그래프 경로
경로는 간선들을 순서대로 나열한 것. 경로 중 한 정점을 최대 한 번만 지나는 경로를 단순경로라고 한다. 시작한 정점에서 끝나는 경로를 사이클이라 한다.
# 1. 그래프를 코드로 표현
# 인접 행렬
# V * V 배열을 활용해서 표현
# 갈 수 없다면 0, 있다면 1(or 가중치)을 저장
# 장점:
# 노드 간의 연결 정보를 한 방에 확인 가능
# 행렬곱을 이용해서 탐색이 쉽게 가능
# 간선이 많을수록 유리
# 단점:
# 노드 수가 커지면 메모리가 낭비된다
# 연결이 안된 것도 저장됨
# => 노드 수 + 메모리 제한 반드시 확인할 것!
# 특징: 양방향 그래프는 중앙 우하단 대각선 기준으로 대칭됨
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],
]
# 인접 리스트
# V개의 노드가 갈 수 있는 정보만 저장
# 장점:
# 메모리 사용량이 적다
# 탐색할 때 갈 수 있는 곳만 확인하기 때문에 시간적으로 효율적임
# 단점:
# 특정 노드 간 연결 여부를 확인하는데 시간이 걸림
graph = [
[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=' ')
# 다음 재귀 호출
# dfs: 현재 노드에서 다른 노드들을 확인
# 다른 노드들 == 반복문
for to in range(5):
# 갈 수 없다면 pass
if graph[now][to] == 0:
continue
# 이미 방문했다면 pass
if visited[to]:
continue
dfs(to)
dfs(0)# 인접 행렬 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
path = []
def dfs(now):
# 다음 재귀 호출
# dfs: 현재 노드에서 다른 노드들을 확인
# 다른 노드들 == 반복문
for to in range(5):
# 갈 수 없다면 pass
if graph[now][to] == 0:
continue
# 이미 방문했다면 pass
if visited[to]:
continue
visited[to] = 1
path.append(to)
dfs(to)
# 출발점 초기화
visited[0] = 1
path.append(0)
dfs(0)
print(path)# 인접 리스트 DFS: 재귀
graph = [
[1, 3],
[0, 2, 4],
[1],
[0, 4],
[1, 3],
]
visited = [0] * 5
path = []
def dfs(now):
# 다음 재귀 호출
# 인접 리스트
# 차이점1. 갈 수 없는 곳 조건 필요 없음
# 차이점2. for문 작성 시 인덱스 사용 필요 없음
for to in graph[now]:
# 이미 방문했다면 pass
if visited[to]:
continue
visited[to] = 1
path.append(to)
dfs(to)
# 출발점 초기화
visited[0] = 1
path.append(0)
dfs(0)
print(path)BFS
# 인접 행렬 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
# 시작 노드를 큐에 추가 + 방문 표시
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)# 인접 리스트 BFS
graph = [
[1, 3],
[0, 2, 4],
[1],
[0, 4],
[1, 3],
]
visited = [0] * 5
def bfs(start):
# 시작 노드를 큐에 추가 + 방문 표시
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)Union-Find(Disjoint set)
-
서로소 집합(Disjoint-sets)
: 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다. 다시 말해 교집합이 없다. 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다. 이를 대표자(representative)라 한다. -
상호배타 집합을 표현하는 방법
: 연결리스트 / 트리 -
상호배타 집합 연산
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)]
# 2. find_set: 대표자를 찾아보자
# 부모 노드를 보고, 부모 노드도 연결이 되어 있다면 다시 반복
# 언제까지? 자기 자신이 대표인 데이터를 찾을 때까지
parents = make_set(7)
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)# make 과정: 초기화, 나 자신을 부모로 갖는 단일 그룹 조성
def init(n):
# 각 요소가 자기 자신을 부모로 갖는 일차원 배열을 반환
parent = list(range(n)) # 0 ~ n-1
return parent
# find: x의 그룹의 대표(조상)를 찾아라
def find(x):
if x == parent[x]:
return x
parent[x] = find(parent[x])
return parent[x]
# union: x와 y의 속한 두 그룹을 하나로 합쳐라 (각 대표자들을 찾고 합치기)
def union(x, y):
root_x = find(x)
root_y = find(y)
parent[root_x] = root_y # root_x -> root_y
N = 5 # 요소의 개수
parent = init(N)
union(0, 1)
union(3, 2)
union(0, 4)
print(find(1))
print(find(3))
print("부모 테이블", parent)
멋쟁이 토마토 개발자 🍅