BFS,DFS 算法原理及js實(shí)現(xiàn)

劉德剛發(fā)布于2019-08-22 11:19 / 2220人閱讀

1. 說明

本文所有的算法嚴(yán)格按照《算法導(dǎo)論》，本文將詳細(xì)的對BFS和DFS進(jìn)行分析，并提供算法的 js 實(shí)現(xiàn)，同時(shí)會對創(chuàng)建鏈表的方式進(jìn)行優(yōu)化

2. 圖的表示

圖的表示分為對頂點(diǎn)集 V 的表示和對邊集 E 的表示，這里的重點(diǎn)是如何表示邊，邊的表示分為鄰接矩陣和鄰接鏈表這兩種表示方法，鄰接矩陣適合表示邊稠密的圖，其消耗空間為|V|*|V|,如果是無向圖，則可以用上三角矩陣或者下三角矩陣來表示，是空間消耗變?yōu)?b>|V|*|V|/2，鄰接鏈表適合表示邊稀疏的圖，其消耗的空間為 O(|V|+|E|),用鄰接鏈表表示圖很緊湊，沒有空間浪費(fèi)，用《算法導(dǎo)論》中的原話就是，鄰接鏈表表示圖，魯棒性很高。本文涉及的圖，全部用鄰接鏈表表示。

2.1. 本文的算法都是對該圖的操作

2.2. 對上圖進(jìn)行鄰接鏈表的轉(zhuǎn)化

從上圖可以看到我們將圖的分為兩部分，頂點(diǎn)和邊，我們分別對這兩部分進(jìn)行表示，我們用數(shù)組去存放頂點(diǎn)，用鏈表去描述邊。A-E 做為節(jié)點(diǎn)的標(biāo)識。數(shù)字表示頂點(diǎn)在數(shù)組中的位置。由這幅圖可以看到從節(jié)點(diǎn) A 發(fā)出的邊有兩條，分別是 ,和

3. BFS 廣度優(yōu)先搜索

廣度優(yōu)先搜索的思想是，對于圖G和給定的節(jié)點(diǎn)s，廣度優(yōu)先搜索需要一個(gè)輔助的先進(jìn)先出的隊(duì)列 Q

將s加入到Q中

將s從Q總移出，用臨時(shí)變量接受s，如果s沒有被訪問過，從s出發(fā)，發(fā)現(xiàn)s的所有鄰接節(jié)點(diǎn)并放入Q中

訪問s

將Q隊(duì)列的第一個(gè)元素移除隊(duì)列作為新的s執(zhí)行2-4過程直到隊(duì)列Q為空

3.1 表示頂點(diǎn)的數(shù)據(jù)結(jié)構(gòu)

function Vertex() {
    if (!(this instanceof Vertex))
        return new Vertex();
    this.color = this.WHITE; //初始為 白色
    this.pi = null; //初始為 無前驅(qū)
    this.d = this.INFINITY; //初始為 無窮大
    this.edges = null; //由頂點(diǎn)發(fā)出的所有邊
    this.value = null; //節(jié)點(diǎn)的值 默認(rèn)為空
}
Vertex.prototype = {
    constructor: Vertex,
    WHITE: "white", //白色
    GRAY: "gray", //灰色
    BLACK: "black", //黑色
    INFINITY: null, //d 為 null 時(shí)表示無窮大
}

為了跟蹤算法的進(jìn)展，我們對圖進(jìn)行搜索的時(shí)候會對圖中的頂點(diǎn)進(jìn)行涂色，圖初始化是頂點(diǎn)全部為白色，當(dāng)?shù)谝淮伟l(fā)現(xiàn)某個(gè)節(jié)點(diǎn)時(shí)，我們將他涂為灰色，當(dāng)對某個(gè)節(jié)點(diǎn)訪問完成后，我們將它涂為黑色。在這里我們看到每個(gè)節(jié)點(diǎn)都有五個(gè) 屬性，color表示節(jié)點(diǎn)的顏色，pi 表示前驅(qū)結(jié)點(diǎn)，d 表示廣度優(yōu)先搜索中從源節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的距離，edges 表示從當(dāng)前節(jié)點(diǎn)發(fā)出的所有邊，value 表示節(jié)點(diǎn)存放的數(shù)據(jù)

