[이.코.테] 그래프 이론

💡 '서로 다른 개체가 연결되어 있다' or '여러 개의 도시가 연결되어 있다'
⇒ 그래프 알고리즘

 

그래프와 트리

속성	그래프	트리
방향성	방향 그래프 or 무방향 그래프	방향 그래프
순환성	순환 및 비순환	비순환
루트 노드 존재 여부	X	O
노드간 관계성	부모와 자식 관계 X	부모와 자식 관계 O
모델의 종류	네트워크 모델	계층 모델

 

서로소 집합

• union: 하나의 집합으로 합치는 연산
• find: 특정한 원소가 속한 집합을 알려주는 연산

서로소 집합 알고리즘

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

v, e = map(int, input().split())
parent = [0] * (v+1)

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

for i in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)

사이클 판별

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
    else:
        union_parent(parent, a, b)

 

신장 트리

하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

 

최소 신장 트리 (MST: Minimum Spanning Tree)

• E(간선의 개수) = V(노드의 개수) - 1

 

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

• 방향성이 없을 때만 적용 가능
• 시간복잡도: O(ElogE)
• 그리디 알고리즘

1. 간선 데이터 오름차순 정렬
2. 간선 사이클 발생 확인
  a. 사이클 발생 X ⇒ 최소 신장 트리에 포함
  b. 사이클 발생 O ⇒ 최소 신장 트리에 포함하지 않음
3. 모든 간선에 대하여 2번 과정 반복

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

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

 

위상 정렬 알고리즘 (Topology Algorithm)

• 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'
• 시간복잡도: O(V+E)

1. 진입차수가 0인 노드 큐에 삽입
2. 큐가 빌 때까지 다음의 과정 반복
  a. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거
  b. 새롭게 진입차수가 0인 노드 큐에 삽입

from collections import deque

v, e = map(int, input().split())
indegree = [0] * (v+1) # 진입차수 0으로 초기화
graph = [[] for i in range(v+1)]

for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1

def topology_sort():
    result = []
    q = deque()

    for i in range(1, v+1): # 진입차수가 0인 노드 큐에 삽입
        if indegree[i] == 0:
            q.append(i)
		
    while q:
        now = q.popleft()
        result.append(now)
        for i in graph[now]: # 해당 원소와 연결된 노드들의 진입차수 1 빼기
            indegree[i] -= 1
            if indegree[i] == 0: # 새롭게 진입차수가 0이 되는 노드 큐에 삽입
                q.append(i)