Do it 알고리즘 코딩테스트 하루코딩 8장 그래프 이론

# 20 그래프

 

그래프는 노드와 엣지로 구성된 집합이다.

노드는 데이터를 표현하는 단위

에지는 노드로 연결

트리도 그래프의 일종

 

유니온 파인드

그래프의 싸이클이 생성되는지 판별

 

위상정렬

조건 싸이클X, 방향O

전후 관계가 있는 노드를 선형으로 정렬

ex) 수강신청 수1 -> 수2

게임 빌드오더

주의 결과가 유일하지 않다.

 

최단거리 알고리즘

다른 모든 노드로 가는 최단거리를 구하는 알고리즘

 

다익스트라

조건 시작점O, 음수간선X

 

벨만포드

조건 시작점O, 음수간선 ok

음수 싸이클이 있는지? 최단거리가 음의 무한대로 간다.

ex) 시간 여행, 웜홀

 

플로이드 워셜

조건 시작점X

모든 노드 쌍의 최단거리

단점 시간복잡도 나쁘다. // 노드의 개수가 작을 때 또는 모든 노드쌍을 구할때 사용

 

최소신장트리 MST

모든 노드를 연결하는데 최소의 가중치 합

그러므로 싸이클이 있으면 안된다. 그래서 유니온 파인드 활용

 

# 21 그래프의 표현

3가지 방법으로 그래프를 표현한다.

에지 중심, 노드 중심 표현으로 나뉜다.

 

1. 에지 리스트

가중치X 그래프 표현 2열 배열 A[N][2] S, E ex) 1 2 은 1->2

가중치O                    3열 배열 A[N][3] S, E, V ex) 1 2 8 은 1-8->2

 

단점

특정 노드와 관련있는 에지 탐색 어려움, 노드 중심이 아니라 에지 중심이므로

그러므로 노드 중심 알고리즘에 사용X // 벨만 포드, 크루스칼 알고리즘은 에지 중심이여서 여기에 사용

 

2. 인접 행렬

2차원 배열, 노드가 5개인 그래프는 5 X 5로 표현

 

가중치X 그래프

 

                    도착노드4

출발 노드3           1

 

가중치O 그래프

                            15

 

단점

노드와 관련되어 있는 에지를 탐색하려면 N번 접근 필요 // 배열 인덱싱 가능하므로 행(start 노드)까지는 바로 접근 가능 A[2][N]

노드의 개수에 비해 에지가 적을 때는 공간 비효율적, 노드의 개수가 많으면 메모리 초과 오류 발생

그러므로 시간복잡도, 공간복잡도 모두 나쁘다.

 

그러므로 인접행렬은 노드의 개수에 따라 적절하게 사용여부 판단

 

3. 인접 리스트

노드 중심 알고리즘이 많고, 인접 행렬로 푸는 것도 인접 리스트로 풀 수 있으므로 코테에서 많이 사용

 

가중치X 그래프 표현

ArrayList<Integer>[N] // 배열

A[3].add(4) // 시작 노드 종료 노드

 

가중치O 그래프 표현

ArrayList<Node>[N]

사용자 정의 클래스

class Node {

int E;

int V;

}

A[3].add(new Node(4, 13)) // 시작 노드 종료 노드 가중치

 

구현은 복잡하지만 그래도 노드와 연관 되어 있는 에지를 탐색하는 시간은 매우 뛰어나며 // 배열이므로 인덱싱하여 접근 속도 빠름,

가변적이여서 공간 효율적, 공간복잡도 작고, 메모리 초과에러 발생X 

 

#22 유니온파인드

유니온 연산 특정 노드 2개를 연결해 1개의 집합으로 묶음

파인드 연산 2개의 노드가 같은 집합에 속해 있는지 판별 // 자신의 대표 노드를 찾음

 

과정

1. 초기화

// 대표 노드 저장 배열

1차원 배열에 자신의 인덱스 값으로 초기화 // 처음에는 연결된 노드가 없으므로 자신이 대표 노드이다.

 

2. union 연산 // 하나의 집합으로 만든다는 것은 노드끼리 연결한다는 뜻

과정

1. 작은 것을 기준으로 한다면 // 기준 선택

union(1, 4) // 1과 4를 연결, 작은 것 기준으로 연결하면 4에 1대입

union(5, 6) // 6에 5대입

 

union 연산은 항상 대표 노드끼리 연결한다.

union(4, 6)

find(4) // 4의 대표 노드 찾아 1

find(6) // 6의 대표 노드 찾아 5

대표노드 (1, 5) 찾아서 연결 // 즉, 5에 1 대입

4와 6을 union 했지만 실제로 1과 5를 연결하여 결과적으로 4와 6이 연결되었다.

 

3. find 연산은 연결되어 있는지(한 집합인지)여부를 판단

find연산 //인덱스와 저장된 값 비교 !=이면 저장된 값 인덱스로 이동해서 ==

 

과정

1. 노드에 index와 value 비교

2. != value에 해당되는 index(노드)로 이동

3. == 일때까지 반복 // 즉, 대표노드 찾을때까지, 재귀함수로 구현

4. 재귀함수를 빠져나오면서 거치는 모든 노드를 대표 노드값으로 변경

 

find 연산은 단순히 대표노드만 찾는 역할을 하는 것이 아니라 그래프를 정돈하여 시간 복잡도를 개선

경로 함축 되며 한번의 이동으로 대표노드를 찾을 수 있어서 시간복잡도 개선 // 여러 노드를 거쳐야 대표 노드를 찾을 수 있는 경로에서 더 짧은 경로로 갈 수 있도록 함으로써

 

# 23 위상졍렬

조건 싸이클X, 방향O

노드를 선형으로 정렬

주의 결과가 유일하지 않다.

 

기능 노드간의 순서 결정, 특징 조건 싸이클 X, 방향 O, 시간복잡도 O(V+E) // 노드의 개수+ 에지의 개수

위상 정렬의 핵심은 진입 차수 // 자기 자신을 가리키는 에지의 개수

 

1. 초기화 // 인접리스트 ArrayList 배열로 원본 그래프 표현, 진입 차수 배열 초기화 // 1이 2, 3을 가리키므로 D[2]++; D[3]++;

2. 진입 차수가 0인 노드 선택하여 정렬 배열에 저장

3. 인접 리스트에서 저장된 노드가 가리키는 노드들의 진입 차수 -1

4. 2, 3반복 모든 노드가 정렬 될 때까지 반복

 

# 24 다익스트라