3.2 表示邊的數(shù)據(jù)結(jié)構(gòu)

function Edge() {
    if (!(this instanceof Edge))
        return new Edge();
    this.index = null; //邊所依附的節(jié)點(diǎn)的位置
    this.sibling = null;
}

可以看到，邊包含兩個(gè)兩個(gè)屬性，index，和sibling，index表示這條邊連接的節(jié)點(diǎn)在頂點(diǎn)數(shù)組中的位置，sibling只想下一個(gè)連接兄弟節(jié)點(diǎn)的邊。

3.3 表示圖的數(shù)據(jù)結(jié)構(gòu)

function Graph() {
    if (!(this instanceof Graph))
        return new Graph();
    this.graph = []; //存放頂點(diǎn)的數(shù)組
}
Graph.prototype = {
    constructor: Graph,
    addNode: function (node) {
        this.graph.push(node);
    },
    getNode: function (index) {
        return this.graph[index];
    }
}

3.4 構(gòu)建圖

//創(chuàng)建 頂點(diǎn)
var vA = Vertex();
var vB = Vertex();
var vC = Vertex();
var vD = Vertex();
var vE = Vertex();
var vF = Vertex();
vA.value = "A";
vB.value = "B";
vC.value = "C";
vD.value = "D";
vE.value = "E";
vF.value = "F";

//構(gòu)建由 A 節(jié)點(diǎn)發(fā)出的邊集
var eA1 = Edge();
var eA2 = Edge();
eA1.index = 1;
eA2.index = 3;
eA1.sibling = eA2;
vA.edges = eA1;

//構(gòu)建有 B 節(jié)點(diǎn)發(fā)出的邊集
var eB1 = Edge();
var eB2 = Edge();
var eB3 = Edge();
eB1.index = 0;
eB2.index = 4;
eB3.index = 2;
eB1.sibling = eB2;
eB2.sibling = eB3;
vB.edges = eB1;

//構(gòu)建由 C 節(jié)點(diǎn)發(fā)出的邊
var eC1 = Edge();
var eC2 = Edge();
var eC3 = Edge();
eC1.index = 1;
eC2.index = 4;
eC3.index = 5;
eC1.sibling = eC2;
eC2.sibling = eC3;
vC.edges = eC1;

//構(gòu)建由 D 節(jié)點(diǎn)發(fā)出的邊
var eD1 = Edge();
eD1.index = 0;
vD.edges = eD1;

//構(gòu)建由 E 節(jié)點(diǎn)發(fā)出的邊
var eE1 = Edge();
var eE2 = Edge();
var eE3 = Edge();
eE1.index = 1;
eE2.index = 2;
eE3.index = 5;
eE1.sibling = eE2;
eE2.sibling = eE3;
vE.edges = eE1;

//構(gòu)建由 F 節(jié)點(diǎn)發(fā)出的邊
var eF1 = Edge();
var eF2 = Edge();
eF1.index = 2;
eF2.index = 4;
eF1.sibling = eF2;
vF.edges = eF1;

//構(gòu)建圖
var g = Graph();
g.addNode(vA);
g.addNode(vB);
g.addNode(vC);
g.addNode(vD);
g.addNode(vE);
g.addNode(vF);

3.5 BFS算法

//廣度優(yōu)先搜索
function BFS(g, s) {
    let queue = []; //輔助隊(duì)列 Q
    s.color = s.GRAY; //首次發(fā)現(xiàn)s涂為灰色
    s.d = 0; //距離為0
    queue.push(s); //將s放入隊(duì)列 Q
    while (queue.length > 0) { //當(dāng)隊(duì)列Q中有頂點(diǎn)時(shí)執(zhí)行搜索
        let u = queue.shift(); //將Q中的第一個(gè)元素移出
        if (u.edges == null) continue; //如果從當(dāng)前頂點(diǎn)沒有發(fā)出邊
        let sibling = u.edges; //獲取表示鄰接邊的鏈表的頭節(jié)點(diǎn)
        while (sibling != null) { //當(dāng)鏈表不為空
            let index = sibling.index; //當(dāng)前邊所連接的頂點(diǎn)在隊(duì)列中的位置
            let n = g.getNode(index); //獲取頂點(diǎn)
            if (n.color == n.WHITE) { //如果沒有被訪問過
                n.color = n.GRAY; //涂為灰色
                n.d = u.d + 1; //距離加1
                n.pi = u; //設(shè)置前驅(qū)節(jié)點(diǎn)
                queue.push(n); //將 n 放入隊(duì)列 Q
            }
            sibling = sibling.sibling; //下一條邊
        }
        u.color = u.BLACK; //當(dāng)前頂點(diǎn)訪問結(jié)束 涂為黑色
    }
}

