Graph Algorithms (그래프 알고리즘)

In [1]:

from IPython.core.display import display, HTML

display(HTML("<style>.container { width:100% !important; }</style>"))

View Source

Graph Algorithms (그래프 알고리즘)¶

Objective¶

1. 서로소 집합 알고리즘
2. 서로소 집합 알고리즘을 통한 사이클 판별
3. Kruskal Algorithm
4. Topology Sort Algorithm
5. Graph Algorithm 예시 문제

1. 서로소 집합 알고리즘¶

1-1. 서로소 집합 정의¶

• 서로소 집합 (Disjoint Sets)란 공통 원소가 없는 두 집합 을 의미합니다.
• 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 입니다.

1-2. 서로소 집합 자료구조의 연산¶

• Union : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산입니다.
• Find : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산입니다.
• 서로소 집합 자료구조는 Union-find 자료구조라고 불리기도 합니다.

1-3. 서로소 집합 자료구조의 동작 과정¶

• 서로소 집합을 구현할 때는 트리 자료구조를 이용하여 집합을 표현합니다.
• 서로소 집합 계산의 알고리즘은 다음과 같습니다.
  1. Union 연산을 확인하여, 서로 연결된 두 노드 A,B 를 확인합니다.
     a. A와 B의 루트 노드 A', B' 를 각각 찾습니다.
     b. A'를 B'의 부모노드로 설정합니다.
  2. 모든 Union 연산을 처리할 때까지 1번의 과정을 반복합니다.

In [2]:

v, e = map(int, input().split())
union_lst = []
for i in range(e):
    a, b = map(int, input().split())
    union_lst.append((a,b))

6 4
1 4
2 3
2 4
5 6

In [4]:

# Find 함수
def find_parent(parent, x):
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return x

# Union 함수
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

In [5]:

# 부모 테이블 초기화
parent = [0] * (v+1)
for i in range(1, v+1):
    parent[i] = i
    

# union 연산 실행
for a, b in union_lst:
    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 = ' ')

각 원소가 속한 집합 :  1 1 1 1 5 5 
부모 테이블 :  1 1 2 1 5 5 

1-4. 기본적인 서로소 집합 자료구조의 단점¶

• 위의 기본적인 형태의 서로소 집합의 자료구조에서는 루트 노드에 즉시 접근할 수 없습니다.
  • 루트 노드를 찾기 위해 부모 테이블을 계속해서 확인하며 거슬러 올라가야 합니다.
  • 위에서 볼수 있듯이 각 원소가 속한 집합 과 부모 테이블이 내용이 서로 다른 것을 볼 수 있습니다.
• 이 경우 Union 연산이 편향되게 이루어져 Find 함수가 비효율적으로 동작합니다.
  • 최악의 경우 (1<-2<-3<-4<-5) 로 서로소 집합 자료구조가 정의될 시, 시간 복잡도가 $O(V)$ 입니다.

1-5. 개선된 서로소 집합 자료구조¶

• Find 함수를 최적화 하기위해 경로 압축 (Path Compression) 을 이용할 수 있습니다.
  • Find 함수를 재귀적으로 호출한 뒤에 _부모 테이블 값을 바로 갱신_합니다.

In [7]:

