[C언어로 쉽게 풀어쓴 자료구조] Chapter11. 그래프 II (2)

11.4 최단 경로

● 최단 경로(shortest path): 정점 i와 j를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로

- DIjkstra 알고리즘은 하나의 시작 정점에서 다른 정점까지의 최단 경로를 구한다.

- Floyd 알고리즘은 모든 정점에서 다른 모든 정점까지의 최단 경로를 구한다.

가중치는 가중치 인접 행렬에 저장돼 있고 u와 v사이에 간선이 없다면 INF가 저장된다.

 

* 인접행렬에서는 간선이 없으면 인접 행렬의 값이 0인 반면 가중치 인접 행렬에서는 실제 가중치가 0일 수 있어서

0의 값이 간선이 없음을 나타내지 못한다. 따라서 INF가 간선이 없음을 나타낸다.

 

 

11.5 Dijkstra의 최단 경로 알고리즘

 

●DIjkstra 알고리즘: 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘

- 집합 S에는 최단 경로가 이미 발견되어 지나온 정점들을 담는다.

- 시작 정점에서 집합 S에 담긴 정점들을 지나 다음 정점으로 가는 최단거리를 기록하는 배열 distance 사용

- 최단거리는 [집합 S에 담기지 않은 정점 중 distance가 가장 작은 정점]을 지나야만 만족 하는데,

그 이유는 다른 정점 w를 지나서 v로 가려고 해도 (정점 u와 w사이의 거리 + w와 v의 사이의 거리)가 distance이고,

정점 u와 w사이의 거리가 이미 u와 v사이의 거리보다 길기 때문이다.

- 따라서 [S에 담기지 않은 정점 중 distance가 가장 작은 정점들을 추가해 나가면서 distance를 갱신]하면

시작 정점에서 모든 정점까지의 최단거리를 구할 수 있다.

 

 

 [집합 S에 담기지 않은 정점 중 distance가 가장 작은 정점]

int choose(int distance[], int n, int found[]){
	int i,min,minpos;
	min = INF;
	minpos = -1;
	for(i=0; i<n;i++){
		if(distance[i]<min && !found[i]){
			min = distance[i];
			minpos=i;
		}
	}
	return minpos;
}// 집합 S에 포함되지 않는 정점 중 distance가 가장 작은 정점 return

 

[S에 담기지 않은 정점 중 distance가 가장 작은 정점들을 추가해나가면서 distance를 갱신]

 

void shortest_path(GraphType *g,int start){
	int i,u,w;
	for(i =0; i<g->n; i++){
		distance[i] = g->weight[start][i];
		found[i] = FALSE;
	} // 초기화
	found[start] = TRUE; // 시작 정점 방문
	distance[start] = 0;
	
	for(i=0;i<g->n;i++){
		print_status(g);
		u = choose(distance, g->n, found);
		found[u] = TRUE;
		for(w=0; w<g->n; w++){
			if(!found[w]){
				if(distance[u] + g-> weight[u][w] < distance[w]){
					distance[w] = distance[u] + g->weight[u][w];
				}
			}
		}
	}
}

 

●DIjkstra의 분석

- n개의 정점이 있다면 주 반복문을 n번, 내부 반복문을 2n번 반복하므로 O(n^2)의 복잡도를 가진다.

 

♠ 424p Quiz

01 

0	1	2	3	4	5	6	7
0	7	*	5	*	2	*	*
0	7	*	5	4	2	6	*
0	6	*	5	4	2	6	8
0	6	7	5	4	2	6	8
0	6	7	5	4	2	6	8
0	6	7	5	4	2	6	8
0	6	7	5	4	2	6	8
0	6	7	5	4	2	6	8

집합 S에 담기는 순서 : 0 - 5 - 4 - 3 - 1 - 6 - 2 - 7

 

 

11.6 Floyd의 최단 경로 알고리즘

 

● Floyd 알고리즘:

그래프에 존재하는 모든 정점 사이의 최단 경로를 한 번에 모두 찾아주는 알고리즘- 2차원 배열 A를 이용하여 3중 반복을 구성한다.- 인접 행렬 weight는 1) i==j 이면 weight[i][j] = 02) 두 정점 사이에 간선이 존재하면 weight[i][j] = 간선(i, j)의 가중치3) 두 정점 사이에 간선이 존재하지 않으면 weight[i][j] = ∞   (행렬에 표시는 *으로 할 것이다)로 초기화 한다.

 

- Ak[i][j]을 0부터 k까지의 정점만을 이용한 정점 i에서 j까지의 최단 경로라고 하면

우리의 최종 목표는 0부터 n-1까지의 모든 정점을 활용한 최단 경로이기 때문에 An-1[i][j]가 될 것이다.

 

초기화된 weight를 A-1이라 하고 Ak-1을 0에서 k-1까지의 정점만을 이용한 최단 거리 배열이라고 생각하자.

이제 k까지의 정점을 사용하려고 하면,

1) 정점 k를 거치지 않고 i에서 j로 가는 거리가 최단거리일 때

