섹션 6. 그래프(Graph)

그래프의 기본

유니온 파인드 : 그래프의 사이클이 생성되는지 판별되는 알고리즘

 

위상 정렬

조건

1. 사이클이 없다
2. 방향이 있는 그래프이다.

노드를 정렬해줌, 정렬 결과가 꼭 1개가 아니다.

사용 예시) 수강신청, 롤 아이템 트리등 방향이 있어야 한다.

 

다익스트라 : 시작점이 있고 다른 모든 노드로 가는 최단거리 알고리즘

단, 음수 간선이 있으면 안된다.

 

벨만-포드 : 음수 간선이 있어도 괜찮다. 주로 음수 사이클이 있는지 구할때 사용

ex) 시간 여행, 웜홀등 워프

 

플로이드-워셜 : 시작점이 없는 임의의 모든 노드에서의 최단거리 알고리즘

ex) 모든 도시간의 최단거리를 구하기, 모든 도시를 가는데 최소 시간

 

최소 신장 트리(MST) : 그래프에서 최소의 가중치 합으로 노드를 연결 할 수 있게 해주는 알고리즘으로 사이클이 없다. 유니온 파인드 이용

그래프의 표현

그래프를 구현하는 방법은 3가지가 있다.

1. 에지 리스트 : 에지를 중심으로 표현

에지 리스트로 가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하기 떄문에 배열의 행은 2개면 충분하다.

 

 

Tip) 방향이 없는 그래프라면 [1, 2], [2, 1]은 같다.

 

에지 리스트로 가중치가 있는 그래프는 3번째 행에 가중치를 저장하면 된다.

 

단점으로는 특정 노드와 관련이 있는 에지를 탐색하기가 쉽지 않다.

에지 리스트는 벨만 포드나 크루수칼 알고리즘에 사용하며, 노드 중심 알고리즘에는 잘 사용하지 않는다.

2. 인접 행렬 : 2차원 배열을 자료구조로 사용하여 그래프를 표현

ex) 노드가 5 → [5][5]

 

인접 행렬로 가중치가 없는 그래프 표현하기

가중치가 없기 때문에 값은 1을 넣어준다.

 

인접 행렬로 가중치가 있는 그래프 표현하기

가중치만 넣어주면 된다.

 

인접 행렬을 이용한 그래프 구현은 쉽다.

두 노드를 연결하는 에지의 여부와 가중치 값은 배열에 직접 접근하면 바로 확인할 수 있는 것도 장점이다.

하지만 노드와 관련되어 있는 에지를 탐색하려면 N번 접근해야 하므로 노드 개수에 비해 에지가 적을 때에는 공간 효율성이 떨어진다.

 

ex) A[3][n] → 1 ~ n 접근, n이 10만인 경우등 100 이상인 경우 공간 효율성이 점점 떨어진다.

 

인접 행렬은 노드 개수에 따라 사용 여부를 적절하게 판단하는 능력도 필요하다.

Tip) 노드가 3만개가 넘으면 자바 힙 스페이스(java heap space)에러가 발생한다.

3. 인접 리스트

인접 리스트(adjacency list)는 arraylist로 그래프를 표현한다. 노드 개수만큼 arraylist를 선언한다.

 

인접 리스트로 가중치 없는 그래프 표현하기

ArrayList는 가변적이라는 특징을 이용함

 

인접 리스트로 가중치 있는 그래프 표현하기

 

가중치가 있는 경우 자료형을 클래스로 사용한다.

아래의 경우 node 클래스를 선언하여 ArrayList에 사용하였다.

 

ex) a[3].add(new node(4, 13))

 

그래프 구현은 복잡한편이지만 노드와 연결되어 있는 에지를 탐색하는 시간은 매우 뛰어나며, 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러도 발생하지 않는다. 이런 장점으로 실제 코딩 테스트에서 인접 리스트를 이용한 그래프 구현을 선호한다.

 

유니온 파인드

 

유니온 파인드(union-find)는 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘이다.

 

union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산으로, 노드 a, b가 a ∈ A, b ∈ B 일때 union(a, b)는 A∪B 이다.

find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산이다. 노드 a가 a ∈ A일때 find(a)는 A 집합의 대표 노드를 반환한다.

 

유니온 파인드의 알고리즘 구현 방법

1. 1차원 배열을 이용한다. 각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스 값으로 초기화

2. 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산을 수행

Tip) union 연산을 할때 항상 대표노드끼리 연결한다.

 

