다양하게 사용되는 그래프 알고리즘

• 그래프 : 노드(Node)와 간선(Edge)의 정보를 가지고 있는 자료구조

트리와 그래프

그래프의 구현 방법

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

그래프 알고리즘 적용 사례

• 트리 자료구조 : 우선수위 큐(heapq), 서로소 집합(Disjoint Sets)
• 그래프 자료구조
  - 인접 행렬(2차원 배열을 사용) : 플로이드 워셜 알고리즘
  • 인접 리스트(리스트를 사용하는 방식) : 다익스트라 알고리즘

서로소 집합

• 서로소 집합(Disjoint sets) : 공통 원소가 없는 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
• 특징 : 2개의 연산으로 구성됨
  - Union : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
  • Find : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

코드 예시

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

# 값 초기화 하기
'''
v : 노드의 수
e : 합치기 연산 (Union)의 수
'''
v, e = map(int, input().split())
parent = [0] * (v+1)

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

# 합치기 연산 수행
for _ 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("부모 테이블 : ", end='')
for i in range(1, v+1):
    print(parent[i], end=' ')

• Union이 편향적으로 있다면 비효율적일 수 있음 -> 시간 복잡도가 O(V)가 될 수 있다.
• find_parent 함수가 if 재쉬 함수로 연속적으로 구현될 수 있기 때문이다.
• 부모테이블을 바로 갱신하는 방법으로 바꾸기

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

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

• 무방향 그래프에서의 사이클 판별(방향 그래프는 dfs로 판별 가능)
• 같은 루트 노드를 가진 원소끼리 union연산을 수행할 경우 사이클이 발생하는 것임!

# 이코테 273쪽 - 서로소 집합을 활용한 사이클 판별

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

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)

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