3.6 完整代碼可粘貼到瀏覽器控制臺運(yùn)行

//數(shù)據(jù)結(jié)構(gòu) 鄰接鏈表-頂點(diǎn)
function Vertex() {
    if (!(this instanceof Vertex))
        return new Vertex();
    this.color = this.WHITE; //初始為 白色
    this.pi = null; //初始為 無前驅(qū)
    this.d = this.INFINITY; //初始為 無窮大
    this.edges = null; //由頂點(diǎn)發(fā)出的所有邊
    this.value = null; //節(jié)點(diǎn)的值 默認(rèn)為空
}
Vertex.prototype = {
    constructor: Vertex,
    WHITE: "white", //白色
    GRAY: "gray", //灰色
    BLACK: "black", //黑色
    INFINITY: null, //d 為 null 時(shí)表示無窮大
}

//數(shù)據(jù)結(jié)構(gòu) 鄰接鏈表-邊
function Edge() {
    if (!(this instanceof Edge))
        return new Edge();
    this.index = null; //邊所依附的節(jié)點(diǎn)的位置
    this.sibling = null;
}

//數(shù)據(jù)結(jié)構(gòu) 圖-G
function Graph() {
    if (!(this instanceof Graph))
        return new Graph();
    this.graph = [];
}
Graph.prototype = {
    constructor: Graph,
    //這里加進(jìn)來的已經(jīng)具備了邊的關(guān)系
    addNode: function (node) {
        this.graph.push(node);
    },
    getNode: function (index) {
        return this.graph[index];
    }
}

//廣度優(yōu)先搜索
function BFS(g, s) {
    let queue = [];
    s.color = s.GRAY;
    s.d = 0;
    queue.push(s);
    while (queue.length > 0) {
        let u = queue.shift();
        if (u.edges == null) continue;
        let sibling = u.edges;
        while (sibling != null) {
            let index = sibling.index;
            let n = g.getNode(index);
            if (n.color == n.WHITE) {
                n.color = n.GRAY;
                n.d = u.d + 1;
                n.pi = u;
                queue.push(n);
            }
            sibling = sibling.sibling;
        }
        u.color = u.BLACK;
        console.log(u);
    }
}

//創(chuàng)建 頂點(diǎn)
var vA = Vertex();
var vB = Vertex();
var vC = Vertex();
var vD = Vertex();
var vE = Vertex();
var vF = Vertex();
vA.value = "A";
vB.value = "B";
vC.value = "C";
vD.value = "D";
vE.value = "E";
vF.value = "F";

//構(gòu)建由 A 節(jié)點(diǎn)發(fā)出的邊集
var eA1 = Edge();
var eA2 = Edge();
eA1.index = 1;
eA2.index = 3;
eA1.sibling = eA2;
vA.edges = eA1;

//構(gòu)建有 B 節(jié)點(diǎn)發(fā)出的邊集
var eB1 = Edge();
var eB2 = Edge();
var eB3 = Edge();
eB1.index = 0;
eB2.index = 4;
eB3.index = 2;
eB1.sibling = eB2;
eB2.sibling = eB3;
vB.edges = eB1;

//構(gòu)建由 C 節(jié)點(diǎn)發(fā)出的邊
var eC1 = Edge();
var eC2 = Edge();
var eC3 = Edge();
eC1.index = 1;
eC2.index = 4;
eC3.index = 5;
eC1.sibling = eC2;
eC2.sibling = eC3;
vC.edges = eC1;

