書籍筆記 – 頁面 4 – Bake

圖說演算法使用JavaScript(三十六)

10-4-2 Kruskal 演算法

Kruskal 演算法是將各邊緣線依權值大小由小到大排列，接著從權值最低的邊緣開始架構最小成本擴張樹，如果加入的邊線會造成迴路則捨棄不用，直到加入了n-1個邊線為止。

這方法看起來似乎不難，我們直接來看如何以K氏法得到範例下圖中最小成本擴張樹：

步驟一：把所有邊線的成本列出並由小到大排序。

步驟二：選擇成本最低的一條邊線作為架構最小成本擴張樹的起點。

步驟三：依步驟一所建立的表格，依序加入邊線。

步驟四： C-D加入會形成迴路，所以直接跳過。

完成圖

Kruskal 法的演算法

const VERTS=6;
class edge {
	constructor() {
		this.start=0;
		this.to=0;
		this.find=0;
		this.val=0;
		this.next=null;
	}
}

v=[];
for (let i=0; i<VERTS+1; i++) v[i]=0;
var findmincost=(head)=> {
	minval=100;
	let ptr=head;
	while (ptr!=null) {
		if (ptr.val<minval && ptr.find==0) {
			minval=ptr.val;
			retptr=ptr;
		}
		ptr=ptr.next;
	}
	retptr.find=1;
	return retptr;
}
var mintree=(head)=> {
	let result=0;
	let ptr=0;
	for (let i=0; i<VERTS; i++)
		v[i]=0;
	while (ptr!=null) {
		mceptr=findmincost(head);
		v[mceptr.start]=v[mceptr.start]+1;
		v[mceptr.to]=v[mceptr.to]+1;
		if (v[mceptr.start]>1 && v[mceptr.to]>1) {
			v[mceptr.start]=v[mceptr.start]-1;
			v[mceptr.to]=v[mceptr.to]-1;
			result=1;
		}
		else
			result=0;
		if (result==0) {
			process.stdout.write('起點頂點 ['+mceptr.start+'] -> 終止頂點 [' + mceptr.to+'] -> 路徑長度 ['+mceptr.val+']\n');
		}
		ptr=ptr.next;
	}
}

JS kruskal.js

const VERTS=6;
class edge {
	constructor() {
		this.start=0;
		this.to=0;
		this.find=0;
		this.val=0;
		this.next=null;
	}
}

v=[];
for (let i=0; i<VERTS+1; i++) v[i]=0;
var findmincost=(head)=> {
	minval=100;
	let ptr=head;
	while (ptr!=null) {
		if (ptr.val<minval && ptr.find==0) {
			minval=ptr.val;
			retptr=ptr;
		}
		ptr=ptr.next;
	}
	retptr.find=1;
	return retptr;
}
var mintree=(head)=> {
	let result=0;
	let ptr=head;
	for (let i=0; i<VERTS; i++)
		v[i]=0;
	while (ptr!=null) {
		mceptr=findmincost(head);
		v[mceptr.start]=v[mceptr.start]+1;
		v[mceptr.to]=v[mceptr.to]+1;
		if (v[mceptr.start]>1 && v[mceptr.to]>1) {
			v[mceptr.start]=v[mceptr.start]-1;
			v[mceptr.to]=v[mceptr.to]-1;
			result=1;
		}
		else
			result=0;
		if (result==0) {
			process.stdout.write('起點頂點 ['+mceptr.start+'] -> 終止頂點 [' +
				mceptr.to+'] -> 路徑長度 ['+mceptr.val+']\n');
		}
		ptr=ptr.next;
	}
}

data=[[1,2,6],[1,6,12],[1,5,10],[2,3,3],
		[2,4,5],[2,6,8],[3,4,7],[4,6,11],
		[4,5,9],[5,5,16]];
var head=null;
for (i=0; i<10; i++) {
	for (j=1; j<=VERTS+1; j++) {
		if (data[i][0]==j) {
			newnode=new edge();
			newnode.start=data[i][0];
			newnode.to=data[i][1];
			newnode.val=data[i][2];
			newnode.find=0;
			newnode.next=null;
			if (head==null) {
				head=newnode;
				head.next=null;
				ptr=head;
			}
			else {
				ptr.next=newnode;
				ptr=ptr.next;
			}
		}
	}
}

process.stdout.write('--------------------------------------------------\n');
process.stdout.write('建立最小成本擴張樹：\n');
process.stdout.write('--------------------------------------------------\n');
mintree(head);

10-5 圖形最短路徑演算法

在一個有向圖形G=(V,E)，G中每一個邊都有一個比例常數W(Weight)與之對應，如果想求G圖形中某一個頂點V0到其他頂點的最少W總和之值，這類問題就稱為最短路徑問題(The Shortest Path Problem)。由於交通運輸工具的便利與普及，所以兩地之間有發生運送或者資訊的傳遞下，最短路徑(Shortest Path)的問題隨時都可能因應需求而產生，簡單來說，就是找出兩個端點間可行的捷徑。

