그래프 - swkim0128/PARA GitHub Wiki

type: Algorithm archive: false

그래프

그래프는 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결 관계를 표현한다.

  • 정점(Vertex) : 그래프의 구성요소로 하나의 연결점

  • 간선(Edge) : 두 정점을 연결하는 선

  • 차수(Degree) : 정점에 연결된 간선의 수

  • 그래프(Graph) : 노드(Node)와 노드 사이에 연결된 간선(Edge)의 정보를 가지고 있는 자료구조.
    V : 정점의 개수, E : 그래프에 포함된 간선의 개수
    V개의 정점을 가지는 그래프는 최대 V * (V - 1) / 2 간선이 가능
    예) 5개의 정점이 있는 그래프의 최대 간선 수는 10(⇒ 5 * 4 / 2)개이다.

  • 선형 자료구조나 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소들을 표현하기에 용이하다.

그래프 유형

  • 무향 그래프(Undirected Graph)

  • 유향 그래프(Directed Graph)

  • 가중치 그래프(Weighted Graph)

  • 사이클 없는 방향 그래프(DAG, Directed Acyclic Graph)

  • 완전 그래프
    정점들에 대해 가능한 모든 간선들을 가진 그래프

  • 부분 그래프
    원래 그래프에서 일부의 정점이나 간선을 제외한 그래프

인접(Adjacency)

두 개의 정점에 간선이 존재(연결됨)하면 서로 인접해 있다고 한다.

완전 그래프에 속한 임의의 두 정점들은 서로 인접해 있다.

그래프 경로

어떤 정점 A에서 시작하여 다른 정점 B로 끝나는 순회로 두 정점 사이를 잇는 간선들을 순서대로 나열한 것

  • 어떤 정점에서 다른 정점으로 가는 경로는 여러가지일 수 있다.

단순 경로

시작정점과 끝 정점을 제외하고 중복된 정점이 없는 경로

싸이클(Cyclic)

경로의 시작 정점과 끝 정점이 같음

그래프 표현

간선의 정보를 저장하는 방식, 메모리나 성능을 고려해서 결정

인접 행렬 (Adjacent matrix)

V x V 크기의 2차원 배열을 이용해서 간선 정보를 저장

배열의 배열(Reference Array)

인접 리스트(Adjacent List)

각 정점마다 다른 정점으로 나가는 간선의 정보를 저장

간선 리스트(Edge List)

간선(시작 정점, 끝 정점)의 정보를 객체로 표현하여 리스트에 저장

알고리즘 문제를 접했을 때 '서로 다른 개체(혹은 객체)가 연결되어 있다'는 이야기가 있으면 가장 먼저 그래프 알고리즘을 떠올려야 한다.

  • 인접 행렬(Adjacency Matrix) : 2차원 배열을 사용하는 방식
  • 인접 리스트(Adjacency List) : 리스트를 사용하는 방식

서로소 집합

수학에서 서로소 집합이란 공통 원소가 없는 두 집합을 의미.

서로소 집합 자료구조

서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조.

union과 find 이 2개의 연산으로 조작할 수 있다.
union(합집합) 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산.
find(찾기) 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산.

서로소 집합 정보 (합집합 연산)가 주어졌을 때 트리 자료구조를 이용해서 집합을 표현하는 서로소 집합 계산 알고리즘은 다음과 같다.

  1. union (합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
    1. A와 B의 루트 노드 A, B를 각각 찾는다.
    2. A를 B의 부모 노드로 설정한다(B가 A 를 가리키도록 한다.)
  2. 모든 union (합집합) 연산을 처리할 떄까지 1번 과정을 반복한다.

java

makeSet(x)
	p[x] <- x

findSet(x)
	if x == p[x] : return x
	else : return p[x] = findSet(p[x])

union(x, y)
	if findSet(y) == findSet(x) return ;
	p[findSet(y)] = findSet(x)

python

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return x

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선(union 연산)의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1)  # 부모 테이블 초기화

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

# union 연산을 각각 수행
for i in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)

# 각 원소가 속한 집합 출력
print('각 원소가 속한 집합: ', end=' ')
for i in range(1, v + 1):
    print(find_parent(parent, i), end=' ')

print()

