8. 기타 그래프 이론

hiworld·2022년 6월 24일
0
post-thumbnail

📌 1. 서로소 집합 자료구조

1. 서로소 집합 자료구조

  • 서로소 집합 자료구조의 두 연산

    • 합집합(Union) : 두 원소의 부모 노드를 동일하게 만듦.

    • 찾기(Find) : 특정한 원소의 루트 노드를 찾음. 즉 특정한 원소가 속한 집합을 알려줌.

🎨 서로소 집합 자료구조 구현 코드 - find에 경로 압축 사용

def find(parent, x):
  if parent[x] != x:
    '''
    자신이 루트 노드가 아니라는 의미. 즉, 부모 노드가 있음!
    이 부모 노드에 대해 재귀적으로 find를 호출하다 보면 루트 노드까지 찾아낼 수 있음.
    '''
    parent[x] = find(parent, parent[x])
    # 호출하면서 부모테이블에 루트 노드를 바로바로 기록 -> 경로 압축 :)
  return parent[x]

def union(parent, a, b):
  a = find(parent, a) # a의 루트 노드 찾기
  b = find(parent, b) # b의 루트 노드 찾기
  '''
  둘의 루트 노드가 같다면, 이미 같은 집합 안에 있다는 소리니까 합집합 연산 필요 X.
  BUT 다르다면 합집합 연산 수행.
  '''
  if a < b:
    parent[b] = a
  else:
    parent[a] = b

# v: 노드의 개수, e: 간선의 개수
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, a, b)

# 최종적으로, 각 원소가 속한 루트 노드, 즉 집합 출력
# 같은 수가 출력되면 같은 집합. 다른 수는 서로소 집합.
for i in range(1, v + 1):
  print(find(parent, i), end = ' ')

🎨 실행 결과

6 4
1 4
2 3
2 4
5 6
1 1 1 1 5 5 

-> 즉, {1, 2, 3, 4}, {5, 6} 이렇게 두 개의 집합이 존재

2. 서로소 집합 자료구조의 활용

  • 무방향 그래프에서 사이클이 존재하는지 여부를 판단할 때 사용

  • 사이클 판별 알고리즘 : 모든 간선에 대해 연결된 두 노드의 루트 노드 확인 (Find)

    1. 루트 노드가 서로 다르다면, 두 노드에 대해 Union 연산 수행

    2. 루트 노드가 같다면, 사이클(Cycle)이 존재한단 의미

      => 즉, 위의 서로소 집합 자료구조 구현 코드에서 모든 간선에 대해 Union 연산을 수행하던 부분을, 먼저 루트 노드를 찾기 위한 Find 연산을 수행한 뒤에 다르면 Union 연산을 수행하고 같으면 종료하는 코드로 수정하면 끝 :)

🎨 서로소 집합 자료구조를 활용한 사이클 판별 알고리즘 구현

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

def union(parent, a, b):
  a = find(parent, a)
  b = find(parent, b)
  if a < b:
    parent[b] = a
  else:
    parent[a] = b

# v: 노드의 개수, e: 간선의 개수
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, a) == find(parent, b):
    cycle = True
    break
  # 루트 노드가 동일하지 않다면 Union 연산 수행
  else:
    union(parent, a, b)

if cycle:
  print("사이클 존재 O")
else:
  print("사이클 존재 X")

🎨 실행 결과

5 5
1 2
2 3
3 5
4 5
2 4
사이클 존재 O

📌 2. 최소 신장 트리 알고리즘

1. 최소 신장 트리

  • 신장 트리

    • 그래프에서 모든 노드가 연결되고 사이클이 존재하지 않는 부분 그래프

    • 이는 트리의 조건이기도 하기 때문에 신장 '트리'라고 부름

  • 최소 신장 트리

    • 최소한의 비용으로 이루어진 신장 트리

    • 최소 신장 트리의 간선의 개수 = 노드의 개수 - 1

