JavaScript數(shù)據(jù)結(jié)構(gòu)和算法之圖和圖算法
圖的定義
圖（Graph）是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為：G(V,E)，其中，G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合，E是圖G中邊的集合。
有向圖
有向邊：若從頂點(diǎn)Vi到Vj的邊有方向，則稱這條邊為有向邊，也成為弧(Arc)，用有序偶<Vi,Vj>來(lái)表示，Vi稱為弧尾，Vj稱為弧頭。
無(wú)序圖
無(wú)向邊：若頂點(diǎn)Vi到Vj之間的邊沒(méi)有方向，則稱這條邊為無(wú)向邊(Edge)，用無(wú)序偶(Vi,Vj)來(lái)表示。
簡(jiǎn)單圖
簡(jiǎn)單圖：在圖結(jié)構(gòu)中，若不存在頂點(diǎn)到其自身的邊，且同一條邊不重復(fù)出現(xiàn)，則稱這樣的圖為簡(jiǎn)單圖。
圖類
表示頂點(diǎn)
創(chuàng)建圖類的第一步就是要?jiǎng)?chuàng)建一個(gè)Vertex類來(lái)保存頂點(diǎn)和邊。這個(gè)類的作用和鏈表、二叉搜索樹(shù)的Node類一樣。Vertex類有兩個(gè)數(shù)據(jù)成員：一個(gè)用于標(biāo)識(shí)頂點(diǎn)，另一個(gè)表明是否被訪問(wèn)過(guò)的布爾值。分別被命名為label和wasVisited。
function Vertex(label){
this.label = label;
}
我們將所有頂點(diǎn)保存在數(shù)組中，在圖類里，可以通過(guò)他們?cè)跀?shù)組中的位置引用他們
表示邊
圖的實(shí)際信息都保存在“邊”上面，因?yàn)樗麄兠枋隽藞D的結(jié)構(gòu)。二叉樹(shù)的一個(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<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ù)來(lái)記錄頂點(diǎn)的數(shù)量。
function addEdge(){
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
}
這里我們使用for循環(huán)為數(shù)組中的每個(gè)元素添加一個(gè)子數(shù)組來(lái)存儲(chǔ)所有的相鄰頂點(diǎn)，并將所有元素初始化為空字符串。
圖的遍歷
深度優(yōu)先遍歷
深度優(yōu)先遍歷(DepthFirstSearch)，也有稱為深度優(yōu)先搜索，簡(jiǎn)稱為DFS。
比如在一個(gè)房間內(nèi)尋找一把鑰匙，無(wú)論從哪一間房間開(kāi)始都可以，將房間內(nèi)的墻角、床頭柜、床上、床下、衣柜、電視柜等挨個(gè)尋找，做到不放過(guò)任何一個(gè)死角，當(dāng)所有的抽屜、儲(chǔ)藏柜中全部都找遍后，接著再尋找下一個(gè)房間。
深度優(yōu)先搜索：
深度優(yōu)先搜索就是訪問(wèn)一個(gè)沒(méi)有訪問(wèn)過(guò)的頂點(diǎn)，將他標(biāo)記為已訪問(wèn)，再遞歸地去訪問(wèn)在初始頂點(diǎn)的鄰接表中其他沒(méi)有訪問(wèn)過(guò)的頂點(diǎn)
為Graph類添加一個(gè)數(shù)組：
this.marked = [];//保存已訪問(wèn)過(guò)的頂點(diǎn)
for(var i=0;i<this.vertices;++i){
this.marked[i] = false;//初始化為false
}
深度優(yōu)先搜索函數(shù)：
function dfs(v){
this.marked[v] = true;
//if語(yǔ)句在這里不是必須的
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)地展開(kāi)并檢查圖中的所有節(jié)點(diǎn)，以找尋結(jié)果。換句話說(shuō)，它并不考慮結(jié)果的可能位置，徹底地搜索整張圖，直到找到結(jié)果為止。
廣度優(yōu)先搜索從第一個(gè)頂點(diǎn)開(kāi)始，嘗試訪問(wèn)盡可能靠近它的頂點(diǎn)，如下圖所示：
其工作原理為：
1. 首先查找與當(dāng)前頂點(diǎn)相鄰的未訪問(wèn)的頂點(diǎn)，將其添加到已訪問(wèn)頂點(diǎn)列表及隊(duì)列中；
2. 然后從圖中取出下一個(gè)頂點(diǎn)v，添加到已訪問(wèn)的頂點(diǎn)列表
3. 最后將所有與v相鄰的未訪問(wèn)頂點(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)先搜索算法來(lái)記錄從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的路徑，我們需要一個(gè)數(shù)組來(lái)保存從一個(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ù)渑判蛩惴?/strong>
拓?fù)渑判驎?huì)對(duì)有向圖的所有頂點(diǎn)進(jìn)行排序，使有向邊從前面的頂點(diǎn)指向后面的頂點(diǎn)。
拓?fù)渑判蛩惴ㄅcBFS類似，不同的是，拓?fù)渑判蛩惴ú粫?huì)立即輸出已訪問(wèn)的頂點(diǎn)，而是訪問(wèn)當(dāng)前頂點(diǎn)鄰接表中的所有相鄰頂點(diǎn)，直到這個(gè)列表窮盡時(shí)，才會(huì)將當(dāng)前頂點(diǎn)壓入棧中。
拓?fù)渑判蛩惴ū徊鸱譃閮蓚€(gè)函數(shù)，第一個(gè)函數(shù)是topSort()，用來(lái)設(shè)置排序進(jìn)程并調(diào)用一個(gè)輔助函數(shù)topSortHelper()，然后顯示排序好的頂點(diǎn)列表
拓?fù)渑判蛩惴ㄖ饕ぷ魇窃谶f歸函數(shù)topSortHelper()中完成的，這個(gè)函數(shù)會(huì)將當(dāng)前頂點(diǎn)標(biāo)記為已訪問(wèn)，然后遞歸訪問(wèn)當(dāng)前頂點(diǎn)鄰接表中的每個(gè)頂點(diǎn)，標(biāo)記這些頂點(diǎn)為已訪問(wèn)。最后，將當(dāng)前頂點(diǎn)壓入棧中。
//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);
}
}
for(var i = 0;i<stack.length;i++){
if(stack[i] !=undefined && stack[i] != false){
print(this.vertexList[stack[i]]);
}
}
}
//topSortHelper()函數(shù)
function topSortHelper(v,visited,stack){
visited[v] = true;
for each(var w in this.adj[v]){
if(!visited[w]){
this.topSortHelper(visited[w],visited,stack);
}
}
stack.push(v);
}
- js實(shí)現(xiàn)無(wú)限層級(jí)樹(shù)形數(shù)據(jù)結(jié)構(gòu)(創(chuàng)新算法)
- JS中的算法與數(shù)據(jù)結(jié)構(gòu)之字典(Dictionary)實(shí)例詳解
- JS中的算法與數(shù)據(jù)結(jié)構(gòu)之隊(duì)列(Queue)實(shí)例詳解
- JS中的算法與數(shù)據(jù)結(jié)構(gòu)之列表(List)實(shí)例詳解
- JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之集合(Set)
- JS數(shù)據(jù)結(jié)構(gòu)與算法中的隊(duì)列結(jié)構(gòu)詳解
相關(guān)文章
JavaScript的Set數(shù)據(jù)結(jié)構(gòu)詳解
這篇文章主要為大家介紹了JavaScript的Set數(shù)據(jù)結(jié)構(gòu)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-01-01
事件處理是對(duì)象化編程的一個(gè)很重要的環(huán)節(jié)，沒(méi)有了事件處理，程序就會(huì)變得很死，缺乏靈活性。2009-01-01
下面小編就為大家?guī)?lái)一篇js閉包引起的事件注冊(cè)問(wèn)題介紹。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-03-03
這篇文章介紹了ES6中函數(shù)的用法，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-05-05
JavaScipt中的Math.ceil() 、Math.floor() 、Math.round() 三個(gè)函數(shù)的理解
以前一直會(huì)三個(gè)函數(shù)的使用產(chǎn)生混淆，現(xiàn)在通過(guò)對(duì)三個(gè)函數(shù)的原型定義的理解，其實(shí)很容易記住三個(gè)函數(shù)。2010-04-04
JS的垃圾回收機(jī)制是為了以防內(nèi)存泄漏，內(nèi)存泄漏的含義就是當(dāng)已經(jīng)不需要某塊內(nèi)存時(shí)這塊內(nèi)存還存在著，垃圾回收機(jī)制就是間歇的不定期的尋找到不再使用的變量，并釋放掉它們所指向的內(nèi)存。下面我們來(lái)一起深入學(xué)習(xí)一下吧2019-06-06
ie和firefox中img對(duì)象區(qū)別的困惑
ie和firefox中img對(duì)象區(qū)別的困惑...2006-12-12
分享5個(gè)頂級(jí)的JavaScript Ajax組件庫(kù)
AJAX是用來(lái)對(duì)服務(wù)器進(jìn)行異步HTTP調(diào)用的一系列web開(kāi)發(fā)技術(shù)客戶端框架,本文為大家分享了5個(gè)頂級(jí)的JavaScript Ajax組件庫(kù)2018-09-09
JavaScript是一種基于對(duì)象和事件驅(qū)動(dòng)的客戶端腳本語(yǔ)言。JavaScript最初的設(shè)計(jì)是為了檢驗(yàn)HTML表單輸入的正確性。javaScript起源于Netscape公司的LiveScript語(yǔ)言。2009-08-08
本文從javascript簡(jiǎn)介開(kāi)始，介紹了javascript的語(yǔ)法以及注意事項(xiàng)、動(dòng)態(tài)語(yǔ)言、引用外部JS文件、變量命名規(guī)則、判斷是否已經(jīng)聲明、不存在塊級(jí)作用域這些方面的內(nèi)容，是篇相當(dāng)不錯(cuò)的基礎(chǔ)語(yǔ)法的介紹文章，推薦給小伙伴們2015-02-02