《學習JavaScript數據結構與算法》（第9章）（圖）

bitkylin 發布于2019-08-26 10:38 / 1967人閱讀

摘要：構建圖添加頂點用數組存儲圖中所有頂點的名字添加邊用對象的形式存儲每個頂點包含的邊功能打印廣度優先遍歷采用隊列數據結構廣度優先遍歷采用隊列數據結構未發現的全部入列，并且標識為已發現深度優先遍歷初始化顏色構建函數基于廣度優先的最短路徑生成算法設

構建圖：

1、添加頂點：用數組存儲圖中所有頂點的名字

this.addVertex = function(v) {
        vertices.push(v);
        adjList[v] = [];
    }

2、添加邊：用對象的形式存儲每個頂點包含的邊

this.addEdge = function(a,b) {
        adjList[a].push(b);
        adjList[b].push(a);
    }

功能：

1、打印

this.print= function() {
        let s = "
";
        for(let i=0; i";
            let bian = adjList[dingdian];
            for(let j=0; j
2、廣度優先遍歷（采用隊列數據結構）
let initColor = function() {
       let color = [];
       for(let i=1; i
3、深度優先遍歷
 this.dfs = function(v,callback) {
        let color = initColor();   //初始化顏色
        dfsVisite(v,color,callback);
    }

    let dfsVisite = function(u,color,callback) {
        color[u] = "grey";
        let n = adjList[u];
        for(let i=0; i
構建函數：
1、基于廣度優先的最短路徑生成算法
let  zuiduan = function(from,to){
    let v  = to; //設置當前點
    let s = g.BFS(from);
    let path = new Stack();
    while(v !== from) {
        path.push(v);
        v = s.pred[v];
    }
    path.push(v);
    let str = "";
    while(!path.isEmpty()) {
        str += path.pop() + "-";
    }
    str = str.slice(0,str.length-1);
    console.log(str);
}
全部整體代碼
//棧
let Stack = function() {
    let items = [];
    //添加元素
    this.push = function(element) {
        items.push(element);
    };
    //刪除元素
    this.pop = function() {
        return items.pop();
    };
    //查看棧頂元素
    this.peek = function() {
        return items[items.lenght -1];
    };
    //檢查棧是否為空
    this.isEmpty = function() {
        return  items.length == 0;
    } 
    //棧的長度
    this.size = function() {
        return items.length;
    }
    //清空棧
    this.clear = function() {
        items = [];
    }
    //打印棧元素
    this.print = function() {
        console.log(items.toString());
    }
};

//隊列
let Queue= function() {
    let items = [];
    //入隊
    this.enqueue = function(element) {
        items.push(element);
    };
    //出隊
    this.dequeue = function() {
        return items.shift();
    };
    //查看隊列頭
    this.front = function() {
        return items[0];
    };
    //檢查隊列是否為空
    this.isEmpty = function() {
        return items.length === 0;
    };
    //隊列大小
    this.size = function() {
        return items.length;
    };
};

//圖
let Graph = function() {
    //頂點(用數組存儲圖中所有頂點的名字)
    let vertices = [];
    //邊（用對象的形式存儲每個頂點包含的邊）
    let adjList = {};

    //1、添加頂點
    this.addVertex = function(v) {
        vertices.push(v);
        adjList[v] = [];
    }

    //2、添加邊
    this.addEdge = function(a,b) {
        adjList[a].push(b);
        adjList[b].push(a);
    }

    //打印
    this.print= function() {
        let s = "
";
        for(let i=0; i";
            let bian = adjList[dingdian];
            for(let j=0; j
結果測試
let g =new Graph;
g.addVertex("A");
g.addVertex("B");
g.addVertex("C");
g.addVertex("D");
g.addVertex("E");
g.addVertex("F");

g.addEdge("A","B");
g.addEdge("A","C");
g.addEdge("A","D");
g.addEdge("C","D");
g.addEdge("B","E");
g.addEdge("F","B");

g.print();  //A=>BCD  B=>AEF  C=>AD  D=>AC  E=>B  F=>B
g.bfs("A", function(e) {console.log(e)}); //A B C D E F
g.BFS("A");   //d:{A:0, B:1, C:1, D:1, E:2} pred:{A:null, B:"A", C:"A", D:"A", E:"B"}
g.dfs("A",function(e){console.log(e);}); //E F B D C A
zuiduan("A","E")   //A-B-F

GPU云服務器云服務器明解c語言第9章 js數據結構與算法第2 js數據結構與算法+第2 javascript基礎教程第9版

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

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

ApacheCN 人工智能知識樹 v1.0

摘要：貢獻者飛龍版本最近總是有人問我，把這些資料看完一遍要用多長時間，如果你一本書一本書看的話，的確要用很長時間。為了方便大家，我就把每本書的章節拆開，再按照知識點合并，手動整理了這個知識樹。 Special Sponsors showImg(https://segmentfault.com/img/remote/1460000018907426?w=1760&h=200); 貢獻者：飛龍版...

劉厚水 2019-06-26 19:00 評論0 收藏0
《學習JavaScript數據結構與算法》（第8章）（樹）

摘要：先序遍歷的一種應用是打印一個結構化的文檔。方法的實現如下中序遍歷中序遍歷是一種以上行順序訪問所有節點的遍歷方式，也就是以從最小到最大的順序訪問所有節點。中序遍歷的一種應用就是對樹進行排序操作。 1、二叉搜索樹(兩個條件)：（1）二叉樹中的節點最多只有兩個子節點：一個是左側節點，另一個是右側子節點；（2）只允許在左側節點存儲（比父節點）小的值，在右側節點存儲（比父節點）大（或者等于）的...

30e8336b8229 2019-08-26 10:36 評論0 收藏0
《學習JavaScript數據結構與算法》（第8章）（平衡二叉樹代碼實現）

摘要：平衡二叉樹代碼實現根節點插入節點樹為空樹不為空比較小于往左走大于往右走空樹樹非空自平衡樹插入新節點向左走向左子樹拆入新節點，且節點的值小于其左子節點時，應該進行旋轉。平衡二叉樹JS代碼實現 var Tree = function() { var Node = function(value) { this.value = value; this....

isLishude 2019-08-26 10:37 評論0 收藏0
重讀《學習JavaScript數據結構與算法-第三版》- 第3章數組（一）

摘要：此處應該有掌聲前言讀學習數據結構與算法第章數組，本節將為各位小伙伴分享數組的相關知識概念創建方式常見方法以及數組的新功能。數組數組是最簡單的內存數據結構，用于存儲一系列同一種數據類型的值。定場詩大將生來膽氣豪，腰橫秋水雁翎刀。風吹鼉鼓山河動，電閃旌旗日月高。天上麒麟原有種，穴中螻蟻豈能逃。太平待詔歸來日，朕與先生解戰袍。此處應該有掌聲... 前言讀《學習JavaScrip...

iKcamp 2019-08-26 10:46 評論0 收藏0
翻譯連載 | 第 9 章：遞歸（上）－《JavaScript輕量級函數式編程》 |《你不知道的JS》

摘要：一旦我們滿足了基本條件值為，我們將不再調用遞歸函數，只是有效地執行了。遞歸深諳函數式編程之精髓，最被廣泛引證的原因是，在調用棧中，遞歸把大部分顯式狀態跟蹤換為了隱式狀態。原文地址：Functional-Light-JS 原文作者：Kyle Simpson－《You-Dont-Know-JS》作者關于譯者：這是一個流淌著滬江血液的純粹工程：認真，是 HTML 最堅實的梁柱；...

MasonEast 2019-08-22 11:11 評論0 收藏0