6강 - 그래프

목차

1. 그래프 추상 데이터 타입
2. 그래프의 기본 연산
3. 최소 비용 신장 트리
4. 최단 경로와 이행적 폐쇄
5. 작업 네트워크

 

 

1. 그래프 추상 데이터 타입

 

그래프는 이산수학에서도 배웠다시피 오일러의 퀸즈 버그 다리 문제에서 처음 사용되었다고 한다.

 

그래프의 정의 : 그래프는 두 개의 집합 V와 E로 구성된다. V는 정점(vertex), E는 간선(edge)로 이루어진 유한 집합이다.

임의의 그래프 G = (V, E)로 나타낼 수 있으며, 간선을 나타내는 정점의 쌍에 순서가 있거나 없음을 통해 무방향, 방향 그래프로 나눌 수 있다. 예를 들어 트리구조도 그래프라 할 수 있는데 이는 무 방향 그래프라 할 수 있다.

ex) (u,v) 는 무방향 그래프에서 표현, (v, u)와 같은 표현임.

    <u,v>는 유방 향 그래프에서 표현, <v, u>와 다른 표현임

 

완전 그래프 - 모든 정점이 자신을 제외한 모든 정점과의 간선을 가지고 있는 그래프

       무방향 그래프 - n개의 정점과 n(n-1)/2개의 간선을 가짐

       유방향 그래프 - n개의 정점과 n(n-1) 개의 간선을 가짐

 

단순 경로 : 경로에서 처음과 마지막을 제외한 모든 정점들이 서로 다른 경로

 

연결 그래프 : 모든 정점 사이에 경로가 존재하는 그래프(한 정점에서 모든 정점과 연결되어 있지 않아도 됨 ex) tree )

 

연결 요소 : 최대 연결 그래프

 

강력 연결 : 방향 그래프에서 V(G)에 속한 서로 다른 두 정점 u,v의 모든 쌍에 대해서, u에서 v로, 또한 v에서 u로의 방향                경로가 존재하면 그 방향 그래프는 강력 연결되었다고 한다.

 

강력 요소 : 강력 연결된 최대 부분 그래프

 

그래프의 표현 방법

 

그래프는 인접 행렬, 인접 리스트로 표현이 가능하다.

 

인접 행렬로 표현 -> 임의의 두 정점 i, j 를 연결하는 간선이 존재하는지 바로 확인 가능

ex) 아래와 같이 정점 i, j에 대해 간선이 존재하면 1로, 존재하지 않으면 0으로 표현

	0	1	2	3
0	0	0	1	0
1	0	0	0	1
2	1	0	0	0
3	0	1	0	0

인접 리스트로 표현 -> 간선이 존재하면 체인으로 표현

 

역 인접 리스트 -> 인접 리스트가 진출 차수를 표현한다면 역 인접 리스트는 출입 차수를 표현하는 리스트이다.

 

2. 그래프의 기본 연산

깊이 우선 탐색 - DFS(Depth first search)

출발 정점을 방문 하고, 그 정점으로부터 간선이 있는 정점들 중 방문하지 않은 정점을 선택하여 방문, 이를 더 이상 방문할 정점이 없을 때까지 반복하고, 다시 되돌아와서 위 과정을 반복한다.

따라서 주로 stack을 사용하며 재귀함수로 표현된다.

 

넓이 우선 탐색 - BFS(Breadth first search)

출발 정점을 방문하고 그 정점과 간선이 있는 모든 노드들을 방문한다. 그 후 방문한 모든 노드들과 간선이 있는 모든 노드들을 방문한다. 이 과정을 더 이상 방문할 노드가 없을 때까지 반복한다.

따라서 주로 queue를 사용하여 표현된다.

 

간단히 정리하면 위와 같고 DFS와 BFS는 실제로 많이 구현해 봐야 익숙해 질 수 있는 것 같다.

 

이렇게 DFS, BFS를 통해 연결 요소를 구할 수 있다. (DFS, BFS는 연결된 모든 정점을 방문하는 알고리즘이기 때문)

 

신장 트리

신장 트리란 그래프의 모든 정점을 포함하고, 간선들이 그래프의 간선들로만 이루어진 트리를 말한다.

신장 트리는 DFS와 BFS 두 알고리즘 모두로 만들 수 있는데 둘은 차이가 있다.

직접 그려보며 이해해보자. 알고리즘을 따라가면 쉽게 구할 수 있다.

 

3. 최소 비용 신장 트리

최소 비용 신장 트리란 가중치를 갖는 그래프에서 최소의 비용을 갖는 신장 트리를 의미한다.

 

최소 비용 신장 트리를 구하는 알고리즘은 2가지 방법이 있다.

1. Kruskal 알고리즘 : 가장 가중치가 적은 간선들만 연결 (사이클이 생기면 건너 뜀)
2. Prim 알고리즘 : 첫 정점 부터 차례대로 가지고 있는 간선 중 가중치가 가장 적은 간선을 선택하여 연결
3. Solin 알고리즘 : 모든 정점에서 가중치가 가장 적은 간선들만 연결 후 중복 제거, 반복

