圖說演算法使用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的走訪過程：