JavaScript數(shù)據(jù)結(jié)構(gòu)和算法之圖和圖算法
圖的定義
圖（Graph）是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G(V,E)，其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。
有向圖
有向邊：若從頂點Vi到Vj的邊有方向，則稱這條邊為有向邊，也成為弧(Arc)，用有序偶<Vi,Vj>來表示，Vi稱為弧尾，Vj稱為弧頭。
無序圖
無向邊：若頂點Vi到Vj之間的邊沒有方向，則稱這條邊為無向邊(Edge)，用無序偶(Vi,Vj)來表示。
簡單圖
簡單圖：在圖結(jié)構(gòu)中，若不存在頂點到其自身的邊，且同一條邊不重復(fù)出現(xiàn)，則稱這樣的圖為簡單圖。
圖類
表示頂點
創(chuàng)建圖類的第一步就是要創(chuàng)建一個Vertex類來保存頂點和邊。這個類的作用和鏈表、二叉搜索樹的Node類一樣。Vertex類有兩個數(shù)據(jù)成員：一個用于標(biāo)識頂點，另一個表明是否被訪問過的布爾值。分別被命名為label和wasVisited。
function Vertex(label){
this.label = label;
}
我們將所有頂點保存在數(shù)組中，在圖類里，可以通過他們在數(shù)組中的位置引用他們
表示邊
圖的實際信息都保存在“邊”上面，因為他們描述了圖的結(jié)構(gòu)。二叉樹的一個父節(jié)點只能有兩個子節(jié)點，而圖的結(jié)構(gòu)卻要靈活得多，一個頂點既可以有一條邊，也可以有多條邊和它相連。
我們將表示圖的邊的方法成為鄰接表或者鄰接表數(shù)組。它將存儲由頂點的相鄰頂點列表構(gòu)成的數(shù)組
構(gòu)建圖
定義如下一個Graph類：
function Graph(v){
this.vertices = v;//vertices至高點
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;
}
這個類會記錄一個圖表示了多少條邊，并使用一個長度與圖的頂點數(shù)來記錄頂點的數(shù)量。
function addEdge(){
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
}
這里我們使用for循環(huán)為數(shù)組中的每個元素添加一個子數(shù)組來存儲所有的相鄰頂點，并將所有元素初始化為空字符串。
圖的遍歷
深度優(yōu)先遍歷
深度優(yōu)先遍歷(DepthFirstSearch)，也有稱為深度優(yōu)先搜索，簡稱為DFS。
比如在一個房間內(nèi)尋找一把鑰匙，無論從哪一間房間開始都可以，將房間內(nèi)的墻角、床頭柜、床上、床下、衣柜、電視柜等挨個尋找，做到不放過任何一個死角，當(dāng)所有的抽屜、儲藏柜中全部都找遍后，接著再尋找下一個房間。
深度優(yōu)先搜索：
深度優(yōu)先搜索就是訪問一個沒有訪問過的頂點，將他標(biāo)記為已訪問，再遞歸地去訪問在初始頂點的鄰接表中其他沒有訪問過的頂點
為Graph類添加一個數(shù)組：
this.marked = [];//保存已訪問過的頂點
for(var i=0;i<this.vertices;++i){
this.marked[i] = false;//初始化為false
}
深度優(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é)點，以找尋結(jié)果。換句話說，它并不考慮結(jié)果的可能位置，徹底地搜索整張圖，直到找到結(jié)果為止。
廣度優(yōu)先搜索從第一個頂點開始，嘗試訪問盡可能靠近它的頂點，如下圖所示：
其工作原理為：
1. 首先查找與當(dāng)前頂點相鄰的未訪問的頂點，將其添加到已訪問頂點列表及隊列中；
2. 然后從圖中取出下一個頂點v，添加到已訪問的頂點列表
3. 最后將所有與v相鄰的未訪問頂點添加到隊列中
下面是廣度優(yōu)先搜索函數(shù)的定義：
function bfs(s){
var queue = [];
this.marked = true;
queue.push(s);//添加到隊尾
while(queue.length>0){
var v = queue.shift();//從隊首移除
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)先搜索時，會自動查找從一個頂點到另一個相連頂點的最短路徑
確定路徑
要查找最短路徑，需要修改廣度優(yōu)先搜索算法來記錄從一個頂點到另一個頂點的路徑，我們需要一個數(shù)組來保存從一個頂點操下一個頂點的所有邊，我們將這個數(shù)組命名為edgeTo
this.edgeTo = [];//將這行添加到Graph類中
//bfs函數(shù)
function bfs(s){
var queue = [];
this.marked = true;
queue.push(s);//添加到隊尾
while(queue.length>0){
var v = queue.shift();//從隊首移除
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ù)渑判驎τ邢驁D的所有頂點進(jìn)行排序，使有向邊從前面的頂點指向后面的頂點。
拓?fù)渑判蛩惴ㄅcBFS類似，不同的是，拓?fù)渑判蛩惴ú粫⒓摧敵鲆言L問的頂點，而是訪問當(dāng)前頂點鄰接表中的所有相鄰頂點，直到這個列表窮盡時，才會將當(dāng)前頂點壓入棧中。
拓?fù)渑判蛩惴ū徊鸱譃閮蓚€函數(shù)，第一個函數(shù)是topSort()，用來設(shè)置排序進(jìn)程并調(diào)用一個輔助函數(shù)topSortHelper()，然后顯示排序好的頂點列表
拓?fù)渑判蛩惴ㄖ饕ぷ魇窃谶f歸函數(shù)topSortHelper()中完成的，這個函數(shù)會將當(dāng)前頂點標(biāo)記為已訪問，然后遞歸訪問當(dāng)前頂點鄰接表中的每個頂點，標(biāo)記這些頂點為已訪問。最后，將當(dāng)前頂點壓入棧中。
//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);
}
相關(guān)文章
本篇文章，小編將與大家談?wù)凧avaScript中的函數(shù)與閉包，有需要的朋友可以參考一下2013-04-04
JavaScript 學(xué)習(xí)筆記一些小技巧，大家可以參考下，比較實用的知識。2010-03-03
利用下面的腳本方便返回當(dāng)前網(wǎng)頁的url,一般自己可以根據(jù)需要利用2008-09-09
關(guān)于javascript中的typeof和instanceof介紹
typeof用來檢測給定變量的數(shù)據(jù)類型 instanceof用來檢測對象的類型2012-12-12
下面小編就為大家?guī)硪黄狫S函數(shù)定義方式的區(qū)別介紹。小編覺得挺不錯的，現(xiàn)在分享給大家，給大家一個參考。一起跟隨小編過來看看吧2016-03-03
JS,CSS加載中的一些小問題，或許大家早已把它遺忘，下面和大家一起重溫下，感興趣的朋友可以不要錯過2013-11-11
本節(jié)我將分享我對函數(shù)，嵌套函數(shù)，作為數(shù)據(jù)的函數(shù)，作為對象的函數(shù)等2012-04-04
MVC+Layui彈出表單模態(tài)框的實現(xiàn)代碼
這篇文章主要介紹了MVC+Layui彈出表單模態(tài)框的實現(xiàn)代碼,本文結(jié)合實例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友參考下吧2024-01-01
這篇文章主要介紹了TypeScript定義接口(interface)案例教程,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
實現(xiàn)元素復(fù)制的方法有很多，在本文將為大家介紹下使用js是如何實現(xiàn)的，下面有個不錯的示例，希望大家可以嘗試操作下2013-11-11