# Path Compression Find 함수
def find_parent_path_comp(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# Union 함수
def union_parent_path_comp(parent, a, b):
    a = find_parent_path_comp(parent, a)
    b = find_parent_path_comp(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

In [8]:

# 부모 테이블 초기화
parent = [0] * (v+1)
for i in range(1, v+1):
    parent[i] = i
    

# union 연산 실행
for a, b in union_lst:
    union_parent_path_comp(parent, a, b)

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

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

각 원소가 속한 집합 :  1 1 1 1 5 5 
부모 테이블 :  1 1 1 1 5 5 

2. 서로소 집합 알고리즘을 통한 사이클 판별¶

• 서로소 집합은 무방향 그래프(Undirected Graph) 내에서의 사이클을 판별할 때 사용할 수 있습니다.
  • 방향 그래프(Directed Graph) 에서의 사이클 여부는 DFS 를 이용하여 판별할 수 있습니다.
• 사이클 판별 알고리즘
  1. 각 간선을 하나씩 확인하며 두노드의 루트 노드를 확입니다.
     a. 루트 노드가 다르다면 두 노드에 대하여 Union 연산을 수행합니다.
     b. 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것입니다.
  2. 그래프에 포함되어 있는 모든 간선에 대하여 1번의 과정을 반복합니다.

In [9]:

v, e = map(int, input().split())
edges_lst = []
for i in range(e):
    a, b = map(int, input().split())
    edges_lst.append((a,b))

3 3
1 2
1 3
2 3

In [11]:

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

In [12]:

parent = [0] * (v + 1)
for i in range(1, v+1):
    parent[i] = i

In [13]:

cycle = False

for a, b in edges_lst:
    if find_parent(parent, a) == find_parent(parent, b):
        cycle = True
        break
    else:
        union_parent(parent, a, b)
        
if cycle:
    print('사이클이 발생했습니다')
else:
    print('사이클이 발생하지 않았습니다.')

사이클이 발생했습니다

3. Kruskal Algorithm¶

• 신장 트리 란 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미합니다.
  • 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리 의 조건이기도 합니다.
• 최소 신장 트리 란 최소한의 비용으로 구성되는 신장트리를 뜻 합니다.
  • 예를 들어 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우가 있습니다.

• 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 최소 신장 트리 알고리즘 이라고 하며, 대표적으로는 Kruskal Algorithm 이 있습니다.

• Kruskal Algorithm

  • 그리디 알고리즘으로 분류 됩니다.
  • 알고리즘은 다음과 같습니다.
    1. 간선 데이터를 비용에 따라 오름차순 으로 정렬합니다.
    2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인 합니다.
       1) 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킵니다. 2) 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않습니다.
    3. 모든 간선에 대하여 2번의 과정을 반복합니다.
  • 간선의 개수가 E개 일때 $0(ElogE)$ 의 시간 복잡도를 가집니다. 해당 알고리즘에서 가장 오래 걸리는 부분이 간선을 정렬하는 작업이기 때문입니다.

In [14]:

v, e = map(int, input().split())
edges_lst = []
for i in range(e):
    a, b, cost = map(int, input().split())
    edges_lst.append((a, b, cost))

7 9
1 2 29
1 5 75
2 3 35
2 6 34
3 4 7
4 6 23
4 7 13
5 6 53
6 7 25

In [20]:

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

In [21]:

parent = [0] * (v+1)
for i in range(1, v+1):
    parent[i] = i

In [22]:

edges = []
result = 0

for a, b, cost in edges_lst:
    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(a, b)
        result += cost

print(result)

159

4. Topology Sort Algorithm (위상 정렬 알고리즘)¶

• 사이클이 없는 방향 그래프 - DAG (Directed Acyclic Graph) 의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 입니다.
• 전형적인 예시로는 '선수과목을 고려한 학습 순서 설정' 이 있습니다.
• 진입차수(Indegree) 란 특정한 노드로 '들어오는' 간선의 개수를 의미합니다.
• 진출차수(Outdegree) 란 특정한 노드에서 '나가는' 간선의 개수를 의미합니다.

• 위상 정렬 알고리즘은 다음과 같습니다.

  1. 집입차수가 0인 노드를 큐에 넣습니다.
  2. 큐가 빌 때까지 다음의 과정을 반복합니다.
     a. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거합니다.
     b. 새롭게 진입차수가 0이 된 노드를 큐에 넣습니다.

• 결과적으로 각 노드가 큐에 들어온 순서가 위상정렬을 수행한 결과 입니다.

• 위상 정렬에서는 여러 가지 답이 존재 할수 있습니다.
  • 매 단계에서 큐에 새롭게 들어오는 원소가 2개 이상인 경우 여러가지 답이 존재합니다.

• 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재 하는 것을 의미합니다.

  • 사이클에 포함된 원소 중에서 어떠한 원소도 큐에 들어가지 못합니다.