- 이미 0에서 k-1까지는 최단 거리 배열이고 k보다 큰 정점은 통과하지 않으므로 최단 거리는 Ak-1[i][j]

2) 정점 k를 거쳐서 i에서 j로 가는 거리가 최단거리 일 때

- i에서 k까지의 최단거리 Ak-1[i][j]에다가 k에서 j까지의 최단 거리 Ak-1[k][j]를 더한 값

 

따라서 Ak-1[i][j]와 Ak-1[i][j] +  Ak-1 [k][j] 중 작은 값이 Ak[i][j]가 될 것이다.

 

이를 삼중 for문으로 나타내면 다음과 같다.

for(k=0; k<g->n; k++){
		for(int i=0; i<g->n; i++){
			for(int j=0; j<g->n; j++){
				if(A[i][k]+A[k][j]<A[i][j]){
					A[i][j] = A[i][k] + A[k][j];
				}
			}
		}
		print_A(g);
    }

 

floyd 전체 코드는 다음과 같다.

void floyd(GraphType *g){
	int i,j,k;
	for(i =0; i<g->n;i++){
		for(j=0; j<g->n;j++){
			A[i][j] = g->weight[i][j];
		}
	}
	print_A(g); // 가중치들을 A-1에 넣어주기
	
	for(k=0; k<g->n; k++){
		for(int i=0; i<g->n; i++){
			for(int j=0; j<g->n; j++){
				if(A[i][k]+A[k][j]<A[i][j]){
					A[i][j] = A[i][k] + A[k][j];
				}
			}
		}
		print_A(g);
	}
	
}

 

●Floyd 알고리즘의 분석

- 모든 정점 쌍의 최단 경로를 구하는 알고리즘을 두 개의 정점 사이의 최단 경로를 구할 수 있는 Dijkstra로 구할 경우

Dijkstra를 n번 반복해야 하므로 O(n^2) * n 이어서 O(n^3)이 된다.

- Floyd는 삼중 반복문을 사용하므로 O(n^3)이어서 두 알고리즘의 큰 차이는 없다.

다만 Floyd의 알고리즘이 간결한 반복문이어서 모든 정점 간의 최단 경로를 찾는데 용이하다.

 

♠ 430p Quiz

01

A-1	0	1	2
0	0	3	1
1	2	0	4
2	5	1	0

A0	0	1	2
0	0	3	1
1	2	0	3
2	5	1	0

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

 

11.7 위상 정렬

● 위상 정렬: 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것

* 선행: 방향 그래프의 간선 <u,v>에서 정점 u는 정점 v를 선행한다.

 

- 진입차수가 0인 정점을 선택 후 선택된 정점과 여기에 부착된 모든 간선을 삭제

- 진입 차수 0인 정점의 선택과 삭제 과정이 반복되어 모든 정점이 선택, 삭제 되면 알고리즘 종료

*진입 차수 0 인 정점이 남은 정점들 중에 존재하지 않는다면 알고리즘의 비정상적 종료

 

ex)위의 그림에서 진입차수가 0인 노드1과 연결된 간선들이 삭제되면 진입차수가 0인 노드는 노드3과 노드2이다.

 

위상 순서: 위상 정렬 시 선택되는 정점의 순서

 

 

● 위상 정렬 알고리즘의 구현

- in_degree라는 1차원 배열에 각 정점의 진입 차수(= in_degree[i]는 정점i로 들어오는 간선의 개수)를 기록

- 진입 차수가 0인 정점이 그래프에서 제거되면 인접한 정점의 in_degree[i]도 1 감소

- 위의 예시에서 노드1이 삭제되면 그 다음 진입차수가 0인 노드3과 노드2는 스택에 담는다.

- 그래프는 인접 리스트로 표현, 후보 정점들은 스택에 저장

 

int topo_sort(GraphType *g){
	int i;
	StackType s;
	GraphNode *node;
	
	int *in_degree = (int*)malloc(g->n * sizeof(int));
	for(i=0; i<g->n;i++){
		in_degree[i]=0;
	} // 배열 초기화
	for(i =0; i<g->n; i++){
		GraphNode *node = g->adj_list[i];
		while(node != NULL){
			in_degree[node->vertex]++;
			node = node->link;
		}
	} // 각 노드에 들어오는 간선 수 만큼 ++
	
	init_stack(&s);
	for(i=0; i<g->n; i++){
		if(in_degree[i]==0) push(&s,i);
	}
	
	while(!is_empty(&s)){
		int w;
		w = pop(&s);
		printf("정점 %d -> ",w);
		node = g->adj_list[w];
		while(node !=NULL){
			int u = node->vertex;
			in_degree[u]--;
			if(in_degree[u]==0) push(&s,u);
			node = node->link;
		}
	}
	free(in_degree);
	printf("\n");
	return (i == g->n);
	
}

 

♠ 437p Quiz

01 정점 0 -> 정점 1 -> 정점 2 -> 정점 4 -> 정점 3 -> 정점 5     정점 0 -> 정점 1 -> 정점 3 -> 정점 2 -> 정점 4 -> 정점 5