# 부모 테이블 내용 출력
print('부모 테이블: ', end='')
for i in range(1, v + 1):
    print(parent[i], end=' ')
# 개선된 경로 압축 기법 소스코드
# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선(union 연산)의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1)      # 부모 테이블 초기화

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

# union 연산을 각각 수행
for i in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)

# 각 원소가 속한 집합 출력
print('각 원소가 속한 집합: ', end='')
for i in range(1, v + 1):
    print(find_parent(parent, i), end=' ')

print()

# 부모 테이블 내용 출력
print('부모 테이블: ', end='')
for i in range(1, v + 1):
    print(parent[i], end=' ')

서로소 집합을 활용한 사이클 판별

서로소 집합은 다양한 알고리즘에 사용될 수 있다. 특히 서로소 집합은 무 방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다는 특징이 있다. 참고로 방향 그래프에서의 사이클 여부는 DFS를 이용하여 판별할 수 있음.

앞서 union 연산은 그래프에서의 간선으로 표현될 수 있다. 따라서 간선을 하나씩 확인하면서 두 노드가 포함되어 있는 지합을 합치는 과정을 반복하는 것만으로도 사이클을 판별할 수 있다.

  1. 각 간선을 확인하며 두 노드의 로투 노드를 확인한다.
    1. 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행한다.
    2. 루트 노드가 서로 같다면 사이클 (Cycle)이 발생한 것이다.
  2. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복한다.
# 노드의 개수와 가선(union 연산)의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1)      # 부모 테이블 초기화

# 부모 테이블 상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i
    
cycle = False       # 사이클 발생 여부

for i in range(e):
    a, b = map(int, input().split())
    # 사이클이 발생한 경우 종료
    if find_parent(parent, a) == find_parent(parent, b):
        cycle = True
        break
    # 사이클이 발생하지 않았다면 합집합(union) 수행
    else:
        union_parent(parent, a, b)

if cycle:
    print("사이클이 발생했습니다.")
else:
    print("사이클이 발생하지 않았습니다.")

신장 트리(Spanning Tree)

하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n - 1개의 간선으로 이루어진 트리

그래프에서 최소 비용 문제

  1. 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리
  2. 두 정점 사이의 최소 비용의 경로 찾기

최소 신장 트리 (Minimum Spanning Tree)

무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

크루스칼 알고리즘(Kruskal Algorithm)

간선을 하나씩 선택해서 MST를 찾는 알고리즘

신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 최소 신장 트리 알고리즘. 대표적인 최소 신장 트리 알고리즘이 크루스칼 알고리즘이다.

  1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
  2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
    1. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
    2. 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
  3. 모든 간선에 대하여 2번의 과정을 반복한다.

java

MST_KRUSKAL(G, w)
	for vertex v in G.V    // G.V : 그래프의 정점 집합
		makeSet(v)           // G.E : 그래프의 간선 집합

	G.E에 포함된 간선들을 가중치 w에 의해 정렬

	for 가중치가 가장 낮은 간선 (u, v) ∊ G.E 선택 (n - 1개)
		if findSet(u) != findSet(v)
			A <- A ∪ {(u, v)}
			union(u, v)

python

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선(union 연산)의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1)      # 부모 테이블 초기화

# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

# 모든 간선에 대한 정보를 입력받기
for _ in range(e):
		a, b, cost = map(int, input().split())
		# 비용순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정
		edges.append((cost, a, b))
!
# 간선을 비용순으로 정렬
edges.sort()

# 간선을 하나씩 확인하며
for edge in edges:
		cost, a, b = edge
		# 사이클이 발생하지 않는 경우에만 집합에 포함
		if find_parent(parent, a) != find_parent(parent, b):
				union_parent(parent, a, b)
				result += cost

print(result)

PRIM 알고리즘

하나의 정점에서 연결된 간선들 중 하나씩 선택하면서 MST를 만들어 가는 방식

  1. 임의 정점을 하나 선택해서 시작
  2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택
  3. 모든 정점이 선택될 때까지 1, 2 과정을 반복

서로소인 2개의 집합(2 disjoint-sets) 정보를 유지

  • 트리 정점들(tree vertices) - MST를 만들기 위해 선택된 정점들
  • 비트리 정점들(non-tree vertices) - 선택 되지 않은 정점들

