JavaScript-JavaScript數(shù)據(jù)結(jié)構(gòu)和算法之圖和圖算法,

時(shí)間：2024-10-25 13:21:36 JavaScript

　　圖的定義

　　圖（Graph）是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為：G(V,E)，其中，G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合，E是圖G中邊的集合。

　　有向圖

　　有向邊：若從頂點(diǎn)Vi到Vj的邊有方向，則稱這條邊為有向邊，也成為弧(Arc)，用有序偶來表示，Vi稱為弧尾，Vj稱為弧頭。

　　無序圖

　　無向邊：若頂點(diǎn)Vi到Vj之間的邊沒有方向，則稱這條邊為無向邊(Edge)，用無序偶(Vi,Vj)來表示。

　　簡(jiǎn)單圖

　　簡(jiǎn)單圖：在圖結(jié)構(gòu)中，若不存在頂點(diǎn)到其自身的邊，且同一條邊不重復(fù)出現(xiàn)，則稱這樣的圖為簡(jiǎn)單圖。

　　圖類

　　表示頂點(diǎn)

　　創(chuàng)建圖類的第一步就是要?jiǎng)?chuàng)建一個(gè)Vertex類來保存頂點(diǎn)和邊。這個(gè)類的作用和鏈表、二叉搜索樹的Node類一樣。Vertex類有兩個(gè)數(shù)據(jù)成員：一個(gè)用于標(biāo)識(shí)頂點(diǎn)，另一個(gè)表明是否被訪問過的布爾值。分別被命名為label和wasVisited。

　　復(fù)制代碼代碼如下:

　　function Vertex(label){

　　this.label = label;

　　}

　　我們將所有頂點(diǎn)保存在數(shù)組中，在圖類里，可以通過他們?cè)跀?shù)組中的位置引用他們

　　表示邊

　　圖的實(shí)際信息都保存在“邊”上面，因?yàn)樗麄兠枋隽藞D的結(jié)構(gòu)。二叉樹的一個(gè)父節(jié)點(diǎn)只能有兩個(gè)子節(jié)點(diǎn)，而圖的結(jié)構(gòu)卻要靈活得多，一個(gè)頂點(diǎn)既可以有一條邊，也可以有多條邊和它相連。

　　我們將表示圖的邊的方法成為鄰接表或者鄰接表數(shù)組。它將存儲(chǔ)由頂點(diǎn)的相鄰頂點(diǎn)列表構(gòu)成的數(shù)組

　　構(gòu)建圖

　　定義如下一個(gè)Graph類：

　　復(fù)制代碼代碼如下:

　　function Graph(v){

　　this.vertices = v;//vertices至高點(diǎn)

　　this.edges = 0;

　　this.adj = [];

　　for(var i =0;I<this.vertices;++i){

　　this.adj[i] = [];

　　this.adj[i].push(');

　　}

　　this.addEdge = addEdge;

　　this.toString = toString;

　　}

　　這個(gè)類會(huì)記錄一個(gè)圖表示了多少條邊，并使用一個(gè)長(zhǎng)度與圖的頂點(diǎn)數(shù)來記錄頂點(diǎn)的數(shù)量。

　　復(fù)制代碼代碼如下:

　　function addEdge(){

　　this.adj[v].push(w);

　　this.adj[w].push(v);

　　this.edges++;

　　}

　　這里我們使用for循環(huán)為數(shù)組中的每個(gè)元素添加一個(gè)子數(shù)組來存儲(chǔ)所有的相鄰頂點(diǎn)，并將所有元素初始化為空字符串。

　　圖的遍歷

　　深度優(yōu)先遍歷

　　深度優(yōu)先遍歷(DepthFirstSearch)，也有稱為深度優(yōu)先搜索，簡(jiǎn)稱為DFS。

　　比如在一個(gè)房間內(nèi)尋找一把鑰匙，無論從哪一間房間開始都可以，將房間內(nèi)的墻角、床頭柜、床上、床下、衣柜、電視柜等挨個(gè)尋找，做到不放過任何一個(gè)死角，當(dāng)所有的抽屜、儲(chǔ)藏柜中全部都找遍后，接著再尋找下一個(gè)房間。

　　深度優(yōu)先搜索：

　　深度優(yōu)先搜索就是訪問一個(gè)沒有訪問過的頂點(diǎn)，將他標(biāo)記為已訪問，再遞歸地去訪問在初始頂點(diǎn)的鄰接表中其他沒有訪問過的頂點(diǎn)

　　為Graph類添加一個(gè)數(shù)組：

　　復(fù)制代碼代碼如下:

　　this.marked = [];//保存已訪問過的頂點(diǎn)

　　for(var i=0;i<this.vertices;++i){

　　this.marked[i] = false;//初始化為false

　　}

　　深度優(yōu)先搜索函數(shù)：

　　復(fù)制代碼代碼如下:

　　function dfs(v){

　　this.marked[v] = true;

　　//if語句在這里不是必須的

　　if(this.adj[v] != undefined){

　　print("Visited vertex: " + v );

　　for each(var w in this.adj[v]){

　　if(!this.marked[w]){

　　this.dfs(w);

　　}

　　廣度優(yōu)先搜索

　　廣度優(yōu)先搜索（BFS）屬于一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點(diǎn)，以找尋結(jié)果。換句話說，它并不考慮結(jié)果的可能位置，徹底地搜索整張圖，直到找到結(jié)果為止。

　　廣度優(yōu)先搜索從第一個(gè)頂點(diǎn)開始，嘗試訪問盡可能靠近它的頂點(diǎn)，如下圖所示：

　　其工作原理為：

　　1. 首先查找與當(dāng)前頂點(diǎn)相鄰的未訪問的頂點(diǎn)，將其添加到已訪問頂點(diǎn)列表及隊(duì)列中；

　　2. 然后從圖中取出下一個(gè)頂點(diǎn)v，添加到已訪問的頂點(diǎn)列表

　　3. 最后將所有與v相鄰的未訪問頂點(diǎn)添加到隊(duì)列中

　　下面是廣度優(yōu)先搜索函數(shù)的定義：

　　復(fù)制代碼代碼如下:

　　function bfs(s){

　　var queue = [];

　　this.marked = true;

　　queue.push(s);//添加到隊(duì)尾

　　while(queue.length>0){

　　var v = queue.shift();//從隊(duì)首移除

　　if(v == undefined){

　　print("Visited vertex: " + v);

　　}

　　for each(var w in this.adj[v]){

　　if(!this.marked[w]){

　　this.edgeTo[w] = v;

　　this.marked[w] = true;

　　queue.push(w);

　　}

　　最短路徑

　　在執(zhí)行廣度優(yōu)先搜索時(shí)，會(huì)自動(dòng)查找從一個(gè)頂點(diǎn)到另一個(gè)相連頂點(diǎn)的最短路徑

　　確定路徑

　　要查找最短路徑，需要修改廣度優(yōu)先搜索算法來記錄從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的路徑，我們需要一個(gè)數(shù)組來保存從一個(gè)頂點(diǎn)操下一個(gè)頂點(diǎn)的所有邊，我們將這個(gè)數(shù)組命名為edgeTo

　　復(fù)制代碼代碼如下:

　　this.edgeTo = [];//將這行添加到Graph類中

　　//bfs函數(shù)

　　function bfs(s){

　　var queue = [];

　　this.marked = true;

　　queue.push(s);//添加到隊(duì)尾

　　while(queue.length>0){

　　var v = queue.shift();//從隊(duì)首移除

　　if(v == undefined){

　　print("Visited vertex: " + v);

　　}

　　for each(var w in this.adj[v]){

　　if(!this.marked[w]){

　　this.edgeTo[w] = v;

　　this.marked[w] = true;

　　queue.push(w);

　　}

　　拓?fù)渑判蛩惴?/p>

　　拓?fù)渑判驎?huì)對(duì)有向圖的所有頂點(diǎn)進(jìn)行排序，使有向邊從前面的頂點(diǎn)指向后面的頂點(diǎn)。

　　拓?fù)渑判蛩惴ㄅcBFS類似，不同的是，拓?fù)渑判蛩惴ú粫?huì)立即輸出已訪問的頂點(diǎn)，而是訪問當(dāng)前頂點(diǎn)鄰接表中的所有相鄰頂點(diǎn)，直到這個(gè)列表窮盡時(shí)，才會(huì)將當(dāng)前頂點(diǎn)壓入棧中。

　　拓?fù)渑判蛩惴ū徊鸱譃閮蓚€(gè)函數(shù)，第一個(gè)函數(shù)是topSort()，用來設(shè)置排序進(jìn)程并調(diào)用一個(gè)輔助函數(shù)topSortHelper()，然后顯示排序好的頂點(diǎn)列表

　　拓?fù)渑判蛩惴ㄖ饕ぷ魇窃谶f歸函數(shù)topSortHelper()中完成的，這個(gè)函數(shù)會(huì)將當(dāng)前頂點(diǎn)標(biāo)記為已訪問，然后遞歸訪問當(dāng)前頂點(diǎn)鄰接表中的每個(gè)頂點(diǎn)，標(biāo)記這些頂點(diǎn)為已訪問。最后，將當(dāng)前頂點(diǎn)壓入棧中。

　　復(fù)制代碼代碼如下:

　　//topSort()函數(shù)

　　function topSort(){

　　var stack = [];

　　var visited = [];

　　for(var i =0;i<this.vertices;i++){

　　visited[i] = false;

　　}

　　for(var i = 0;i<this.vertices;i++){

　　if(visited[i] == false){

　　this.topSortHelper(i,visited,stack);

　　}