我們在上捷中所說明的花費最少擴張樹(MST)，是計算聯繫網路中每一個頂點所需的最少花費，但連繫樹中任何倆頂點的路徑不一定是一條花費最少的路徑，這也是本節將研究最短路徑問題的主要理由。以下是在討論最短路徑常見的演算法。

10-5-1 Dijlstra 演算法與A*演算法

從上述的演算法我們可以推演出如下步驟：

由頂點5到其他各頂點的最短距離為：
頂點5-頂點0：26
頂點5-頂點1：12
頂點5-頂點2：18
頂點5-頂點3：20
頂點5-頂點4：14

JS dijkstra.js

const SIZE=7;
const NUMBER=6;
const INFINITE=99999; //無窮大
var Graph_Matrix=[[0,0,0,0,0,0,0],
				  [0,0,0,0,0,0,0],
				  [0,0,0,0,0,0,0],
				  [0,0,0,0,0,0,0],
				  [0,0,0,0,0,0,0],
				  [0,0,0,0,0,0,0],
				  [0,0,0,0,0,0,0]];
var distance=[];
for (let i=0; i<SIZE; i++) distance[i]=0;

var BuildGraph_Matrix=(Path_Cost)=> {
	for (let i=1; i<SIZE; i++) {
		for (let j=1; j<SIZE; j++) {
			if (i==j)
				Graph_Matrix[i][j]=0;
			else
				Graph_Matrix[i][j]=INFINITE;
		}
	}
	i=0;
	while (i<SIZE) {
		Start_Point=Path_Cost[i][0];
		End_Point=Path_Cost[i][1];
		Graph_Matrix[Start_Point][End_Point]=Path_Cost[i][2];
		i+=1;
	}
}

var shortestPath=(vertexl, vertex_total)=> {
	let shortest_vertex=1;
	let goal=[];
	for (let i=1; i<vertex_total+1; i++) {
		goal[i]=0;
		distance[i]=Graph_Matrix[vertexl][i];
	}
	goal[vertexl]=1;
	distance[vertexl]=0;
	process.stdout.write('\n');

	for (let i=1; i<vertex_total; i++) {
		shortest_distance=INFINITE;
		for (let j=1; j<vertex_total+1; j++) {
			if (goal[j]==0 && shortest_distance>distance[j]) {
				shortest_distance=distance[j];
				shortest_vertex=j;
			}
		}
		goal[shortest_vertex]=1;

		for (let j=1; j<vertex_total+1; j++) {
			if (goal[j]==0 && 
				distance[shortest_vertex]+Graph_Matrix[shortest_vertex]
											[j]<distance[j]){
				distance[j]=distance[shortest_vertex]+Graph_Matrix[shortest_vertex][j];
			}
		}
	}
}

Path_Cost=[[1,2,29],[2,3,30],[2,4,35],
			[3,5,28],[3,6,87],[4,5,42],
			[4,6,75],[5,6,97]];
BuildGraph_Matrix(Path_Cost);
shortestPath(1,NUMBER);
process.stdout.write('------------------------------\n');
process.stdout.write('頂點1到各頂點最短距離的最終結果\n');
process.stdout.write('------------------------------\n');
for (let j=1; j<SIZE; j++) {
	process.stdout.write('頂點1到頂點'+j+'的做短距離='+distance[j]+'\n');
}
process.stdout.write('------------------------------\n');

圖說演算法使用JavaScript(三十五)

10-4 擴張術的密碼

擴張樹又稱(花費樹)或(植樹)，一個圖形的擴張樹(Spanning Tree)就是以最少的編來連結圖形中所有的頂點，且不造成循環(Cycle)的樹狀結構。假設在樹的編加上一個權重(weight)值，這種圖形就成為(加權圖形 Weighted Graph)。如果這個權重值代表兩個頂點間的距離(distance)或成本(Cost)，這類圖形就稱為網路(Network)。如下圖所示：

假如想知道從某個點到另一個點間的路徑成本，例如由頂點1到頂點5有(1+2+3)、(1+6+4)及5這三個路徑成本，而(最小成本擴張樹Minimun Cost Spanning Tree)則是路徑成本為5的擴張樹。請看說明：

一個加權圖形中如何找到最小成本擴張樹是相當重要，因為許多工作都可以由圖形來表示，例如從高雄到花蓮的距離或花費等。接著將介紹以所謂(貪婪法則Greedy Rule)為基礎，來求得一個無向連通圖形的最小花費樹的常見建立方法。分別是Prim’s演算法及Kruskal’s演算法。

10-4-1 Prim演算法

Prim 演算法又稱P氏法，對一個加權圖形G=(V,E)，設V={1,2,……n}，假設U={1}，也就是說，U及V是兩個頂點的集合。

然後從U-V差集所產生的集合中找出一個頂點x，該頂點x能與U集合中的某點形成最小成本的邊，且不會造成迴圈。然後將頂點x加入U集合中，反覆執行同樣的步驟，一直到U集合等於V集合(即U=V)為止。