알고리즘

MST_PRIM(G, r)    // G : 그래프, r : 시작 정점
	result <- 0, cnt <- 0    
	// result : 신장트리 최소비용, cnt : 처리한 정점 수 , visited[] : 최소신장트리 구성에 포함된 정점여부
	for u in G.V
		minEdge[u] <- ∞        // minEdge[] : 각 정점기준으로 다른 정점과의 간선 중 최소비용
	minEdge[r] <- 0          // 시작 정점 r의 최소비용 0 처리 

	while true               // 빈 Q가 아닐동안 반복
		u <- Extract_MIN()     // 방문하지 않은(최소신장트리에 포함되지 않은 정점) 최소비용 정점 찾기
		visited[u] <- true     // 방문 처리
		result <- result + minEdge[u];

		if (++cnt == N) break; // 모든 정점이 다 연결되었으면 최소신장트리 완성.

	for v in G.Adj[u]        // u의 인접 정점들
		if visited[v] == false and w(u, v) < minEdge[v]  
		// u에서 v로의 비용이 v의 최소비용보다 작다면 갱신
			minEdge[v] <- w{u, v)
	return result
end MST_PRIM

최단 경로 알고리즘

최단 경로 정의 : 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로

하나의 시작 정점에서 끝 정점까지의 최단 경로

다익스트라(dijkstra) 알고리즘

  • 음의 가중치를 허용하지 않음.

벨만-포드(Bellman-Ford) 알고리즘

  • 음의 가중치 허용

모든 정점들에 대한 최단 경로

플로이드-워샬(Floyd-Warshall) 알고리즘

Dijkstra 알고리즘

시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다.

탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사하다.

s : 시작 정점, A : 인접 행렬, D : 시작정점에서의 거리
V : 정점 집합, U : 선택된 정점 집합

Dijkstra(s, A, D)
	U = {s};

	for 모든 정점 v
		D[v] <- A[s][v]

	while U != V
		D[w]가 최소인 정점 w ∊ V-U 를 선택
		U <- U ∪ {w}
		for w에 인접한 모든 미방문 정점 v
			D[v] <- min(D[v], D[w] + A[w][v])

위상 정렬(Topology Sort)

정렬 알고리즘의 일종. 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 위상 정렬이란 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'이다.

현실 세계에서 위상 정렬을 수행하게 되는 전형적인 예시로는 '선수과목을 고려한 학습 순서 설정'을 들 수 있다.

  • 진입차수(Indegree) : 특정한 노드로 '들어오는' 간선의 개수를 의미.

  1. 진입차수가 0인 노드를 큐에 넣는다.

  2. 큐가 빌 때까지 다음의 과정을 반복한다.

    1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
    2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
from collections import deque

# 노드의 개수와 간선의 개수를 입력받기
v, e = map(int, input().split())
# 모든 노드에 대한 진입 차수는 0으로 초기화
indegree = [0] * (v + 1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트(그래프) 초기화
graph = [[] for i in range(v + 1)]

# 방향 그래프의 모든 간선 정보를 입력받기
for _ in range(e):
		a, b = map(int, input().split())
		graph[a].append(b)  # 정점 A에서 B로 이동 가능
		# 진입 차수를 1 증가
		indegree[b] += 1

# 위상 정렬 함수
def topology_sort():
		result = []  # 알고리즘 수행 결과를 담을 리스트
		q = deque()  # 큐 기능을 위한 deque 라이브러리 사용

		# 처음 시작할 때는 진입 차수가 0인 노드를 큐에 삽입
		for i in range(1, v + 1):
				if indegree[i] == 0:
						q.append(i)

		# 큐가 빌 때까지 반복
		while q:
				# 큐에서 원소 꺼내기
				now = q.popleft()
				result.append(now)

				#해당 원소와 연결된 노드들의 진입차수에서 1 빼기
				for i in graph[now]:
						indegree[i] -= 1

						# 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
						if indegree[i] == 0:
								q.append(i)

		# 위상 정렬을 수행한 결과 출력
		for i in result:
				print(i, end=' ')

topology_sort()
⚠️ **GitHub.com Fallback** ⚠️