用JavaScript實現圖的廣度優先和深度優先遍歷

Hydrogen 發布于2019-08-23 17:11 / 3521人閱讀

摘要：圖的相關術語有一條邊相連的頂點叫相鄰頂點一個頂點的度就是該頂點的相鄰頂點數路徑指頂點組成的連續序列簡單路徑沒有重復頂點有向圖和無向圖圖的表示鄰接矩陣代表節點和節點相鄰，否則不相鄰鄰接表相當于把每個節點的相鄰節點一一列舉出來。

1.圖的相關術語

1.1.有一條邊相連的頂點叫相鄰頂點；
1.2.一個頂點的度就是該頂點的相鄰頂點數；
1.3.路徑指頂點組成的連續序列；
1.4.簡單路徑沒有重復頂點；
1.5.有向圖和無向圖

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

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

2.2.鄰接表

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

2.3.關聯矩陣

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

3.創建圖類

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

3.1.創建字典類

/創建字典類
    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查找特定的數值并返回，這里主要用來查找頂點對應的邊數組
    this.get = function(key){
        return this.has(key) ? items[key] : undefined;
    }
}

3.2.創建圖類

//創建圖類Graph()
function Graph(){
    var vertices = [];    //用來儲存頂點
    var adjList = new Dictionary();    //用來儲存邊

    //創建initializeColor用來初始化各個頂點的顏色，為遍歷過程中的標記做準備
    var initializeColor = function(){
        var color = [];
        for (var i=0; i";
            var neighbors = adjList.get(vertices[i]);
            for(var j=0; j
3.3.創建實例
//創建實例
var graph = new Graph();
var myVertices = ["A","B","C","D","E","F","G","H","I"];
//添加頂點
for(var i=0; i
輸出的結果為：
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.廣度優先遍歷

采用隊列的方式，先添加節點的先被探索；
采用三種顏色來反應節點的狀態：
白色：還沒被訪問；
灰色：被訪問但未被探索；
黑色：被訪問且探索過；
思路：
首先搜索節點A，探索A節點的相鄰節點B,C,D,把其加入隊列中，再逐一出隊列進行探索，從而實現廣度遍歷。
添加bfs方法
//廣度優先遍歷，在Graph()類中添加以下方法
    this.bfs = function(v, callback){
        var color = initializeColor();    //初始化節點，都標記為白色
        var queue = [];    //創建隊列用來頂點的入隊；
        queue.push(v);    //訪問的節點入隊列
        while(!queue.length==0){    //如果隊列非空就執行以下
            var u = queue.shift();    //節點出隊列
            var neighbors = adjList.get(u);  //探索節點對應的邊
            color[u] = "grey";    //把搜索過的節點變成灰色
            for (var i=0; i
創建bfs實例
//bfs實例
function printNode(value){
    console.log("Visited vertex:"+value);
}
graph.bfs(myVertices[0],printNode);

bfs輸出結果
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 = [];    //用來儲存節點的前溯點
        queue.push(v);

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

//搜索路徑BFS
var fromVertex = myVertices[0];
for (var i=1; i
BFS輸出結果
A-B
A-C
A-D
A-B-E
A-B-F
A-C-G
A-D-H
A-B-E-I

4.2.深度優先遍歷

采用棧的方式，先添加節點的先被探索；
由遞歸實現。

思路：
從節點A開始，探索到A的相鄰節點B,C,D壓入棧中（這里的代碼采用for循環，所以沒有實質上的棧，但是用棧更容易理解），接著搜索B，探索到B的相鄰節點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
}
創建dfs實例
graph.dfs(printNode);

dfs輸出結果
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

關注微信公眾號“廈猿”，獲取更多前端學習資料！

GPU云服務器云服務器廣度優先遍歷廣度優先搜索 python廣度優先廣度優先搜索算法代碼

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/103940.html

圖的JS實現

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

LeanCloud 2019-08-21 17:00 評論0 收藏0
Javascript的數據結構與算法(三)

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

MasonEast 2019-08-21 11:24 評論0 收藏0
JS算法之深度優先遍歷(DFS)和廣度優先遍歷(BFS)

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

roadtogeek 2019-08-23 16:33 評論0 收藏0
算法系列——JavaScript中廣度優先搜索思想實現

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

everfly 2019-08-21 17:36 評論0 收藏0