Prim 알고리즘은 각 단계에서 결정되는 간선들과 정점들은 트리 구조를 이루고 있음을 알 수 있다.

 

4. 최단 경로와 이행적 폐쇄

 

최단 경로 알고리즘 - Dijkstra Algorithm

 

먼저 이 알고리즘을 사용하려면 단일 시발점/일반적 가중치를 가진 그래프여야 한다.

 

첫 정점에서 시작 -> 정점에 존재하는 모든 간선의 가중치를 계산하여 표에 작성 (이때 아직 간선이 없어 가지 못하거나 방문하지 않은 정점은 거리를 무한대로 표현) -> 모든 정점 중 가중치가 가장 적은 정점을 다음 정점으로 선택 -> 정점에 존재하는 모든 간선의 가중치 계산하여 표에 작성 -> 모든 정점을 방문할 때까지 반복

 

말로 설명하려고 하니 살짝 어려운 것 같지만 실제로 표로 작성해보면 어렵지 않다.

 

코드로 나타내면 아래와 같다.

 

void MatrixWDigraph::ShortestPath(const int n, const inv v){
//dist[j] , 0<=j<n은 v에서 j까지의 최단 경로의 길이이다.
//간선의 길이는 length[i][j]로 주어진다.
	for(int i=; i<n; i++){s[i]=false;dist[i]=length[v][i];} //초기화
    s[v]=true;
    dist[v]=0;
    
    for(int i=0; i<n-2; i++){ //정점 v에서부터의 n-1 경로를 결정
    	int u = Choose (n); //Choose는 s[w]=false이고 
                            //dist[u] 는 dist[u]가 미니멈이 되는 u를 반환
        s[u]=true;
        for(int w=0; w<n; w++){
        	if(!s[w]&&dist[u]+length[u][w]<dist[w])
            	dist[w]=dist[u]+length[u][w];
    }
}

 

위의 알고리즘은 일반적인 가중치를 가졌을 경우에 최단 경로를 구하는 알고리즘이다.

만약 음의 가중치를 가지고 있는 그래프에서 최단 경로를 구하려면 어떻게 해야 할까?

음의 가중치를 가지고 있다면 많은 문제가 발생할 수 있다.

예를 들어 싸이클을 가지고 있는 그래프라면 경로가 -가 나올 수도 있다.

이러한 경우에 최단 경로를 구할 수 있는 알고리즘이 Bellman Ford 알고리즘이다.

 

Bellman Ford 알고리즘

 

이 알고리즘은 동적 프로그래밍(Dinamic Programming) 기법을 사용한다.

알고리즘의 핵심은 다음과 같다. 

음의 가중치를 갖는 간선이 존재하기 때문에 동적 프로그래밍을 통해 모든 경로를 탐색해야 한다.

min(min(직접 가는 경우 , 정점 1개를 거쳐서 가는 경우), 정점 2개를 거쳐서 가는 경우)... 정점 n-1개를 거쳐서 가는 경우)

즉 계속해서 거쳐서 가는 정점의 개수를 늘려가며 기존의 최단 경로와 비교해 갱신해 나가는 알고리즘이다.

코드로 나타내 보면 아래와 같다.

dist_k[u] = min ( dist_k [u], min ( dist_k-1 [i] + length [i][u] )

 

이행적 폐쇄

 

이행적 폐쇄 행렬 - A+로 나타내며 i에서 j로의 경로의 길이가 >0 을 표현한 행렬이다.

 

반사 이행적 폐쇄 행렬 - A*로 나타내며 i에서 j로의 경로의 길이가 >=0 인 점들을 표현한 행렬이다.

 

이행적 폐쇄 행렬의 대각선(i==j) 부분이 모두 1로 채워지면 반사 이행적 폐쇄 행렬임을 쉽게 알 수 있다.

 

5. 작업 네트워크

 

AOV 네트워크 - 노드가 작업 

 

• 정점 i로 부터 정점 j 로의 방향 경로 존재하면 정점 i는 정점 j의 선행자
• 간선 <i,j>가 존재하면 정점 i는 정점 j의 직속 선행자

부분 순서

• 이행적 - 관계 &에 대하여 i&j이고 j&k 이면 i&k이다.
• 비반사적 - 관계 &에 대하여 i&i가 성립하지 않는다.

부분 순서는 이행적이며 비반사적인 선행 관계이다.

 

위상 순서 : i, j에 대하여 네트워크에서 i가 j의 선행자이면, 그래프의 정점에서도 i가 j앞에 있는 선형 순서

 

AOE 네트워크 - 정점이 작업

 

임계 경로 : 시작 정점에서 종료 정점 가지의 최장 경로

임계 작업 : 임계 경로 상의 작업들

 

정점 중심 시간

e(i) = ee [k] -> 사건 k의 가장 이른 발생 시간

l(i) = le [k] - 작업 ai의 기간 -> 사건 l의 가장 늦은 발생시간 

 

즉 ee와 le를 통해 e와 l을 구하고 e==l이면 임계 경로임을 알 수 있다.