//構(gòu)建由 D 節(jié)點(diǎn)發(fā)出的邊
var eD1 = Edge();
eD1.index = 0;
vD.edges = eD1;

//構(gòu)建由 E 節(jié)點(diǎn)發(fā)出的邊
var eE1 = Edge();
var eE2 = Edge();
var eE3 = Edge();
eE1.index = 1;
eE2.index = 2;
eE3.index = 5;
eE1.sibling = eE2;
eE2.sibling = eE3;
vE.edges = eE1;

//構(gòu)建由 F 節(jié)點(diǎn)發(fā)出的邊
var eF1 = Edge();
var eF2 = Edge();
eF1.index = 2;
eF2.index = 4;
eF1.sibling = eF2;
vF.edges = eF1;

//構(gòu)建圖
var g = Graph();
g.addNode(vA);
g.addNode(vB);
g.addNode(vC);
g.addNode(vD);
g.addNode(vE);
g.addNode(vF);

BFS(g, vB);

頂點(diǎn)的訪問順序?yàn)?B->A->E->C->D->F

4. DFS 深度優(yōu)先搜索

特點(diǎn)
深度優(yōu)先搜索一般默認(rèn)的源點(diǎn)有多個(gè)，搜索時(shí)的前驅(qū)子圖會構(gòu)成一個(gè)深度優(yōu)先森林，這是依據(jù)深度優(yōu)先搜索的搜索結(jié)果的使用深度優(yōu)先搜索算法常常作為另一個(gè)算法的一個(gè)子程序被使用深度優(yōu)先搜索在節(jié)點(diǎn)中增加了一個(gè)發(fā)現(xiàn)的時(shí)間戳，一個(gè)訪問的時(shí)間戳，通常能幫助我們推斷算法的行為，在d-f之間是灰色，在f之后是黑色，時(shí)間戳為1到2*|v|之間的整數(shù)

算法思想
只要有可能，就在圖中盡量“深入”，總是對最近才發(fā)現(xiàn)的節(jié)點(diǎn)v的出發(fā)邊進(jìn)行探索，知道該節(jié)點(diǎn)的所有出發(fā)邊都被發(fā)現(xiàn)為止。一旦v的所有發(fā)出的邊都被發(fā)現(xiàn)，搜索則“回溯”到v的前驅(qū)節(jié)點(diǎn)，該過程一直持續(xù)到源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)都被發(fā)現(xiàn)為止，如果還有未發(fā)現(xiàn)的節(jié)點(diǎn)，則深度優(yōu)先搜索將從這些未被發(fā)現(xiàn)的節(jié)點(diǎn)中任選一個(gè)作為新的源節(jié)點(diǎn)，并重復(fù)同樣的搜索過程

4.1 算法數(shù)據(jù)結(jié)構(gòu)

深度優(yōu)先搜索的數(shù)據(jù)結(jié)構(gòu)只有在表示頂點(diǎn)時(shí)稍有不同，其它的都相同，這里給出表示頂點(diǎn)的數(shù)據(jù)結(jié)構(gòu)

function Vertex() {
    if (!(this instanceof Vertex))
        return new Vertex();
    this.color = this.WHITE; //初始為 白色
    this.pi = null; //初始為 無前驅(qū)
    this.d = null; //時(shí)間戳 發(fā)現(xiàn)時(shí)
    this.f = null; //時(shí)間戳 鄰接鏈表掃描完成時(shí)
    this.edges = null; //由頂點(diǎn)發(fā)出的所有邊
    this.value = null; //節(jié)點(diǎn)的值 默認(rèn)為空
}
Vertex.prototype = {
    constructor: Vertex,
    WHITE: "white", //白色
    GRAY: "gray", //灰色
    BLACK: "black", //黑色
}

可以看到頂點(diǎn)數(shù)據(jù)結(jié)構(gòu)中的多了一個(gè)f，同時(shí)d的含義也發(fā)生了變化d和f作為發(fā)現(xiàn)和訪問完成的時(shí)間戳，取值為從1到2*|v|

4.2 DFS算法