• 간선의 개수 : E, 노드가 V 일때 시간복잡도는 $0(V+E)$ 입니다. 위상정렬을 수행할때에는 모든 노드를 확인하고, 해당 노드에 연결된 간선을 차례대로 제거하기 때문입니다. 결과적으로 모든 간선과 노드를 확인한다는 측면에서 $0(V+E)$의 시간이 소요됩니다.

In [23]:

v, e = map(int, input().split())
edge_lst = []
for i in range(e):
    a, b = map(int, input().split())
    edge_lst.append((a,b))

7 8
1 2
1 5
2 3
2 6
3 4
4 7
5 6
6 4

In [25]:

indegree = [0] * (v+1)
graph = [[] for _ in range(v+1)]

In [26]:

for a, b in edge_lst:
    graph[a].append(b)
    indegree[b] += 1

In [27]:

from collections import deque

def topology_sort(indegree, graph):
    result = []
    q = deque()
    
    for i in range(1, v+1):
        if indegree[i] == 0:
            q.append(i)
            
    while q:
        
        now = q.popleft()
        result.append(now)
        
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)
    return result

In [28]:

print(topology_sort(indegree, graph))

[1, 2, 5, 3, 6, 4, 7]

5. Graph Algorithm 예시 문제¶

5-1. 팀 결성¶

• https://github.com/ndb796/python-for-coding-test 참고
• 서로소 집합 알고리즘

In [29]:

n, m = map(int, input().split())
oper_lst = []

for _ in range(m):
    oper, a, b = map(int, input().split())
    oper_lst.append((oper, a, b))

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

In [31]:

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

In [35]:

def solution(n, m, oper_lst):
    parent = [0] * (n+1)
    for i in range(0, n+1):
        parent[i] = i
    
    for oper, a, b in oper_lst:
        if oper == 0:
            union_parent(parent, a, b)
        else:
            if find_parent(parent, a) != find_parent(parent, b):
                print('NO')
            else:
                print('YES')
solution(n, m, oper_lst)

NO
NO
YES

5-2. 도시 분할 계획¶

• https://github.com/ndb796/python-for-coding-test 참고
• Kruskal Algorithm

In [36]:

n, m = map(int, input().split())
edges_lst = []

for _ in range(m):
    a, b, cost = map(int, input().split())
    edges_lst.append((a, b, cost))

7 12
1 2 3
1 3 2
3 2 1
2 5 2
3 4 4
7 3 6
5 1 5
1 6 2
6 4 1
6 5 3
4 5 3
6 7 4

In [44]:

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

In [45]:

parent = [0] * (n+1)
for i in range(1, n+1):
    parent[i] = i

In [46]:

edges = []

for a, b, cost in edges_lst:
    edges.append((cost, a, b))
    
edges.sort()

In [47]:

result = []

for cost, a, b in edges:
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result.append(cost)

In [49]:

print(sum(result)-max(result))

8

5-3. 커리큘럼¶

• https://github.com/ndb796/python-for-coding-test 참고
• Topology Sort Algorithm

In [82]:

n = int(input())

graph = [[] for _ in range(n+1)]
indegree = [0] * (n+1)
time = [0] * (n+1)

for i in range(1, n+1):
    input_lst = list(map(int, input().split()))
    time[i] = input_lst[0]
    for course in input_lst[1:-1]:
        graph[course].append(i)
        indegree[i] += 1

# 5
# 10 -1
# 10 1 -1
# 4 1 -1
# 4 3 1 -1
# 3 3 -1

5 
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1

In [86]:

from copy import deepcopy
result_time = deepcopy(time)

In [88]:

from collections import deque
from copy import deepcopy

def topology_sort():
    q = deque()
    
    for i in range(1, n+1):
        if indegree[i] == 0:
            q.append(i)
    
    while q:
        now = q.popleft()
        
        for i in graph[now]:
            result_time[i] = max(result_time[i], result_time[now] + time[i])
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)
                
    for i in range(1, n+1):
        print(result_time[i])
        
topology_sort()

10
20
14
18
17