成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

用JavaScript實現(xiàn)圖的廣度優(yōu)先和深度優(yōu)先遍歷

Hydrogen / 3534人閱讀

摘要：圖的相關(guān)術(shù)語有一條邊相連的頂點叫相鄰頂點一個頂點的度就是該頂點的相鄰頂點數(shù)路徑指頂點組成的連續(xù)序列簡單路徑?jīng)]有重復(fù)頂點有向圖和無向圖圖的表示鄰接矩陣代表節(jié)點和節(jié)點相鄰，否則不相鄰鄰接表相當于把每個節(jié)點的相鄰節(jié)點一一列舉出來。

1.圖的相關(guān)術(shù)語

1.1.有一條邊相連的頂點叫相鄰頂點；
1.2.一個頂點的度就是該頂點的相鄰頂點數(shù)；
1.3.路徑指頂點組成的連續(xù)序列；
1.4.簡單路徑?jīng)]有重復(fù)頂點；
1.5.有向圖和無向圖

2.圖的表示 2.1.鄰接矩陣


arrayi ===1代表i節(jié)點和j節(jié)點相鄰，否則不相鄰

2.2.鄰接表


相當于把每個節(jié)點的相鄰節(jié)點一一列舉出來。

2.3.關(guān)聯(lián)矩陣

形式和鄰接矩陣一樣，只是把鄰接矩陣的直接維度換成對應(yīng)的邊，適用于邊比頂點多的情況。

3.創(chuàng)建圖類


接下來就采用鄰接表的方式創(chuàng)建上面的圖并且采用字典來表示：