function DFS(g) {
    let t = 0; //時(shí)間戳
    for (let v of g.vertexs) { //讓每個(gè)節(jié)點(diǎn)都作為一次源節(jié)點(diǎn)
        if (v.color == v.WHITE) DFSVisit(g, v);
    }
    function DFSVisit(g, v) {
        t = t + 1; //時(shí)間戳加一
        v.d = t;
        v.color = v.GRAY;
        let sibling = v.edges;
        while (sibling != null) {
            let index = sibling.index;
            let n = g.getNode(index);
            if (n.color == n.WHITE) {
                n.pi = v;
                DFSVisit(g, n); //先縱向找
            }
            sibling = sibling.sibling; //利用遞歸的特性來回溯
        }
        v.color = v.BLACK;
        t = t + 1; //時(shí)間戳加一
        v.f = t;
    }
}

4.3 DFS完整代碼

function Vertex() {
    if (!(this instanceof Vertex))
        return new Vertex();
    this.color = this.WHITE; //初始為 白色
    this.pi = null; //初始為 無前驅(qū)
    this.d = null; //時(shí)間戳 發(fā)現(xiàn)時(shí)
    this.f = null; //時(shí)間戳 鄰接鏈表掃描完成
    this.edges = null; //由頂點(diǎn)發(fā)出的所有邊
    this.value = null; //節(jié)點(diǎn)的值 默認(rèn)為空
}
Vertex.prototype = {
    constructor: Vertex,
    WHITE: "white", //白色
    GRAY: "gray", //灰色
    BLACK: "black", //黑色
}

//數(shù)據(jù)結(jié)構(gòu) 圖-G
function Graph() {
    if (!(this instanceof Graph))
        return new Graph();
    this.vertexs = [];
}
Graph.prototype = {
    constructor: Graph,
    addNode: function (node) {
        this.vertexs.push(node);
    },
    getNode: function (index) {
        return this.vertexs[index];
    }
}

//這里 t 作為全局變量和參數(shù)時(shí)結(jié)果不一樣 因?yàn)?js 對于基本類型的參數(shù)采用的是值捕獲，對于對象類型的參數(shù)采用的是引用捕獲
function DFS(g) {
    let t = 0;
    for (let v of g.vertexs) {
        if (v.color == v.WHITE) DFSVisit(g, v);
    }
    function DFSVisit(g, v) {
        t = t + 1;
        v.d = t;
        v.color = v.GRAY;
        let sibling = v.edges;
        while (sibling != null) {
            let index = sibling.index;
            let n = g.getNode(index);
            if (n.color == n.WHITE) {
                n.pi = v;
                DFSVisit(g, n); //先縱向找
            }
            sibling = sibling.sibling; //利用遞歸的特性來回溯
        }
        v.color = v.BLACK;
        t = t + 1;
        v.f = t;
        console.log(v);
    }
}

//數(shù)據(jù)結(jié)構(gòu) 鄰接鏈表-邊
function Edge() {
    if (!(this instanceof Edge))
        return new Edge();
    this.index = null; //邊所依附的節(jié)點(diǎn)的位置
    this.sibling = null;
}

//創(chuàng)建 頂點(diǎn)
var vA = Vertex();
var vB = Vertex();
var vC = Vertex();
var vD = Vertex();
var vE = Vertex();
var vF = Vertex();
vA.value = "A";
vB.value = "B";
vC.value = "C";
vD.value = "D";
vE.value = "E";
vF.value = "F";

//構(gòu)建由 A 節(jié)點(diǎn)發(fā)出的邊集
var eA1 = Edge();
var eA2 = Edge();
eA1.index = 1;
eA2.index = 3;
eA1.sibling = eA2;
vA.edges = eA1;

//構(gòu)建有 B 節(jié)點(diǎn)發(fā)出的邊集
var eB1 = Edge();
var eB2 = Edge();
var eB3 = Edge();
eB1.index = 0;
eB2.index = 4;
eB3.index = 2;
eB1.sibling = eB2;
eB2.sibling = eB3;
vB.edges = eB1;

//構(gòu)建由 C 節(jié)點(diǎn)發(fā)出的邊
var eC1 = Edge();
var eC2 = Edge();
var eC3 = Edge();
eC1.index = 1;
eC2.index = 4;
eC3.index = 5;
eC1.sibling = eC2;
eC2.sibling = eC3;
vC.edges = eC1;

