Chap08. Graph Optimization Problems and Greedy Algorithms

Graph Optimization Problems

Prim's Algorithm

Greedyを使用して最小生成ツリーを検索するアルゴリズム1

任意の点を始点(最小生成ツリーのルート)

として選択する.

反復のたびにedgeを追加し、edgeの別の頂点をツリーに追加します.
このときedgeは最小重みのedge-greedyアルゴリズム

を選択する.
ステータスは

各頂点の非交差カテゴリ

として表示する.

ツリー頂点:グラフィックで生成する最小生成ツリーに含まれる

Fringe頂点:ツリー頂点の候補として使用できます.すなわち、最小生成ツリーに隣接する頂点

.

Unsene頂点:ツリーでもエッジポイントでもない

Example::The Algorithm in Action

O(n)回挿入、削除

PrimMST(G,n) // OUTLINE
	Initialize all vertices as unseen.		// O(n) time
	Select an arbitrary vertex s to start the tree; reclassify it as tree.
	Reclassify all vertices adjacent to s as fringe.
    
	While there are fringe vertices;		// O(n)번 수행
		Select an edge of minimum weight between
			a tree vertex t and a fringe vertex v;	// O(n) time
		Reclassify v as tree; add edge tv to the tree;
		Reclassify all unseen vertices adjacent to v as fringe.	// deg(v)

*min-priority queue
sorted sequenceunsorted sequenceheapinsert()O(n)O(1)O(lg n)removeMin()O(1)O(n)O(lg n)decreasekey()O(n)O(1)O(lg n)

通常、heapを用いてより効率的に実施する
Example 1::ソートされていないシーケンスを使用して計算

2つの配列size=n-status、distanceを使用
1.statusはすべて非可視頂点に初期化し、距離はすべて無限-O(n)timeに初期化する
2.O(n)timeを反復するたびにstatusとdistanceを更新する

PrimMST(G,n) // OUTLINE
	Initialize all vertices as unseen.		// O(n) time
	Select an arbitrary vertex s to start the tree; reclassify it as tree.
	Reclassify all vertices adjacent to s as fringe.
    
	While there are fringe vertices;		// O(n)번 수행
		Select an edge of minimum weight between
			a tree vertex t and a fringe vertex v;	// O(n) time
		Reclassify v as tree; add edge tv to the tree;
		Reclassify all unseen vertices adjacent to v as fringe.	// deg(v)

O(n2n^2n2) time using the unsorted sequence
Example 2::heap計算を使用

PrimMST(G,n) // OUTLINE
	Initialize all vertices as unseen.		// O(n) time
	Select an arbitrary vertex s to start the tree; reclassify it as tree.
	Reclassify all vertices adjacent to s as fringe.
    
	While there are fringe vertices;		// O(n)번 삽입, 삭제
		Select an edge of minimum weight between
			a tree vertex t and a fringe vertex v;	// O(n) time
		Reclassify v as tree; add edge tv to the tree;
		Reclassify all unseen vertices adjacent to v as fringe.	// deg(v)

挿入と削除に必要なO(nlgn)時間
各edgeは2回の減量キー()−O(m)回を実行する
従って、O(nlgn+mlgn)<=O(mlgn)time
O(n2n^2n2) time using the unsorted sequence
O(mlgn) time using a heap
与えられたパターンのmの大きさがO(n)の疎図である場合,heap.
mのsizeがO(n 2 n^2 n 2)に近い稠密図である場合,並べ替えられていないシーケンスは有効である.

Kruskal's Algorithm

Greedyを使用して最小生成ツリーを検索するアルゴリズム2

KruskalMST(G,n) // outline
	R = E // R is remaining edges
	F = none // F is forest edges
	while (R is not empty)
		Remove the lightest (shortest) edge, vw, from R;
        
       		// cycle이 발생하지 않을 때만 MST 추가
            	// union-find ADT(disjoint set)
		if (vw does not make a cycle in F)	
			Add vw to F;
	return F ;

O(nlgn)時間で実行
edgeの重みに応じてより小さなedgeからMSTに追加

を使用したソート計算
edgeソート

KruskalMST(G,n) // outline
	R = E	// sorting: O(mlgm) time
	F = none 
	while (R is not empty)
		Remove the lightest (shortest) edge, vw, from R;
		if (vw does not make a cycle in F)	
			Add vw to F;
	return F ;

O(mlgm) time

分-heapを使用して計算
管理

にedgeのすべての情報をheapに挿入する

KruskalMST(G,n) // outline
	R = E	// m개 edges, O(m) time (bottom-up heap construction)
	F = none 
	while (R is not empty)	// O(m) 번
		Remove the lightest (shortest) edge, vw, from R;	// O(lgm) time
		if (vw does not make a cycle in F)	
			Add vw to F;
	return F ;

O(mlgm) time
* m=O(n2n^2n2), O(mlgm) = O(mlgn2n^2n2) = O(2mlgn) = O(mlgn)

Data Structure for Kruskal's Algorithm

O(nlgn)よりも高速

find(u):set id(leader)

を返す

union(u,v):uを含む集合とvを含む集合が異なる場合、unionを1つの集合として、2つのキー値(u,v)の小さい値をset idに設定します.

mMSTm{MST}mMST=n-1