[14, 15일차] 08 그래프 : 08-1 그래프의 표현, 08-2 유니온 파인드

 

함께 푼 문제

[백준 / 그래프] 2178 : 미로 탐색 (python)

 

 

[백준 / 그래프] 20040 : 사이클 게임 (python)

 

 

그래프

노드와 간선으로 이루어진 집합으로 표현되는 자료구조

에지 리스트

• 에지를 중심으로 그래프 표현
• 리스트에 출발 노드, 도착 노드를 저장하여 에지를 표현한다. 가중치가 있는 그래프의 경우 출발 노드, 도착 노드, 가중치를 저장한다.
• 최단 거리 구할 때 유용함

에지 리스트 - 가중치 없는 그래프 / 가중치 있는 그래프

인접 행렬

• 노드 중심으로 그래프 표현
• 2차원 리스트를 자료구조로 이용하여 그래프를 표현
• 가중치가 없는 경우 2차원 리스트에 1을 저장하고, 가중치가 있는 경우 해당 가중치를 저장한다.
• 가중치 값을 바로 확인할 수 있다는 장점 O(1)
• 시간, 공간 복잡도 모두 안좋음

인접 행렬 - 가중치 없는 그래프 / 가중치 있는 그래프

A = [[0 for _ in range(col)] for _ in range(row)] # 2차원 리스트 생성 (깊은 복사)

 

인접 리스트

• 가장 많이 선호하는 방식
• 노드 개수만큼 리스트를 선언하여 그래프 표현
• 시간, 공간 복잡도 좋음

인접 리스트 - 가중치 없는 그래프 / 가중치 있는 그래프

유니온 파인드

union : 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 연산
find : 두 노드가 같은 집합에 속해 있는지를 확인하는 연산

출처 : plainenglish

• 초기값은 인덱스값과 같다.
• 이후 유니온 파인드 연산을 통해 부모 루트를 갱신한다. (위 그림을 보고 부모 루트를 이해할 수 있으면 됨)

파이썬 구현

def find(a):
    if a == parent[a]:
        return a
    else:
        parent[a] = find(parent[a])
        return parent[a]

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

• find는 재귀함수로 구현