//構(gòu)建由 D 節(jié)點(diǎn)發(fā)出的邊
var eD1 = Edge();
eD1.index = 0;
vD.edges = eD1;

//構(gòu)建由 E 節(jié)點(diǎn)發(fā)出的邊
var eE1 = Edge();
var eE2 = Edge();
var eE3 = Edge();
eE1.index = 1;
eE2.index = 2;
eE3.index = 5;
eE1.sibling = eE2;
eE2.sibling = eE3;
vE.edges = eE1;

//構(gòu)建由 F 節(jié)點(diǎn)發(fā)出的邊
var eF1 = Edge();
var eF2 = Edge();
eF1.index = 2;
eF2.index = 4;
eF1.sibling = eF2;
vF.edges = eF1;

//構(gòu)建圖
var g = Graph();
g.addNode(vA);
g.addNode(vB);
g.addNode(vC);
g.addNode(vD);
g.addNode(vE);
g.addNode(vF);

DFS(g);

節(jié)點(diǎn)訪問順序?yàn)?F->C->E->B->D->A

5. 對構(gòu)建鏈表的方式進(jìn)行優(yōu)化

我們發(fā)現(xiàn)構(gòu)建圖的操作過于繁瑣，于是想簡化圖的構(gòu)建方式，簡化后如下

var vertexs = ["A", "B", "C", "D", "E", "F"];
var edges = {
    A: [{ id: "B", w: 1 }, { id: "D", w: 2 }],
    B: [{ id: "A", w: 3 }, { id: "E", w: 3 }, { id: "C", w: 7 }],
    C: [{ id: "B", w: 5 }, { id: "E", w: 3 }, { id: "F", w: 4 }],
    D: [{ id: "A", w: 2 }],
    E: [{ id: "B", w: 3 }, { id: "C", w: 7 }, { id: "F", w: 3 }],
    F: [{ id: "C", w: 6 }, { id: "E", w: 9 }]
}
var g = Graph();
g.initVertex(vertexs);
g.initEdge(edges);

我們想用這種方式初始化一個(gè)圖，w為邊的權(quán)值

這里的改進(jìn)只是針對圖的構(gòu)建，所有無論時(shí)BFS,還是DFS，表示頂點(diǎn)和邊的數(shù)據(jù)結(jié)構(gòu)都沒有變，只有對表示圖的數(shù)據(jù)結(jié)構(gòu) Graph進(jìn)行改進(jìn)

5.1 改進(jìn)之后的Graph

//數(shù)據(jù)結(jié)構(gòu) 圖-G

//數(shù)據(jù)結(jié)構(gòu) 圖-G
function Graph() {
    if (!(this instanceof Graph))
        return new Graph();
    this.graph = [];
    this.refer = new Map(); //字典 用來映射標(biāo)節(jié)點(diǎn)的識符和數(shù)組中的位置
}
Graph.prototype = {
    constructor: Graph,
    //這里加進(jìn)來的已經(jīng)具備了邊的關(guān)系
    addNode: function(node) {
        this.graph.push(node);
    },
    getNode: function(index) {
        return this.graph[index];
    },
    //創(chuàng)建圖的 節(jié)點(diǎn)
    initVertex: function(vertexs) {
        //創(chuàng)建節(jié)點(diǎn)并初始化節(jié)點(diǎn)屬性 value
        for (let value of vertexs) {
            let vertex = Vertex();
            vertex.value = value;
            this.graph.push(vertex);
        }
        //初始化 字典
        for (let i in this.graph) {
            this.refer.set(this.graph[i].value,i);
        }
    },
    //建立圖中 邊 的關(guān)系
    initEdge: (function(){
        //創(chuàng)建鏈表，返回鏈表的第一個(gè)節(jié)點(diǎn)
        function createLink(index, len, edges, refer) {
            if (index >= len) return null;
            let edgeNode = Edge();
            edgeNode.index = refer.get(edges[index].id); //邊連接的節(jié)點(diǎn) 用在數(shù)組中的位置表示 參照字典
            edgeNode.w = edges[index].w; //邊的權(quán)值
            edgeNode.sibling = createLink(++index, len, edges, refer); //通過遞歸實(shí)現(xiàn) 回溯
            return edgeNode;
        }
        return function(edges) {
            for (let field in edges) {
                let index = this.refer.get(field); //從字典表中找出節(jié)點(diǎn)在 graph 中的位置
                let vertex = this.graph[index]; //獲取節(jié)點(diǎn)
                vertex.edges = createLink(0, edges[field].length, edges[field], this.refer);
            }
        }
    }())
}