3.1.創(chuàng)建字典類 
/創(chuàng)建字典類
    function Dictionary(){
    var items = {};
    
    //set(key,value)向字典里添加新元素，這里主要用來添加邊
    this.set = function(key,value){
        items[key] = value;
    }

    //has(key)如果存在就返回true，否則false
    this.has = function(key){
        return key in items;
    }

    //get(key)通過key查找特定的數(shù)值并返回，這里主要用來查找頂點對應(yīng)的邊數(shù)組
    this.get = function(key){
        return this.has(key) ? items[key] : undefined;
    }
}
3.2.創(chuàng)建圖類 
//創(chuàng)建圖類Graph()
function Graph(){
    var vertices = [];    //用來儲存頂點
    var adjList = new Dictionary();    //用來儲存邊

    //創(chuàng)建initializeColor用來初始化各個頂點的顏色，為遍歷過程中的標記做準備
    var initializeColor = function(){
        var color = [];
        for (var i=0; i";
            var neighbors = adjList.get(vertices[i]);
            for(var j=0; j
3.3.創(chuàng)建實例

//創(chuàng)建實例
var graph = new Graph();
var myVertices = ["A","B","C","D","E","F","G","H","I"];
//添加頂點
for(var i=0; i
輸出的結(jié)果為：

A->B C D 
B->A E F 
C->A G D 
D->A C G H 
E->B I 
F->B 
G->C D 
H->D 
I->E 


4.圖的遍歷
4.1.廣度優(yōu)先遍歷


采用隊列的方式，先添加節(jié)點的先被探索；
采用三種顏色來反應(yīng)節(jié)點的狀態(tài)：
白色：還沒被訪問；
灰色：被訪問但未被探索；
黑色：被訪問且探索過；

思路：

首先搜索節(jié)點A，探索A節(jié)點的相鄰節(jié)點B,C,D,把其加入隊列中，再逐一出隊列進行探索，從而實現(xiàn)廣度遍歷。

添加bfs方法

//廣度優(yōu)先遍歷，在Graph()類中添加以下方法
    this.bfs = function(v, callback){
        var color = initializeColor();    //初始化節(jié)點，都標記為白色
        var queue = [];    //創(chuàng)建隊列用來頂點的入隊；
        queue.push(v);    //訪問的節(jié)點入隊列
        while(!queue.length==0){    //如果隊列非空就執(zhí)行以下
            var u = queue.shift();    //節(jié)點出隊列
            var neighbors = adjList.get(u);  //探索節(jié)點對應(yīng)的邊
            color[u] = "grey";    //把搜索過的節(jié)點變成灰色
            for (var i=0; i
創(chuàng)建bfs實例

//bfs實例
function printNode(value){
    console.log("Visited vertex:"+value);
}
graph.bfs(myVertices[0],printNode);


bfs輸出結(jié)果

Visited vertex:A
Visited vertex:B
Visited vertex:C
Visited vertex:D
Visited vertex:E
Visited vertex:F
Visited vertex:G
Visited vertex:H
Visited vertex:I


使用BFS尋找最短路徑


this.BFS = function(v){
        var color = initializeColor(),
        queue = [],
        d = [],    //用來儲存從v到u的距離
        pred = [];    //用來儲存節(jié)點的前溯點
        queue.push(v);

        for(var i=0; i
創(chuàng)建BFS實例

//BFS實例
var shortestPathA = graph.BFS(myVertices[0]);//需要輸入頭節(jié)點myVertices[0]
//console.log(shortestPathA);

//搜索路徑BFS
var fromVertex = myVertices[0];
for (var i=1; i
BFS輸出結(jié)果

A-B
A-C
A-D
A-B-E
A-B-F
A-C-G
A-D-H
A-B-E-I


4.2.深度優(yōu)先遍歷


采用棧的方式，先添加節(jié)點的先被探索；
由遞歸實現(xiàn)。



思路：

從節(jié)點A開始，探索到A的相鄰節(jié)點B,C,D壓入棧中（這里的代碼采用for循環(huán)，所以沒有實質(zhì)上的棧，但是用棧更容易理解），接著搜索B，探索到B的相鄰節(jié)點E,F壓入棧中，以此遞歸。

添加dfs方法

this.dfs = function(callback){


var color = initializeColor();
for (var i=0; i

}


var dfsVisit = function(u, color, callback){


color[u] = "grey";
if(callback){
    callback(u);
}
var neighbors = adjList.get(u);
for(var i=0; i

}

創(chuàng)建dfs實例

graph.dfs(printNode);


dfs輸出結(jié)果

Visited vertex:A
Visited vertex:B
Visited vertex:E
Visited vertex:I
Visited vertex:F
Visited vertex:C
Visited vertex:G
Visited vertex:D
Visited vertex:H



關(guān)注微信公眾號“廈猿”，獲取更多前端學(xué)習資料！

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/103940.html

相關(guān)文章

  • 圖的JS實現(xiàn)

    摘要：圖的實現(xiàn)如下采用鄰接表結(jié)構(gòu)實現(xiàn)。由于本次示例的是無向圖，因此每個頂點都互相增加為鄰接點。然而由于本次示例的圖為無向圖，會出現(xiàn)重復(fù)遍歷的情況，例如頂點的鄰接點有，的鄰接點有。 圖的定義 圖就是由若干個頂點和邊連接起來的一種結(jié)構(gòu)。很多東西都可以用圖來說明，例如人際關(guān)系，或者地圖。 其中圖還分為有向圖和無向圖。如下就是有向圖 圖的數(shù)據(jù)結(jié)構(gòu) 對于圖這種關(guān)系，可以通過兩種方式來存儲。 領(lǐng)接表 將...

    LeanCloud 評論0 收藏0

  • Javascript的數(shù)據(jù)結(jié)構(gòu)與算法(三)

    摘要：存在好幾種方式來表示這種數(shù)據(jù)結(jié)構(gòu)。下面的示意圖展示了鄰接表數(shù)據(jù)結(jié)構(gòu)。在關(guān)聯(lián)矩陣中矩陣的行表示頂點列表示邊。廣度優(yōu)先搜索算法和深度優(yōu)先搜索算法基本上是相同的只有一點不同那就是待訪問頂點列表的數(shù)據(jù)結(jié)構(gòu)。 1 樹 一個樹結(jié)構(gòu)包含一系列存在父子關(guān)系的節(jié)點。每個節(jié)點都有一個父節(jié)點(除了頂部的第一個節(jié)點)以及零個或多個子節(jié)點。位于樹頂部的節(jié)點叫作根節(jié)點(11)。它沒有父節(jié)點。樹中的每個元素都叫作...

    MasonEast 評論0 收藏0

  • JS算法之深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS)

    摘要：算法之深度優(yōu)先遍歷和廣度優(yōu)先遍歷背景在開發(fā)頁面的時候，我們有時候會遇到這種需求在頁面某個節(jié)點中遍歷，找到目標節(jié)點，我們正常做法是利用選擇器，或者，但在本文，我們從算法的角度去查找節(jié)點，同時理解一下深度優(yōu)先遍歷和廣度優(yōu)先遍歷的原理。 JS算法之深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS) 背景 在開發(fā)頁面的時候，我們有時候會遇到這種需求：在頁面某個dom節(jié)點中遍歷，找到目標dom節(jié)點，...

    roadtogeek 評論0 收藏0

  • 算法系列——JavaScript中廣度優(yōu)先搜索思想實現(xiàn)

    摘要：散列表上面的地圖向我們展示了如何用廣度優(yōu)先搜索的思想找到北京到廣州的最短路線。在廣度優(yōu)先搜索中，我們需要用到隊列的這種思想來實現(xiàn)查找。建立了下面這個模型武漢廣州西藏上海上海武漢廣州代碼完整實現(xiàn)，利用遞歸和廣度優(yōu)先搜索的思想實現(xiàn)。 什么是廣度優(yōu)先搜索？ 如果只是是背概念，幼兒園的小朋友都能背下來念給你聽。 假設(shè)看這篇文章的都和我一樣是個前端工程師，我們要從廣度優(yōu)先搜索（BFS）中學(xué)到什么...

    everfly 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<