資訊專欄INFORMATION COLUMN
摘要：構(gòu)建圖添加頂點(diǎn)用數(shù)組存儲(chǔ)圖中所有頂點(diǎn)的名字添加邊用對(duì)象的形式存儲(chǔ)每個(gè)頂點(diǎn)包含的邊功能打印廣度優(yōu)先遍歷采用隊(duì)列數(shù)據(jù)結(jié)構(gòu)廣度優(yōu)先遍歷采用隊(duì)列數(shù)據(jù)結(jié)構(gòu)未發(fā)現(xiàn)的全部入列，并且標(biāo)識(shí)為已發(fā)現(xiàn)深度優(yōu)先遍歷初始化顏色構(gòu)建函數(shù)基于廣度優(yōu)先的最短路徑生成算法設(shè)
構(gòu)建圖：
1、添加頂點(diǎn)：用數(shù)組存儲(chǔ)圖中所有頂點(diǎn)的名字
this.addVertex = function(v) {
vertices.push(v);
adjList[v] = [];
}
2、添加邊 ：用對(duì)象的形式存儲(chǔ)每個(gè)頂點(diǎn)包含的邊
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、廣度優(yōu)先遍歷（采用隊(duì)列數(shù)據(jù)結(jié)構(gòu)）
let initColor = function() {
let color = [];
for(let i=1; i
3、深度優(yōu)先遍歷
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
構(gòu)建函數(shù)：
1、基于廣度優(yōu)先的最短路徑生成算法
let zuiduan = function(from,to){
let v = to; //設(shè)置當(dāng)前點(diǎn)
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());
}
};
//隊(duì)列
let Queue= function() {
let items = [];
//入隊(duì)
this.enqueue = function(element) {
items.push(element);
};
//出隊(duì)
this.dequeue = function() {
return items.shift();
};
//查看隊(duì)列頭
this.front = function() {
return items[0];
};
//檢查隊(duì)列是否為空
this.isEmpty = function() {
return items.length === 0;
};
//隊(duì)列大小
this.size = function() {
return items.length;
};
};
//圖
let Graph = function() {
//頂點(diǎn)(用數(shù)組存儲(chǔ)圖中所有頂點(diǎn)的名字)
let vertices = [];
//邊（用對(duì)象的形式存儲(chǔ)每個(gè)頂點(diǎn)包含的邊）
let adjList = {};
//1、添加頂點(diǎn)
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
結(jié)果測(cè)試
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
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/106512.html
摘要：貢獻(xiàn)者飛龍版本最近總是有人問我，把這些資料看完一遍要用多長時(shí)間，如果你一本書一本書看的話，的確要用很長時(shí)間。為了方便大家，我就把每本書的章節(jié)拆開，再按照知識(shí)點(diǎn)合并，手動(dòng)整理了這個(gè)知識(shí)樹。 Special Sponsors showImg(https://segmentfault.com/img/remote/1460000018907426?w=1760&h=200); 貢獻(xiàn)者：飛龍版...
摘要：先序遍歷的一種應(yīng)用是打印一個(gè)結(jié)構(gòu)化的文檔。方法的實(shí)現(xiàn)如下中序遍歷中序遍歷是一種以上行順序訪問所有節(jié)點(diǎn)的遍歷方式，也就是以從最小到最大的順序訪問所有節(jié)點(diǎn)。中序遍歷的一種應(yīng)用就是對(duì)樹進(jìn)行排序操作。 1、二叉搜索樹(兩個(gè)條件)： （1）二叉樹中的節(jié)點(diǎn)最多只有兩個(gè)子節(jié)點(diǎn)：一個(gè)是左側(cè)節(jié)點(diǎn)，另一個(gè)是右側(cè)子節(jié)點(diǎn)；（2）只允許在左側(cè)節(jié)點(diǎn)存儲(chǔ)（比父節(jié)點(diǎn)）小的值，在右側(cè)節(jié)點(diǎn)存儲(chǔ)（比父節(jié)點(diǎn)）大（或者等于）的...
摘要：平衡二叉樹代碼實(shí)現(xiàn)根節(jié)點(diǎn)插入節(jié)點(diǎn)樹為空樹不為空比較小于往左走大于往右走空樹樹非空自平衡樹插入新節(jié)點(diǎn)向左走向左子樹拆入新節(jié)點(diǎn)，且節(jié)點(diǎn)的值小于其左子節(jié)點(diǎn)時(shí)，應(yīng)該進(jìn)行旋轉(zhuǎn)。 平衡二叉樹JS代碼實(shí)現(xiàn) var Tree = function() { var Node = function(value) { this.value = value; this....
摘要：此處應(yīng)該有掌聲前言讀學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法第章數(shù)組，本節(jié)將為各位小伙伴分享數(shù)組的相關(guān)知識(shí)概念創(chuàng)建方式常見方法以及數(shù)組的新功能。數(shù)組數(shù)組是最簡(jiǎn)單的內(nèi)存數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)一系列同一種數(shù)據(jù)類型的值。 定場(chǎng)詩 大將生來膽氣豪，腰橫秋水雁翎刀。 風(fēng)吹鼉鼓山河動(dòng)，電閃旌旗日月高。 天上麒麟原有種，穴中螻蟻豈能逃。 太平待詔歸來日，朕與先生解戰(zhàn)袍。 此處應(yīng)該有掌聲... 前言 讀《學(xué)習(xí)JavaScrip...
摘要：一旦我們滿足了基本條件值為，我們將不再調(diào)用遞歸函數(shù)，只是有效地執(zhí)行了。遞歸深諳函數(shù)式編程之精髓，最被廣泛引證的原因是，在調(diào)用棧中，遞歸把大部分顯式狀態(tài)跟蹤換為了隱式狀態(tài)。 原文地址：Functional-Light-JS 原文作者：Kyle Simpson－《You-Dont-Know-JS》作者 關(guān)于譯者：這是一個(gè)流淌著滬江血液的純粹工程：認(rèn)真，是 HTML 最堅(jiān)實(shí)的梁柱；...
閱讀 3355·2023-04-25 16:25
閱讀 3902·2021-11-15 18:01
閱讀 1642·2021-09-10 11:21
閱讀 3073·2021-08-02 16:53
閱讀 3114·2019-08-30 15:55
閱讀 2514·2019-08-29 16:24
閱讀 2128·2019-08-29 13:14
閱讀 1071·2019-08-29 13:00