5.2 改進(jìn)之后的BFS完整代碼

DFS相同

function Vertex() {
    if (!(this instanceof Vertex))
        return new Vertex();
    this.color = this.WHITE; //初始為 白色
    this.pi = null; //初始為 無前驅(qū)
    this.d = this.INFINITY; //初始為 無窮大
    this.edges = null; //由頂點(diǎn)發(fā)出的所有邊
    this.value = null; //節(jié)點(diǎn)的值 默認(rèn)為空
}
Vertex.prototype = {
    constructor: Vertex,
    WHITE: "white", //白色
    GRAY: "gray", //灰色
    BLACK: "black", //黑色
    INFINITY: null, //d 為 null 時(shí)表示無窮大
}

//數(shù)據(jù)結(jié)構(gòu) 鄰接鏈表-邊
function Edge() {
    if (!(this instanceof Edge))
        return new Edge();
    this.index = null; //邊所依附的節(jié)點(diǎn)的位置
    this.sibling = null;
    this.w = null; //保存邊的權(quán)值
}

//數(shù)據(jù)結(jié)構(gòu) 圖-G
function Graph() {
    if (!(this instanceof Graph))
        return new Graph();
    this.graph = [];
    this.refer = new Map(); //字典 用來映射標(biāo)節(jié)點(diǎn)的識符和數(shù)組中的位置
}
Graph.prototype = {
    constructor: Graph,
    //這里加進(jìn)來的已經(jīng)具備了邊的關(guān)系
    addNode: function(node) {
        this.graph.push(node);
    },
    getNode: function(index) {
        return this.graph[index];
    },
    //創(chuàng)建圖的 節(jié)點(diǎn)
    initVertex: function(vertexs) {
        //創(chuàng)建節(jié)點(diǎn)并初始化節(jié)點(diǎn)屬性 value
        for (let value of vertexs) {
            let vertex = Vertex();
            vertex.value = value;
            this.graph.push(vertex);
        }
        //初始化 字典
        for (let i in this.graph) {
            this.refer.set(this.graph[i].value,i);
        }
    },
    //建立圖中 邊 的關(guān)系
    initEdge: (function(){
        //創(chuàng)建鏈表，返回鏈表的第一個(gè)節(jié)點(diǎn)
        function createLink(index, len, edges, refer) {
            if (index >= len) return null;
            let edgeNode = Edge();
            edgeNode.index = refer.get(edges[index].id); //邊連接的節(jié)點(diǎn) 用在數(shù)組中的位置表示 參照字典
            edgeNode.w = edges[index].w; //邊的權(quán)值
            edgeNode.sibling = createLink(++index, len, edges, refer); //通過遞歸實(shí)現(xiàn) 回溯
            return edgeNode;
        }
        return function(edges) {
            for (let field in edges) {
                let index = this.refer.get(field); //從字典表中找出節(jié)點(diǎn)在 graph 中的位置
                let vertex = this.graph[index]; //獲取節(jié)點(diǎn)
                vertex.edges = createLink(0, edges[field].length, edges[field], this.refer);
            }
        }
    }())
}

//廣度優(yōu)先搜索
function BFS(g, s) {
    let queue = [];
    s.color = s.GRAY;
    s.d = 0;
    queue.push(s);
    while (queue.length > 0) {
        let u = queue.shift();
        if (u.edges == null) continue;
        let sibling = u.edges;
        while (sibling != null) {
            let index = sibling.index;
            let n = g.getNode(index);
            if (n.color == n.WHITE) {
                n.color = n.GRAY;
                n.d = u.d + 1;
                n.pi = u;
                queue.push(n);
            }
            sibling = sibling.sibling;
        }
        u.color = u.BLACK;
        console.log(u)
    }
}

