Graph에 대한 개념정리 - 3

이번 정리에서는 Graph의 응용문제에 대해서 다뤄보도록 하겠다.

 

Shortest Path

Weighted Graph의 특정 vertex에서 다른 모든 vertex에 이르는 최단거리 path를 구하는 문제
(single source all destination)

예시로 사용하기 위해서 주어지는 weighted graph

이 문제 또한 graph 관련 알고리즘을 적용함으로서 해결할 수 있다. 그렇다면 이에 대해서 알아보도록 하겠다.

 

Shortest Path Algorithm

1. Adjacency Matrix에서 기준 vertex에 해당하는 행(row)을 초기값으로 설정
2. 다음을 (n-2)회 반복
- 아직 방문하지 않은 vertex 중에서 가장 가까운 vertex를 선택
- 해당 vertex를 거쳐서 가는 path가 현재 알려진 path보다 짧으면 수정한다.
(자기자신과 맨 마지막에 남는 요소 하나가 제외되기 때문에 n-1회가 된다.)

(예시문제) 포항을 기준으로 다른 모든 도시에 이르는 최단 거리를 찾아라!

초기의 adjacency matrix, 빈 공간은 무한대를 의미한다.

흐름을 따라가보면서 아래의 배열을 완성시켜 보도록 하자.

 

이외에도 다른 방법으로 해결할 수 있는 알고리즘이 존재한다.

 

Bellman and Ford Algorithm

하지만 위에서 본 알고리즘과 거의 유사하다. 이전은 vertex 위주로 찾았다면 이번에는 edge를 집중적으로 본다는 점에서 그 차이점이 있다. 그냥 이런 개념이 있다는 정도로 알아두고 넘어가도 무방하다.

기준 vertex (v) 에서 다른 모든 vertex에 이르는 shortest path를 찾는 문제

해당 알고리듬을 자연어로 기술하면 아래와 같다.

1. 모든 edge에 대하여 다음 과정을 n-1회 반복한다.
- 그 edge를 거치면, 현재 알려진 length 보다 짧아지면, length를 수정

해당 알고리듬을 코드로 표현하면 아래와 같이 표현할 수 있다.

처리 대상을 vertex 위주로 할 것이냐, edge 위주로 할 것이냐로 구분지을 수 있음을 기억하자.

 

 

Transitive Closure

우리가 어떤 relation에 대해서 transitive 하다는 것은 A->B, B->C 일 때 A->C 임을 인정하는 것을 말한다. 즉, 우리가 그래프에서 vertex 간의 관계를 생각해보면 edge를 통해 서로 직접 연결되는 Vertex도 있고, 직접적으로 연결되지는 않고 connected 관계를 가지는 vertex일수도 있다. 그런데 마찬가지로 graph 상에서 vertex A와 B가 서로 직접적으로 연결되어 있고, B와 C가 직접적으로 연결되어 있다면 A와 C도 Connected 관계를 서로 가지게 됨을 결론 지을 수 있다. 그래서 이 내용을 기반으로 다음의 개념들을 다뤄보도록 하겠다.

1. Adjacency Matrix
2. Transitive Closure
3. Reflexive transitive closure

1. Adjacency Matrix(A)

Vertex 간에 edge가 존재하는 경우 1, 아니면 0

즉, 직접적인 연결을 가지는 경우에만 1을 할당한다.

2. Transitive Closure(A+)

Vertex 간에 path가 존재하는 경우 1, 아니면 0

즉, 간접적인 연결만을 가지더라도 1을 할당하게 된다.

3. Reflexive Transitive closure(A*)

자신과의 path도 고려한 transitive closure

즉, 자기 자신과의 관계도 인정하는 개념에 해당한다. 2번 개념과 쉽게 혼동할 수 있을 정도로 작은 차이이니 이를 잘 기억해야 한다.

 

해당 개념들을 실제로 표현해보면 아래와 같이 표현할 수 있다.

직접 작성해보면서 이해를 확인할 수 있도록 하자! 

 

그래서 이러한 개념을 통해서 단순한 직접 연결 뿐만 아니라 간접 연결에 대한 정보가 필요한 문제를 풀이함에 있어서 해당 개념들을 유용하게 활용할 수 있을 것이다. 그러니 해당 개념들을 개념적으로 잘 정리하고 기억해둘 수 있도록 하자.