3. find 연산은 자신이 속한 집합의 대표 노드를 찾는 연산이다. find 연산은 단순히 대표 노드를 찾는 역할만 하는 것이 아니라 그래프를 정돈하고 시간 복잡도를 향상시킨다.

 

find 연산의 작동 원리

1. 대상 노드 배열에 index값과 value값이 동일한지 확인
2. 동일하지 않으면 value 값이 가리키는 index 위치로 이동
3. 이동 위치의 index 값과 value값이 같은 때까지(대표 노드 찾을 때까지) 과정 1, 2를 반복, 반복과정은 재귀 함수로 구현
4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 루트 노드값으로 변경

한 번의 find 연산을 이용해 모든 노트가 루트 노드에 직접 연결되는 형태로 변경되는 것을 볼 수 있다. 이러한 형태로 변경되면 이후 find 연산이 진행될 때 경로 압축의 효과가 나타난다.

경로 압축의 효과로 실제 그래프에서 여러 노드를 거쳐야 하는 경로에서 그래프를 변형해 더 짧은 경로로 갈 수 있도록 함으로써 시간 복잡도를 효과적으로 줄이는 방법이 나타난다.

 

위상 정렬(Topological sort)

위상 정렬(topological sort)은 사이클이 없는 방향그래프에서 노드 순서를 찾는 알고리즘이다.

노드 간의 순서를 결정하는 위상 정렬은 사이클이 없어야 한다는 특징을 갖고 있고 시간 복잡도는 O(V(노드 수) + E(에지 수)) 이다. 또한 항상 유일한 값으로 정렬되지 않는다.

 

위상 정렬의 원리

1. 진입 차수는 자기 자신을 가리키는 에지의 개수이다. 인접 리스트형태로 표현
2. 진입 차수 배열을 초기화 해준다.

 

3. 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장한다.

 

다익스트라

다익스트라(dijkstra) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.

출발 노드와 모든 노드간의 최단 거리를 탐색하는 기능을 갖고,사용하기 위해서는 에지는 모두 양수인 특징을 갖는다.

시간 복잡도는 O(E(에지 수)logV(노드 수))이다.

 

다익스트라 알고리즘의 핵심 이론

1. 인접 리스트로 그래프 구현하기

다익스트라 알고리즘은 인접 행렬로 구현해도 좋지만 시간 복잡도 측면 N의 크기가 큰 것을 대비해 인접 리스트를 선택하여 구현하는 것이 좋다.

 

2. 최단 거리 배열을 초기화

   출발 노드는 0, 이외의 노드는 모두 ∞으로 초기화, ∞은 적당히 큰수 ex) 987654321

3. 값이 가장 작은 노드 고르기

4.최단 거리 배열 업데이트

1. 저장해 놓은 연결 리스트를 이용해 현재 선택된 노드의 에지를 탐색, 업데이트
2. 연결 노드의 최단 거리는 두 값중 더 작은 값으로 업데이트
3. Min(선택 노드의 최단 거리 배열의 값 + 에지 가중치, 연결 노드의 최단 거리 배열의 값)

5. 과정 3, 4를 반복 최단 거리 배열 완성

   과정 4에서 선택 노드가 될 때마다 다시 선택되지 않도록 방문 배열을 만들어 처리

다익스트라 알고리즘은 출발 노드와 그외 노드 간의 최단 거리를 구하는 알고리즘이고, 에지는 항상 양수여야 한다는 제약 조건이 있다. 실제로 완성된 배열은 출발 노드와 이외의 모든 노드 간의 최단 거리를 표현함으로 꼭 기억하자

 

벨만-포드 (Bellman-Ford)

벨만-포드(bellman-ford-moore)알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.

 

특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 탐색하는 기능을 갖고,

음수 가중치 에지가 있어도 수행할 수 있다는 특징과 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다는 특징이 있다.

시간 복잡도는 O(V(노드 수)E(에지 수)) 이다.

 

벨만-포드의 핵심 이론

1. 에지리스트로 그래프를 구현하고 최단 경로 리스트 초기화
   1. 에지를 중심으로 동작하므로 그래프를 에지 리스트로 구현
      1. edge 클래스는 일반적으로 노드 변수 2개(start, end)와 가중치(w) 변수로 구성
   2. 최단 경로 리스트를 출발 노드는 0, 나머지 노드는 무한대로 초기화

2. 모든 에지를 확인해 정답 리스트 확인하기

1. 최단 거리 리스트에서 업데이트 반복 횟수는 노드 개수 -1
2. 노드 개수가 N이고, 음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 가수는 N -1이다.
3. 업데이트 반복 횟수가 K라면 해당 시점에 정답 리스트의 값은 시작점에서 K개의 에지를 사용했을 때 각 노드에 대한 최단 거리이다.

