8.4.2 최소 비용 신장 트리 (5)
Kruskal의 MST 알고리즘
최소 비용 신장 트리가 최소 비용의 간선으로 구성됨과 동시에 사이클을 포함하지 않는다는 조건에 근거하여, 각 단계에서 사 이클을 이루지 않는 최소 비용 간선을 선택
그래프의 간선들을 가중치의 오름차순으로 정렬한다.
정렬된 간선들의 리스트에서 사이클을 형성하지 않는 간선을 찾 아서 현재의 최소 비용 신장 트리의 집합에 추가한다.
만약 사이클을 형성하면 그 간선은 제외된다.
8.4.2 최소 비용 신장 트리 (6)
Kruskal의 MST 알고리즘
8.5 그래프의 응용
8.5.1 최단 경로 검색
8.5.2 모든 정점간의 최단경로 8.5.3 이행적 폐쇄행렬
8.5.4 위상정렬
8.5.5 유통문제
8.5.6 임계경로
8.5.1 최단 경로 검색 (1)
최단 경로(shortest path):
최단경로 문제는 네트워크에서 정점 i와 정점 j를 연결하 는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로 를 찾는 문제
간선의 가중치는 비용, 거리, 시간 등을 나타낸다.
8.5.1 최단 경로 검색 (2)
디익스트라(Dijkstra)의 최단 경로 알고리즘
Dijkstra의 최단 경로 알고리즘은 네트워크에서 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾 는 알고리즘
집합 S: 시작 정점 v로부터의 최단경로가 이미 발견된 정 점들의 집합
distance 배열: 최단 경로를 알려진 정점만을 통하여 각 정점까지가는 최단경로의 길이
매단계에서 가장 distance 값이 적은 정점을 S에 추가한 다.
매단계에서 새로운 정점이 S에 추가되면 distance값을 갱
신한다.
8.5.1 최단 경로 검색 (3)
1 2
3
4
5
6 7
0 San Francisco
Denver
Chicago
Miami New Orleans
Los Angeles 800
1200
1500
250
1000
1400
900 1000
1700 1000 300
Boston
New York
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7 0
300 1000
1700 0 800
0 1500 1000
0 1200
0
250 0
900 0
1400 1000 0
Itera
-tion S Vertex
selected
Distance
LA SR DEN CHI BOST NY MIA NO
[0] [1] [2] [3] [4] [5] [6] [7]
Initia l 1 2 3 4 5 6
… {4}
{4,5}
{4,5,6}
{4,5,6,3}
{4,5,6,3,7}
{4,5,6,3,7,2}
{4,5,6,3,7,2,1}
… 5 6 3 7 2 1
+∞ +∞ +∞ 1500 0 250 +∞ +∞
+∞ +∞ +∞ 1500 0 250 1150 1650 +∞ +∞ +∞ 1500 0 250 1150 1650 +∞ +∞ 2450 1500 0 250 1150 1650 3350 +∞ 2450 1500 0 250 1150 1650 3350 3250 2450 1500 0 250 1150 1650 3350 3250 2450 1500 0 250 1150 1650
8.5.1 최단 경로 검색 (3)
디익스트라(Dijkstra)의 최단 경로
8.5.2 모든 정점간의 최단 경로
알고리즘
Public void FLOYD(int [][] A, fload [][] cost, int n) {
int i,j,k;
for(i=0;j<n;i++) for(j=0;j<n;j++) A[i][j]=cost[i][j];
for(k=0;k<n;k++) for(i=0;i<n;i++) for(j=0;j<n;j++)
if(A[i][k]+A[k][j]<A[i][j]
A[i][j]=A[i][k]+A[k][j];
}
0 1
2
6
4
3 2
11
A-1 0 1 2
0 4 11 6 0 2 3 ∞ 0 0
1 2
A0 0 1 2
0 4 11 6 0 2 3 7 0 0
1 2
A1 0 1 2
0 4 6 6 0 2 3 7 0 0
1 2
A2 0 1 2
0 4 6 5 0 2 3 7 0 0
1 2
8.5.3 이행적 폐쇄 행렬
이행적 폐쇄 행렬(Transitive closure matrix)
Definition: Transitive closure matrix A+
Reflexive transitive closure A*
0 1 2 3 5
(a) 방향 그래프 G
0 1 2 3 4 0
1 2 3 4
0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0
0 1 2 3 4 0
1 2 3 4
0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1
0 1 2 3 4 0
1 2 3 4
1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 (b) G의 인접행렬 A
(d) A* (c) A+
8.5.4 위상정렬 (1)
위상정렬(topological sort):
방향 그래프에서 간선 <u, v>가 있다면 정점 u는 정점 v를 선행 한다고 말한다. 방향 그래프에 존재하는 각 정점들의 선행 순서 를 위배하지 않으면서 모든 정점을 나열하는 것을 방향 그래프 의 위상 정렬(topological sort)이라고 한다.
과목번호 과목명 선수과목
0 전산학개론 없음
1 이산수학 없음
2 자료구조 1
3 알고리즘 분석 0, 1, 2
4 운영체제 1
5 인공지능 2, 3, 4
위상정렬: (0,1,2,3,4,5) , (1,0,2,3,4,5)
(2,0,1,3,4,5)는 위상 정렬이 아니다. 왜냐하면 2번 정점이 0번 정점 앞
에 오기 때문이다. 간선 <0, 2>이 존재하기 때문에 0번 정점이 끝나야
만이 2번 정점을 시작할 수 있다.
8.5.4 위상정렬 (2)
8.5.4 위상정렬 (3)
Input: 그래프 G=(V,E) Output: 위상 정렬 순서 topo_sort(G)
for i←0 to do
if( 모든 정점이 선행 정점을 가지면 )
then 사이클이 존재하고 위상 정렬 불가;
선행 정점을 가지지 않는 정점 v 선택;
v를 출력;
v와 v에서 나온 모든 간선들을 그래프에서 삭제;
8.5.6 임계경로 (1)
간접 작업 네트워크(Activity on Edge Network)
1
2
3
4
5 0
6
7
8 a1=6
a3=5
a5=1
a4=1 a7=9 a10=2
a11=4 a8=7
a6=2 a2=4
a9=4
start finish
가상 프로젝트에 대한 AOE- 네트워크
8.5.6 임계경로 (2)
임계경로의 계산
인접리스트 ee의 계산
8.5.6 임계경로 (3)
임계경로의 계산
인접리스트
ee의 계산
16
6.5.1 Activity-on-Vertex (AOV) Networks
Definition:
AOV network (Example: Figure 6.35) Partial order
Topological order
Input the AOV network. Let n be the number of vertices.
for (int i=0;i<n;i++) {
if (every vertex has a predecessor) return;
pick a vertex v that has no predecessors;
cout << v;
delete v and all edges leading out of v from the network;
}
Design of a topological sorting algorithm
17
6.5.1 Activity-on-Vertex (AOV) Networks
void Graph::TopologicalOrder() {
int top=-1;
for (int i=0;i<n;i++)
if (count[i] ==0) {count[i] = top; top= i;}
for (i=0;i<n;i++)
if (top == -1) {cout << “network has a cycle” << endl; return;}
else {
int j=top; top = count[top];
cout << j << endl;
ListIterator<int> li(HeadNodes[j]);
if (! li.NotNull()) continue;
int k = *li.First();
while (1){
count[k]--;
if (count[k] == 0) {count[k]= top; top = k}
if (li.NextNotNull()) k = *li.Next();
else break;
}
} // end of else }
Program 6.12: Topological order
Check time complexity
18
6.5.2 Activity-on-Edge (AOE) Networks
Definition:
AOV network Critical path Earliest time
Latest time
1
2
3
4
5 0
6
7
8 a1=6
a3=5
a5=1
a4=1 a7=9 a10=2
a11=4 a8=7
a6=2 a2=4
a9=4
start finish
(a) Activity network of a hypothetical project
event Interpretation 0
1 4 7 8
Start of project
Completion of activity a1
Completion of activities a4 and a5 Completion of activities a8 and a9 Completion of project
(b) Interpretation of some of the events in the network of (a)
