摘要:分別被命名為和。圖的遍歷深度優(yōu)先遍歷深度優(yōu)先遍歷,也有稱為深度優(yōu)先搜索,簡(jiǎn)稱為。拓?fù)渑判蛩惴ㄅc類似,不同的是,拓?fù)渑判蛩惴ú粫?huì)立即輸出已訪問的頂點(diǎn),而是訪問當(dāng)前頂點(diǎn)鄰接表中的所有相鄰頂點(diǎn),直到這個(gè)列表窮盡時(shí),才會(huì)將當(dāng)前頂點(diǎn)壓入棧中。
圖的定義
圖(Graph)是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成,通常表示為:G(V,E),其中,G表示一個(gè)圖,V是圖G中頂點(diǎn)的集合,E是圖G中邊的集合。
有向圖
有向邊:若從頂點(diǎn)Vi到Vj的邊有方向,則稱這條邊為有向邊,也成為弧(Arc),用有序偶
**
無向邊:**若頂點(diǎn)Vi到Vj之間的邊沒有方向,則稱這條邊為無向邊(Edge),用無序偶(Vi,Vj)來表示。
簡(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。
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類:
function Graph(v){ this.vertices = v;//vertices至高點(diǎn) this.edges = 0; this.adj = []; for(var i =0;I這個(gè)類會(huì)記錄一個(gè)圖表示了多少條邊,并使用一個(gè)長度與圖的頂點(diǎn)數(shù)來記錄頂點(diǎn)的數(shù)量。
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ù)組:
this.marked = [];//保存已訪問過的頂點(diǎn) for(var i=0;i深度優(yōu)先搜索函數(shù):
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ù)的定義:
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
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ù)渑判蛩惴?/b>拓?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)壓入棧中。
//topSort()函數(shù) function topSort(){ var stack = []; var visited = []; for(var i =0;i
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://m.specialneedsforspecialkids.com/yun/85425.html
摘要:圖的定義用圖對(duì)現(xiàn)實(shí)中的系統(tǒng)建模可以用圖對(duì)現(xiàn)實(shí)中的很多系統(tǒng)建模比如對(duì)交通流量建模頂點(diǎn)可以表示街道的十字路口邊可以表示街道加權(quán)的邊可以表示限速或者車道的數(shù)量建模人員可以用這個(gè)系統(tǒng)來判斷最佳路線及最有可能堵車的街道任何運(yùn)輸系統(tǒng)都可以用圖來建模比如 圖的定義 用圖對(duì)現(xiàn)實(shí)中的系統(tǒng)建模 可以用圖對(duì)現(xiàn)實(shí)中的很多系統(tǒng)建模. 比如對(duì)交通流量建模, 頂點(diǎn)可以表示街道的十字路口, 邊可以表示街道. 加權(quán)的邊...
摘要:為檢查長度為的列表,二分查找需要執(zhí)行次操作。最后需要指出的一點(diǎn)是高水平的讀者可研究一下二叉樹關(guān)于二叉樹,戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹算法常見練習(xí)在一個(gè)二維數(shù)組中,每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。 常見數(shù)據(jù)結(jié)構(gòu) 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)(必須理解和掌握) 有序數(shù)據(jù)結(jié)構(gòu):棧、隊(duì)列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間(儲(chǔ)存空間小) 無序數(shù)據(jù)結(jié)構(gòu):集合、字典、散列表,無序...
摘要:為檢查長度為的列表,二分查找需要執(zhí)行次操作。最后需要指出的一點(diǎn)是高水平的讀者可研究一下二叉樹關(guān)于二叉樹,戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹算法常見練習(xí)在一個(gè)二維數(shù)組中,每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。 常見數(shù)據(jù)結(jié)構(gòu) 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)(必須理解和掌握) 有序數(shù)據(jù)結(jié)構(gòu):棧、隊(duì)列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間(儲(chǔ)存空間小) 無序數(shù)據(jù)結(jié)構(gòu):集合、字典、散列表,無序...
摘要:為檢查長度為的列表,二分查找需要執(zhí)行次操作。最后需要指出的一點(diǎn)是高水平的讀者可研究一下二叉樹關(guān)于二叉樹,戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹算法常見練習(xí)在一個(gè)二維數(shù)組中,每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。 常見數(shù)據(jù)結(jié)構(gòu) 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)(必須理解和掌握) 有序數(shù)據(jù)結(jié)構(gòu):棧、隊(duì)列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間(儲(chǔ)存空間小) 無序數(shù)據(jù)結(jié)構(gòu):集合、字典、散列表,無序...
閱讀 3032·2021-11-18 10:07
閱讀 3782·2021-11-17 17:00
閱讀 2113·2021-11-15 18:01
閱讀 938·2021-10-11 10:58
閱讀 3394·2021-09-10 10:50
閱讀 3468·2021-08-13 15:05
閱讀 1237·2019-08-30 15:53
閱讀 2659·2019-08-29 13:01