업데이트 조건과 방법

D[s] ≠∞ 이며 D[e] > D[s] + w일 때 D[e] + w로 리스트 값을 업데이트한다.

 

음수 사이클이 없을 때 N -1번 에지 사용 횟수를 반복하면 출발 노드와 모든 노드 간의 최단 거리를 알려 주는 정답 리스트가 완성된다. 이렇게 완성 후 마지막으로 그래프에 음수 사이클이 있는지 확인해야 한다.

 

3. 음수 사이클 유무 확인하기

1. 모든 에지를 한번씩 다시 사용해 업데이트가 되는 노드가 발생하는지 확인
2. 업데이트시 음수 사이클이 있는 경우
   1. 과정 2에서 도출한 정답 리스트가 무의미하고, 최단 거리를 찾을 수 없는 그래프라는 뜻이 된다.

1. 최단거리 N -1에지 횟수 업데이트
2. 한번 더 업데이트 시도해서 업데이트 되면 최단거리 존재하지 않음, 음수사이클 존재

플로이드 - 워셜 (Floyd-Warshall)

플로이드 - 워셜 (floyd-warshall) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.

 

모든 노드 간에 최단 경로를 탐색하는 기능을 갖고있다.

음수 가중치 에지가 있어도 수행할 수 있으며, 동적 계획법의 원리를 이용해 알고리즘에 접근한다는 특징이 있다.

시간 복잡도는 O(V^3)이다. → 일반적으로 n = 200, 100 주어짐

 

플로이드-워셜의 핵심 이론

 

A 노드에서 B노드까지의 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로이다.

플로이드-워셜 점화식

 

D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

 

플로이드 -워셜 알고리즘 구현 방법

1. 리스트 선언하고 초기화하기
   1. D[S][E]는 노드 S에서 노드 E까지의 최단 거리를 저장하는 리스트로 정의
   2. S와 E의 값이 같은 칸은 0, 다른 칸은 ∞로 초기화
   3. S == E는 자기 자신에게 가는데 걸리는 최단 경로값을 의미한다

2. 최단 거리 리스트에 그래프 데이터 저장하기

1. 출발노드 S, 도착 노드 E, 가중치 W 일 때 D[S][E] = W로 리스트에 입력
2. 플로이드-워셜 알고리즘은 그래프를 인접 행렬로 표현함

3. 점화식으로 리스트 업데이트

1. 점화식을 3중 for문의 형태로 반복하면서 리스트 값을 업데이트

플로이드-워셜 알고리즘

 

for 경유지 K (1 ~ n)

   for 출발 노드 S(1 ~ n)

      for 도착 노드 E (1 ~ n)

         D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

 

최소 신장 트리(MST)

최소 신장 트리(minimum spanning tree)란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다.

MST

1. 크루스칼
2. 프림

최소 신장트리의 특징

1. 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.
2. N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N - 1개

최소 신장 트리의 핵심 이론

 

1. 에지 리스트로 그래프를 구현하고 유니온 파인트 리스트 초기화(사이클 판별)

   a. 데이터 노드가아닌 에지 중심으로 저장하므로 인접리스트가 아닌 에지 리스트의 형태로 저장

   b. 유니온 파인드 리스트는 자신의 index로 값 초기화

2. 그래프 데이터를 가중치 기준으로 오름차순 정렬하기

3. 가중치가 낮은 에지부터 연결 시도하기

   a. 가중치가 낮은 에지부터 순서대로 선택해 연결을 시도

   b. 바로 연결이 아닌 연결 했을때 사이클 형성 유무를 find 연산을 이용해 확인후 

        사이클이 형성되지 않을 때만 union 연산을 이용해 두 노드를 연결

4. 과정 3 반복

   a. 전체 노드의 개수가 N개인 경우, 에지의 개수가 N -1 될 때까지 반복

5. 총 에지 비용 출력

   a. 에지의 개수가 N - 1 개가 되면 알고리즘을 종료

   b. 완성된 최소 신장 트리의 총 에지 비용을 출력

최소 신장 트리는 다른 그래프 알고리즘과 달리, 에지 리스트의 형태를 이용해 데이터를 담는다는 특징이 있다. 왜냐하면 에지를 기준으로 하는 알고리즘이기 때문이다. 또한 사이클이 존재하면 안되는 특징 때문에 사이클 판별 알고리즘인 유니온 파인드 알고리즘을 내부에 구현해야 한다.