var vertexs = ["A", "B", "C", "D", "E", "F"];
var edges = {
    A: [{ id: "B", w: 1 }, { id: "D", w: 2 }],
    B: [{ id: "A", w: 3 }, { id: "E", w: 3 }, { id: "C", w: 7 }],
    C: [{ id: "B", w: 5 }, { id: "E", w: 3 }, { id: "F", w: 4 }],
    D: [{ id: "A", w: 2 }],
    E: [{ id: "B", w: 3 }, { id: "C", w: 7 }, { id: "F", w: 3 }],
    F: [{ id: "C", w: 6 }, { id: "E", w: 9 }]
}
//構(gòu)建圖
var g = Graph();
g.initVertex(vertexs);
g.initEdge(edges);
//調(diào)用BFS
BFS(g, g.graph[1]);

6. 總結(jié)

著重體會

1 如何用鄰接鏈表表示圖的邊

2 如何用遞歸的特性實(shí)現(xiàn)回溯

云服務(wù)器 GPU云服務(wù)器矩陣dfs算法購物車實(shí)現(xiàn)原理 js ddos攻擊原理及防范人工智能原理及應(yīng)用

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

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

發(fā)表評論

登陸后可評論

0條評論

劉德剛

男|高級講師

我要關(guān)注我要私信

TA的文章

Postman測試工具調(diào)試接口詳細(xì)教程【向后端發(fā)送Json數(shù)據(jù)并接收返回的Json結(jié)果】

閱讀 1404·2021-11-15 11:37
半月灣hmbcloud：洛杉磯CN2 GIA方案（DC5）機(jī)房，帶寬升級至200M起步，三網(wǎng)CN2

閱讀 2340·2021-09-30 09:55
換主機(jī)郵件資料怎么換-電腦換主機(jī)，如何才能保存原來的資料在新主機(jī)中？

閱讀 4866·2021-09-22 15:51
怎么刪除匿名主機(jī)-qq匿名回答怎么刪除？

閱讀 3868·2021-09-22 15:46
Bootstrap清除浮動的實(shí)現(xiàn)原理

閱讀 2855·2019-08-30 15:52
vue.js 中使用（...）運(yùn)算符報(bào)錯(cuò)

閱讀 582·2019-08-29 16:20
css流程圖、步驟圖，流程線與環(huán)節(jié)分別實(shí)現(xiàn)，支持單環(huán)節(jié)、多環(huán)節(jié)情況。scss生成CSS

閱讀 2984·2019-08-29 15:12
vue多環(huán)境配置方案

閱讀 1243·2019-08-26 18:27

亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

BFS,DFS 算法原理及js實(shí)現(xiàn)

相關(guān)文章

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

**js 中二叉樹的深度遍歷與廣度遍歷(遞歸實(shí)現(xiàn)與非遞歸實(shí)現(xiàn))**

js版本的BFS&DFS

拓?fù)渑判?em>原理分析及js實(shí)現(xiàn)

PHP面試：常見查找算法一篇說透

發(fā)表評論

0條評論

劉德剛

男|高級講師

TA的文章

Postman測試工具調(diào)試接口詳細(xì)教程【向后端發(fā)送Json數(shù)據(jù)并接收返回的Json結(jié)果】

半月灣hmbcloud：洛杉磯CN2 GIA方案（DC5）機(jī)房，帶寬升級至200M起步，三網(wǎng)CN2

換主機(jī)郵件資料怎么換-電腦換主機(jī)，如何才能保存原來的資料在新主機(jī)中？

怎么刪除匿名主機(jī)-qq匿名回答怎么刪除？

Bootstrap清除浮動的實(shí)現(xiàn)原理

vue.js 中使用（...）運(yùn)算符報(bào)錯(cuò)

css流程圖、步驟圖，流程線與環(huán)節(jié)分別實(shí)現(xiàn)，支持單環(huán)節(jié)、多環(huán)節(jié)情況。scss生成CSS

vue多環(huán)境配置方案

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

BFS,DFS 算法原理及js實(shí)現(xiàn)

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！