2. 크루스칼 알고리즘

  • 대표적인 최소 신장 트리 알고리즘

  • 그리디 알고리즘으로 분류

  • 동작 과정

    1. 간선을 비용에 따라 오름차순으로 정렬

    2. 모든 간선에 대해
      -> 현재의 간선이 사이클을 발생시키지 않으면(즉, 루트 노드가 다르다면) Union 연산을 수행하고 최소 신장 트리에 포함(비용 증가시킴).
      -> 사이클이 발생하면(즉, 루트 노드가 같다면) 신장 트리에 포함시키지 X.

  • 시간 복잡도 : O(ElogE)

    • E : 노드의 개수

    • 크루스칼 알고리즘에서 가장 많은 시간이 소요되는 부분은 간선이 오름차순 정렬되는 부분. 기본 라이브러리를 사용하면 N개의 데이터를 정렬하기 위한 시간 복잡도는 O(NlogN). 따라서 이 경우엔 O(ElogE)가 됨.

🎨 크루스칼 알고리즘 구현

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

def union(parent, a, b):
  a = find(parent, a)
  b = find(parent, b)
  if a < b:
    parent[b] = a
  else:
    parent[a] = b

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

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

edges = [] # 간선 정보 일단 여기에 저장. 정렬 먼저 해야하니까!
result = 0 # 최소 신장 트리 총 비용
count = 0 # 현재까지 최소 신장 트리에 포함된 간선의 개수

for i in range(e):
  a, b, cost = map(int, input().split())
  # 리스트의 구성 요소가 튜플이면, sort()를 할 경우에 튜플의 첫째 원소 -> 둘째 원소 -> ... 순으로 자동 정렬
  edges.append((cost, a, b))

# 간선을 비용 기준 오름차순 정렬
edges.sort()

for edge in edges:
  cost, a, b = edge
  # 두 노드의 루트 노드가 다르면 사이클이 발생하지 않는다는 의미 -> Union 연산, 최소 신장 트리에 포함
  if find(parent, a) != find(parent, b):
    union(parent, a, b)
    result += cost
    count += 1
    # 최소 신장 트리의 간선의 개수 = 노드의 개수 - 1
    # 이므로 이렇게 되면 더이상 간선 더 확인해볼 필요 X
    if count == v - 1:
    	break

print(result)

최소 신장 트리의 간선의 개수 = 노드의 개수 - 1 임을 알면, 굳이 주어진 모든 간선을 확인해 볼 필요가 없다 :-)

🎨 실행 결과

3 3
1 2 23
2 3 13
1 3 25
36

📌 3. 위상 정렬(Topological Sort)

  • 사이클이 없는 방향 그래프(DAG, Direct Acyclic Graph)에서 각 노드의 선행 순서를 위반하지 않도록 순서대로 나열하는 것

  • [참고] 진입차수(Indegree) <-> 진출차수(Outdegree)

  • 스택(DFS)을 사용하여 구현하는 방법과 큐를 사용하여 구현하는 방법 존재

  • 답이 여러 개일 수 있음. B/C 한 단계에서 큐에 삽입하는 원소가 2개 이상일 경우 어느 원소를 먼저 삽입하든 상관 X

  • 만약, 모든 노드를 방문하기 전에 큐가 빈다면 사이클이 존재한다는 뜻. 따라서 위상 정렬 불가.

  • 시간 복잡도 : O(V + E)

    • B/C 모든 노드, 모든 간선을 한 번씩만 처리

🎨 위상 정렬 구현 - 큐 사용

from collections import deque

# v: 노드의 개수, e: 간선의 개수
v, e = map(int, input().split())
# 모든 노드에 대한 진입차수를 0으로 초기화
indegree = [0] * (v + 1)
graph = [[] for _ in range(v + 1)]

for _ in range(e):
  # a: 출발 노드, b: 도착 노드
  a, b = map(int, input().split())
  graph[a].append(b)
  # b의 진입차수는 1 증가
  indegree[b] += 1

def topology_sort():
  result = [] # 결과 저장할 리스트
  q = deque()
  # 맨 먼저, 진입차수가 0인 모든 노드를 큐에 삽입
  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 # 진입차수 1 빼기
      # 새롭게 진입차수가 0이 된 노드는 큐에 삽입
      if indegree[i] == 0:
        q.append(i)

  for i in result:
    print(i, end = ' ')

topology_sort()

🎨 실행 결과

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

[참고]

profile
바쁘게 살아 보자!

0개의 댓글