接下來，我們將實際利用P氏法求出下圖的做小擴張樹。

從此圖形中可得V={1,2,3,4,5,6},U=1

從V-U={2,3,4,5,6}中找一頂點與U頂點能形成最小成本邊，得

V-U={2,3,4,6} U={1,5}

從V-U中頂點找出與U頂點能形成最小成本的邊，得

且 U={1,5,6}，V-U={2,3,4}

同理，找到頂點4

U={1,5,6,4}，V-U={2,3}

同理，找到頂點3

同理，找到頂點2

圖說演算法使用JavaScript(三十四)

10-3 圖形走訪的訣竅

樹的追蹤目的是欲拜訪樹的每一個節點一次，可用的方法有中序法、前序法和後序法等三種。而圖形追蹤的定義如下：

一個圖形G=(V,E)，存在某一頂點vEV，我們希望從v開始，經由此節點相鄰的節點兒去拜訪G中其他節點，這稱之為(圖形追蹤)。也就是從某一個頂點V1開始，走訪可以經由V1到達的頂點，接著在走訪下一個頂點直到全部的頂點走訪完畢為止。

在走訪的過程中可能會重複經過某些頂點及邊線。經由圖形的走訪可以判斷該圖形是否連通，並找出連通單元及路徑。圖形走訪的方法有兩種：(先深後廣走訪)及(先廣後深走訪)。

10-3-1 先深後廣走訪法

先身後廣走訪的方式有點類似前序走訪。適從圖形的某一頂點開始走訪，被拜訪過的頂點就作上已拜訪記號，接著走訪此頂點的所有相鄰且未拜訪過的頂點中的任一個頂點，並作上已拜訪的記號，再以該點為新的起點繼續進行先深厚廣的搜尋。
這種圖形追蹤方法結合了遞迴及堆疊兩種資料結構的技巧，由於此方法會造成無窮迴路，所以必須加入一個變數，判斷該點是否已經走訪完畢。我們以下徒來看看這個方法的走訪過程。

故先深後廣的走訪順序為：頂點1、頂點2、頂點3、頂點4、頂點5。

深度優先函數的演算法如下：

var DFs=(current)=> {
run[current] = 1;
process.stdout.write(“[“+current+”]”);
while (Head[current].first) != null) {
if (run[Head[current].first.x] == 0)
Dfs(Head[current].first.x);
Head[current].first = Head[current].first.next;
}
}

JS dfs.js

class Node {
	constructor(x) {
		this.x = x;
		this.next = null;
	}
}

class GraphLink {
	constructor() {
		this.first = null;
		this.last = null;
	}

	IsEmpty() {
		return this.first == null;
	}

	Print() {
		let current = this.first;
		while (current != null) {
			process.stdout.write('['+current.x+'] ');
			current = current.next;
		}
			process.stdout.write('\n');
	}

	Insert(x) {
		let newNode = new Node(x);
		if (this.IsEmpty()) {
			this.first = newNode;
			this.last = newNode;
		}
		else {
			this.last.next = newNode;
			this.last = newNode;
		}
	}
}

run=[];
Head=[];
for (i=0; i<9; i++)
	Head[i] = new GraphLink();

var DFs=(current)=> {
	run[current] = 1;
	process.stdout.write("["+current+"]");
	while ((Head[current].first) != null) {
		if (run[Head[current].first.x] == 0) 
			DFs(Head[current].first.x);

		Head[current].first = Head[current].first.next;
	}
}

Data=[];

Data=[[1,2],[2,1],[1,3],[3,1],[2,4],
		[4,2],[2,5],[5,2],[3,6],[6,3],
		[3,7],[7,3],[4,5],[5,4],[6,7],
		[7,6],[5,8],[8,5],[6,8],[8,6]];

run=[];
Head=[];

for (i=0; i<9; i++)
	Head[i]=new GraphLink();

process.stdout.write("圖形的相鄰串接內容：\n");

for (let i=1; i<9; i++) {
	run[i]=0;
	process.stdout.write('頂點'+ i +'=>');
	Head[i] = new GraphLink();
	for (j=0; j<20; j++) {
		if (Data[j][0]==i) {
			DataNum = Data[j][1];
			Head[i].Insert(DataNum);
		}
	}
	Head[i].Print();
}
process.stdout.write("深度優先走訪頂點：\n");
DFs(1);
process.stdout.write('\n');

10-3-2 先廣後深搜尋法

之前所談到先深候廣是利用堆疊及遞迴的技巧來走訪圖形，而先廣後深(Breadth-First Search, BFS)走訪方式則是以佇列及遞迴來走訪，也是從圖形的某一頂點開始走訪，被拜訪過的頂點就做以拜訪的記號。接著走訪此頂點的所有相鄰且為拜訪過的頂點中任意一個頂點，並做上已拜訪的記號，再以該點為新的起點繼續進行先廣後深的搜尋。我們以下圖來看看BFS的走訪過程：