資訊專欄INFORMATION COLUMN
摘要：圖的定義用圖對(duì)現(xiàn)實(shí)中的系統(tǒng)建?？梢杂脠D對(duì)現(xiàn)實(shí)中的很多系統(tǒng)建模比如對(duì)交通流量建模頂點(diǎn)可以表示街道的十字路口邊可以表示街道加權(quán)的邊可以表示限速或者車道的數(shù)量建模人員可以用這個(gè)系統(tǒng)來判斷最佳路線及最有可能堵車的街道任何運(yùn)輸系統(tǒng)都可以用圖來建模比如
圖的定義 用圖對(duì)現(xiàn)實(shí)中的系統(tǒng)建模
可以用圖對(duì)現(xiàn)實(shí)中的很多系統(tǒng)建模. 比如對(duì)交通流量建模, 頂點(diǎn)可以表示街道的十字路口, 邊可以表示街道. 加權(quán)的邊可以表示限速或者車道的數(shù)量. 建模人員可以用這個(gè)系統(tǒng)來判斷最佳路線及最有可能堵車的街道.
任何運(yùn)輸系統(tǒng)都可以用圖來建模. 比如, 航空公司可以用圖來為其飛行系統(tǒng)建模. 將每個(gè)機(jī)場(chǎng)看成頂點(diǎn), 將經(jīng)過兩個(gè)頂點(diǎn)的每條航線看作一條邊. 加權(quán)的邊可以表示從一個(gè)機(jī)場(chǎng)到另一個(gè)機(jī)場(chǎng)的航班成本, 或兩個(gè)機(jī)場(chǎng)間的距離, 這取決于建模的對(duì)象是什么.
包含局域網(wǎng)和廣域網(wǎng)(如互聯(lián)網(wǎng))在內(nèi)的計(jì)算機(jī)網(wǎng)絡(luò), 同樣經(jīng)常用圖來建模. 另一個(gè)可以用圖來建模的現(xiàn)實(shí)系統(tǒng)是消費(fèi)市場(chǎng), 頂點(diǎn)可以用來表示供應(yīng)商和消費(fèi)者.
圖類乍一看, 圖和數(shù)或者二叉樹很像, 你可能會(huì)嘗試用樹的方式去創(chuàng)建一個(gè)圖類, 用節(jié)點(diǎn)來表示每一個(gè)頂點(diǎn). 但這種情況下, 如果基于對(duì)象的方式去處理就會(huì)有問題, 因?yàn)閳D可能增長(zhǎng)到非常大. 用對(duì)象來表示圖很快就會(huì)變得效率低下, 所以我們要考慮表示頂點(diǎn)和邊的其它方案.
表示頂點(diǎn)創(chuàng)建圖類的第一步就是要?jiǎng)?chuàng)建一個(gè)Vertex類來保存頂點(diǎn)和邊. 這個(gè)類的作用于鏈表和二叉查找樹的Node類一樣. Vertex類有兩個(gè)數(shù)據(jù)成員:
label: 表示頂點(diǎn).
wasVisited: 表明這個(gè)頂點(diǎn)是否被訪問過的布爾值.
我們將所有頂點(diǎn)保存到數(shù)組中, 在圖類里, 可以通過它們?cè)跀?shù)組中的位置引用它們.
class Vertex {
constructor(label, wasVisited) {
this.label = label;
this.wasVisited = wasVisited;
}
};
表示邊
圖的實(shí)際信息都保存在邊上面, 因?yàn)樗鼈兠枋隽藞D的結(jié)構(gòu). 我們很容易像之前提到的那樣用二叉樹的方式去表示圖, 這是不對(duì)的. 二叉樹的表現(xiàn)形式相當(dāng)固定, 一個(gè)父節(jié)點(diǎn)只能有兩個(gè)子節(jié)點(diǎn), 而圖的結(jié)構(gòu)卻要靈活得多, 一個(gè)頂點(diǎn)既可以有一條邊, 也可以有多條邊與它相連.
我們將表示圖的邊的方法稱為: 鄰接表 或者 _鄰接表數(shù)組_. 這種方法將邊存儲(chǔ)為頂點(diǎn)的相鄰頂點(diǎn)列表構(gòu)成的數(shù)組, 并以此頂點(diǎn)作為索引. 使用這種方案, 當(dāng)我們?cè)诔绦蛑幸靡粋€(gè)頂點(diǎn)時(shí), 可以高效地訪問與整個(gè)頂點(diǎn)相連的所有頂點(diǎn)的列表. 比如, 如果頂點(diǎn)2與頂點(diǎn)0、1、3、4相連, 并且它存儲(chǔ)在數(shù)組中索引為2的位置, 那么, 訪問這個(gè)元素, 我們可以訪問到索引為2的位置處由頂點(diǎn)0、1、3、4組成的數(shù)組. 本章將選用這種表示方法.
0 --> [2] 1 --> [2] 2 --> [0, 1, 3, 4] 3 --> [2] 4 --> [2]
另一種表示圖邊的方法被稱為: _鄰接矩陣_. 它是一個(gè)二維數(shù)組, 其中的元素表示兩個(gè)頂點(diǎn)之間是否有一條邊.
構(gòu)建圖確定了如何在代碼中表示圖之后, 構(gòu)建一個(gè)圖的類就容易多了.
class Graph {
constructor(v) {
this.vertices = v;
this.edges = 0;
this.adj = [];
for(let i = 0; i < this.vertices; i++) {
this.adj[i] = [""];
};
}
addEdge(v, w) {
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
}
showGraph() {
let str = "";
for(let i = 0; i < this.vertices; i++) {
str += i + "-->";
for(let j = 0; j < this.vertices; j++) {
if(this.adj[i][j] != undefined) {
str += this.adj[i][j] + " ";
};
};
str += "
";
};
log(str)
};
};
這個(gè)類會(huì)記錄一個(gè)圖表示了多少條邊, 并使用一個(gè)長(zhǎng)度與圖的定點(diǎn)數(shù)相同的數(shù)組來記錄定點(diǎn)的數(shù)量. 通過for循環(huán)為數(shù)組中的每一個(gè)元素添加一個(gè)字?jǐn)?shù)組來存儲(chǔ)所有的相鄰頂點(diǎn), 并將所有元素初始化為空字符串.
添加邊addEdge()這個(gè)方法會(huì)傳入頂點(diǎn)A和B, 會(huì)先查找頂點(diǎn)A的領(lǐng)接表, 將頂點(diǎn)B添加到列表中, 然后再查找頂點(diǎn)B的領(lǐng)接表, 將頂點(diǎn)A加入列表. 最后將邊數(shù)edges加1.
showGraph()這個(gè)方法會(huì)通過打印所有頂點(diǎn)及其相鄰定點(diǎn)列表的方式來顯示圖.
const g = new Graph(5); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(2, 4); g.showGraph(); //輸出 /** 0--> 1 2 1--> 0 3 2--> 0 4 3--> 1 4--> 2 **/
以上輸出顯示, 下面的用數(shù)字0, 1等來代替頂點(diǎn)0, 頂點(diǎn)1.
0有到1和2的邊.
1有到0和3的邊.
2有到0和4的邊.
3有到1的邊.
4有到2的邊.
當(dāng)然, 這種顯示存在冗余, 例如, 0和1之間的邊和1到0之間的邊相同. 如果只是為了顯示, 這樣是不錯(cuò)的, 但是在開始探索圖的路徑之前, 需要調(diào)整一下輸出.
確定從一個(gè)指定的頂點(diǎn)可以到達(dá)其他哪些頂點(diǎn), 這是經(jīng)常對(duì)圖執(zhí)行的操作. 我們可能想通過地圖了解到從一個(gè)城鎮(zhèn)到另一個(gè)城鎮(zhèn)的路有哪些, 或者從一個(gè)機(jī)場(chǎng)到其它機(jī)場(chǎng)的航班有哪些等.
圖上的這些操作使用搜索算法執(zhí)行的. 在圖上可以執(zhí)行兩種基礎(chǔ)搜索:
深度優(yōu)先搜索.
廣度優(yōu)先搜索.
深度優(yōu)先深度優(yōu)先包括從一條路徑的其實(shí)頂點(diǎn)開始追溯, 直到到達(dá)最后一個(gè)頂點(diǎn), 然后回溯, 繼續(xù)追溯下一條路徑, 直到到達(dá)最后的頂點(diǎn), 如此往復(fù), 直到?jīng)]有路徑為止. 這不是在搜索特定的路徑, 而是通過搜索來查看在圖中有哪些路徑可以選擇.
這里盜個(gè)圖.
深度優(yōu)先: 訪問一個(gè)沒有訪問過的頂點(diǎn), 將它標(biāo)記為已訪問, 再遞歸去訪問在初始頂點(diǎn)的領(lǐng)接表中其它沒有訪問過的頂點(diǎn).
要讓該算法運(yùn)行, 需要向Graph類添加一個(gè)數(shù)組, 用來存儲(chǔ)已訪問過的頂點(diǎn)(marked), 將它所有元素的值全部初始化為false. Graph類的代碼片段顯示了這個(gè)新數(shù)組及其初始化的過程.
window.log = console.log.bind(console)
class Vertex {
constructor(label, wasVisited) {
this.label = label;
this.wasVisited = wasVisited;
}
};
class Graph {
constructor(v) {
this.vertices = v;
this.edges = 0;
this.adj = [];
this.marked = [];
for(let i = 0; i < this.vertices; i++) {
this.adj[i] = [""];
this.marked[i] = false;
};
}
addEdge(v, w) {
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
}
showGraph() {
let str = "";
for(let i = 0; i < this.vertices; i++) {
str += i + "-->";
for(let j = 0; j < this.vertices; j++) {
if(this.adj[i][j] != undefined) {
str += this.adj[i][j] + " ";
};
};
str += "
";
};
log(str)
};
// 深度優(yōu)先算法
dfs(v) {
this.marked[v] = true;
if (this.adj[v] != undefined) {
log("哪些點(diǎn)可以到達(dá): " + v);
};
(this.adj[v] || []).forEach(i => {
if(!this.marked[i]) {
this.dfs(i)
}
})
}
};
const g = new Graph(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.showGraph();
g.dfs(0);
廣度優(yōu)先
廣度優(yōu)先從第一個(gè)頂點(diǎn)開始, 嘗試訪問盡可能靠近它的頂點(diǎn). 本質(zhì)上, 這種搜索在圖上是逐層移動(dòng)的, 首先檢查最靠近第一個(gè)頂點(diǎn)的層, 再逐漸向下移動(dòng)到離起始頂點(diǎn)最遠(yuǎn)層.
這里盜個(gè)圖.
廣度優(yōu)先算法使用了抽象的隊(duì)列而不是數(shù)組來對(duì)已訪問過的頂點(diǎn)進(jìn)行排序. 算法原理:
查找與當(dāng)前頂點(diǎn)相鄰的未訪問頂點(diǎn), 將其添加到已訪問頂點(diǎn)列表及隊(duì)列中.
從圖中去除下一個(gè)頂點(diǎn)v, 添加到已訪問的頂點(diǎn)列表.
將所有與v相鄰的未訪問頂點(diǎn)添加到隊(duì)列.
// 廣度優(yōu)先算法
bfs(s) {
const queue = [];
this.marked[s] = true;
queue.push(s); // 添加至隊(duì)尾
while (queue.length) {
const v = queue.shift(); // 從隊(duì)首刪除
if (this.adj[v] != undefined) {
log("哪些點(diǎn)可以到達(dá): " + v);
};
(this.adj[v] || []).forEach(i => {
if(!this.marked[i]) {
this.marked[i] = true;
queue.push(i);
}
})
}
}
查找最短路徑
圖最常見的操作之一就是尋找從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的最短路徑. 考慮下例: 假期中, 你將在兩個(gè)星期時(shí)間里游歷10大聯(lián)盟城市, 去觀看棒球比賽. 你希望通過最短路徑算法, 找出開車游歷這10個(gè)大聯(lián)盟城市, 去觀看棒球比賽. 你希望通過最短路徑算法, 找出開車游歷這10個(gè)城市行駛的最小里程數(shù). 另一個(gè)最短路徑問題涉及創(chuàng)建一個(gè)計(jì)算機(jī)網(wǎng)絡(luò)時(shí)的開銷, 其中包括兩臺(tái)電腦之間傳遞數(shù)據(jù)的時(shí)間, 或兩臺(tái)電腦建立和維護(hù)連接的成本. 最短路徑算法可以幫助確定構(gòu)建此網(wǎng)絡(luò)的最有效方法.
廣度優(yōu)先對(duì)應(yīng)的最短路徑在執(zhí)行廣度優(yōu)先時(shí), 會(huì)自動(dòng)查找從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的最短路徑. 例如, 要查找從頂點(diǎn)A到頂點(diǎn)D的最短路徑, 我們首先會(huì)查找從A到D是否有任何一條單邊路徑, 接著查找兩條邊的路徑, 以此類推. 這是廣度優(yōu)先算法的過程, 因此我們可以輕松地修改廣度優(yōu)先算法, 找出最短路徑.
確定路徑要查找最短路徑, 需要修改廣度優(yōu)先算法來記錄從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的路徑. 需要對(duì)Graph類做一些修改.
首先, 需要一個(gè)數(shù)組來保存從一個(gè)頂點(diǎn)到下一個(gè)頂點(diǎn)的所有的邊. 我們將這個(gè)數(shù)組命名為edgeTo. 因?yàn)閺氖贾两K都是使用廣度優(yōu)先算法函數(shù), 所以每次都會(huì)遇到一個(gè)沒有標(biāo)記的頂點(diǎn), 除了對(duì)它進(jìn)行標(biāo)記外, 還會(huì)從鄰接列表中我們正在探索的那個(gè)頂點(diǎn)添加一條邊到這個(gè)頂點(diǎn).
修改了bfs()方法以及在constructor()中定義edgeTo屬性.
我們還需要一個(gè)函數(shù)pathTp()用于展示圖中連接到不同頂點(diǎn)的路徑. pathTo()創(chuàng)建一個(gè)棧, 用來存儲(chǔ)于指定頂點(diǎn)有共同邊的所有頂點(diǎn). 以及一個(gè)簡(jiǎn)單的輔助方法: hasPathTo().
window.log = console.log.bind(console)
class Vertex {
constructor(label, wasVisited) {
this.label = label;
this.wasVisited = wasVisited;
}
};
class Graph {
constructor(v) {
this.vertices = v;
this.edges = 0;
this.edgeTo = []; // 保存從一個(gè)頂點(diǎn)到下一個(gè)頂點(diǎn)的所有邊
this.adj = [];
this.marked = [];
for(let i = 0; i < this.vertices; i++) {
this.adj[i] = [""];
this.marked[i] = false;
};
}
addEdge(v, w) {
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
}
showGraph() {
let str = "";
for(let i = 0; i < this.vertices; i++) {
str += i + "-->";
for(let j = 0; j < this.vertices; j++) {
if(this.adj[i][j] != undefined) {
str += this.adj[i][j] + " ";
};
};
str += "
";
};
log(str)
}
// 深度優(yōu)先算法
dfs(v) {
this.marked[v] = true;
if (this.adj[v] != undefined) {
log("哪些點(diǎn)可以到達(dá): " + v);
};
(this.adj[v] || []).forEach(i => {
if(!this.marked[i]) {
this.dfs(i)
}
})
}
// 廣度優(yōu)先算法
bfs(s) {
const queue = [];
this.marked[s] = true;
queue.push(s); // 添加至隊(duì)尾
while (queue.length) {
const v = queue.shift(); // 從隊(duì)首刪除
if (this.adj[v] != undefined) {
log("哪些點(diǎn)可以到達(dá): " + v);
};
(this.adj[v] || []).forEach(i => {
if(!this.marked[i]) {
this.edgeTo[i] = v;
this.marked[i] = true;
queue.push(i);
}
})
}
}
// 創(chuàng)建一個(gè)棧 存儲(chǔ)于指定頂點(diǎn)有共同邊的所有頂點(diǎn)
pathTo(v) {
const source = 0;
if (!this.hasPathTo(v)) {
return undefined;
};
const path = [];
for (let i = v; i != source; i = this.edgeTo[i]) {
path.push(i);
};
path.push(source);
return path;
}
hasPathTo(v) {
return this.marked[v];
}
};
const g = new Graph(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.bfs(0);
const vertex = 4;
const paths = g.pathTo(vertex);
let res = "";
while (paths.length > 0) {
if (paths.length > 1) {
res += paths.pop() + "-";
} else {
res += paths.pop();
}
};
log(res);
輸出:
0-2-4
也就是從頂點(diǎn)0到頂點(diǎn)4的最短路徑.
拓?fù)渑判?/b>拓?fù)渑判?/em> 會(huì)對(duì)有向圖的所有頂點(diǎn)進(jìn)行排序, 使有向邊從前面的頂點(diǎn)指向后面的頂點(diǎn). eg:
-CS1
|-CS2
|-匯編語言
|-數(shù)據(jù)結(jié)構(gòu)
|-操作系統(tǒng)
|-算法
這個(gè)例子的拓?fù)渑判驅(qū)?huì)是一下序列:
CS1
CS2
匯編語言
數(shù)據(jù)結(jié)構(gòu)
操作系統(tǒng)
算法
課程3和課程4可以同時(shí)上, 課程5和課程6也可以.
這類問題被稱為 優(yōu)先級(jí)約束調(diào)度 , 每個(gè)大學(xué)生對(duì)此都很熟悉. 就好像只有先上過大學(xué)英語1的課程才能上大學(xué)英語2的課程一樣.
拓?fù)渑判蛩惴?/b>拓?fù)渑判蛩惴ㄅc深度優(yōu)先算法類似. 不同的是, 拓?fù)渑判蛩惴ú粫?huì)立即輸出已訪問的頂點(diǎn), 而是訪問當(dāng)前頂點(diǎn)鄰接表中的所有相鄰頂點(diǎn), 直到這個(gè)列表窮盡時(shí), 才將當(dāng)前頂點(diǎn)壓入棧中.
實(shí)現(xiàn)拓?fù)渑判蛩惴?/b>拓?fù)渑判蛩惴ū徊鸱譃閮蓚€(gè)方法. 第一個(gè)topSort(), 會(huì)設(shè)置排序進(jìn)程并調(diào)用一個(gè)輔助方法topSortHelper(), 然后顯示排序號(hào)的頂點(diǎn)列表.
主要工作實(shí)在遞歸方法topSortHelper()中完成的. 這個(gè)方法會(huì)將當(dāng)前頂點(diǎn)標(biāo)記為已訪問, 然后遞歸訪問當(dāng)前頂點(diǎn)領(lǐng)接表中的每個(gè)相鄰頂點(diǎn), 標(biāo)記這些頂點(diǎn)為已訪問. 最后 將當(dāng)前頂點(diǎn)壓入棧.
Graph類也將被修改, 這樣不僅可以用于數(shù)字頂點(diǎn), 還可以用于符號(hào)頂點(diǎn). 在代碼中, 每個(gè)頂點(diǎn)都只標(biāo)注了數(shù)字, 但是我們添加了一個(gè)vertexList數(shù)組, 將各個(gè)頂點(diǎn)關(guān)聯(lián)到一個(gè)符號(hào)(上面的課程名稱).
下面將展示整個(gè)部分的完整定義, 包括用于拓?fù)渑判虻姆椒? 以確保Graph類的新的定義更清晰. showGraph()方法也將被修改, 這樣可以顯示符號(hào)名稱而不只是顯示頂點(diǎn)數(shù)字.
window.log = console.log.bind(console)
class Vertex {
constructor(label) {
this.label = label;
}
};
class Graph {
constructor(v) {
this.vertices = v;
this.vertexList = [];
this.edges = 0;
this.edgeTo = []; // 保存從一個(gè)頂點(diǎn)到下一個(gè)頂點(diǎn)的所有邊
this.adj = [];
this.marked = [];
for(let i = 0; i < this.vertices; i++) {
this.adj[i] = [];
this.marked[i] = false;
};
}
topSort() {
const stack = [];
const visited = [];
for (let i = 0; i < this.vertices; i++) {
visited[i] = false;
};
for (let i = 0; i < this.vertices; i++) {
if (visited[i] == false) {
this.topSortHelper(i, visited, stack);
}
};
for (let i = stack.length - 1; i >= 0; i--) {
log(this.vertexList[stack[i]])
};
}
topSortHelper(v, visited, stack) {
visited[v] = true;
(this.adj[v] || []).forEach(w => {
if (!visited[w]) {
this.topSortHelper(w, visited, stack)
}
});
stack.push(v)
}
addEdge(v, w) {
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
}
showGraph() {
var visited = [];
for (let i = 0; i < this.vertices; i++) {
let str = this.vertexList[i] + "-->";
visited.push(this.vertexList[i]);
for (let j = 0; j < this.vertices; j++) {
if (this.adj[i][j] != undefined) {
if (visited.indexOf(this.vertexList[j]) < 0) {
str += this.vertexList[j] + " ";
}
}
};
visited.pop();
log(str)
};
log(" ");
}
// 深度優(yōu)先算法
dfs(v) {
this.marked[v] = true;
if (this.adj[v] != undefined) {
log("哪些點(diǎn)可以到達(dá): " + v);
};
(this.adj[v] || []).forEach(i => {
if(!this.marked[i]) {
this.dfs(i)
}
})
}
// 廣度優(yōu)先算法
bfs(s) {
const queue = [];
this.marked[s] = true;
queue.push(s); // 添加至隊(duì)尾
while (queue.length) {
const v = queue.shift(); // 從隊(duì)首刪除
if (this.adj[v] != undefined) {
log("哪些點(diǎn)可以到達(dá): " + v);
};
(this.adj[v] || []).forEach(i => {
if(!this.marked[i]) {
this.edgeTo[i] = v;
this.marked[i] = true;
queue.push(i);
}
})
}
}
// 創(chuàng)建一個(gè)棧 存儲(chǔ)于指定頂點(diǎn)有共同邊的所有頂點(diǎn)
pathTo(v) {
const source = 0;
if (!this.hasPathTo(v)) {
return undefined;
};
const path = [];
for (let i = v; i != source; i = this.edgeTo[i]) {
path.push(i);
};
path.push(source);
return path;
}
hasPathTo(v) {
return this.marked[v];
}
};
const g = new Graph(6);
g.addEdge(1, 2);
g.addEdge(2, 5);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(0, 1);
g.vertexList = [ "CS1", "CS2", "數(shù)據(jù)結(jié)構(gòu)", "匯編語言", "操作系統(tǒng)", "算法" ];
g.showGraph();
g.topSort();
輸出結(jié)果:
CS1--> CS2-->CS1 數(shù)據(jù)結(jié)構(gòu) 匯編語言 數(shù)據(jù)結(jié)構(gòu)-->CS1 CS2 匯編語言-->CS1 操作系統(tǒng)-->CS1 算法-->CS1 CS1 CS2 操作系統(tǒng) 匯編語言 數(shù)據(jù)結(jié)構(gòu) 算法
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/98186.html
摘要：分別被命名為和。圖的遍歷深度優(yōu)先遍歷深度優(yōu)先遍歷，也有稱為深度優(yōu)先搜索，簡(jiǎn)稱為。拓?fù)渑判蛩惴ㄅc類似，不同的是，拓?fù)渑判蛩惴ú粫?huì)立即輸出已訪問的頂點(diǎn)，而是訪問當(dāng)前頂點(diǎn)鄰接表中的所有相鄰頂點(diǎn)，直到這個(gè)列表窮盡時(shí)，才會(huì)將當(dāng)前頂點(diǎn)壓入棧中。 圖的定義 圖（Graph）是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為：G(V,E)，其中，G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合，E是圖G中邊的...
摘要：為檢查長(zhǎng)度為的列表，二分查找需要執(zhí)行次操作。最后需要指出的一點(diǎn)是高水平的讀者可研究一下二叉樹關(guān)于二叉樹，戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹算法常見練習(xí)在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。 常見數(shù)據(jù)結(jié)構(gòu) 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)（必須理解和掌握） 有序數(shù)據(jù)結(jié)構(gòu)：棧、隊(duì)列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間（儲(chǔ)存空間?。?無序數(shù)據(jù)結(jié)構(gòu)：集合、字典、散列表，無序...
摘要：為檢查長(zhǎng)度為的列表，二分查找需要執(zhí)行次操作。最后需要指出的一點(diǎn)是高水平的讀者可研究一下二叉樹關(guān)于二叉樹，戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹算法常見練習(xí)在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。 常見數(shù)據(jù)結(jié)構(gòu) 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)（必須理解和掌握） 有序數(shù)據(jù)結(jié)構(gòu)：棧、隊(duì)列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間（儲(chǔ)存空間?。?無序數(shù)據(jù)結(jié)構(gòu)：集合、字典、散列表，無序...
摘要：為檢查長(zhǎng)度為的列表，二分查找需要執(zhí)行次操作。最后需要指出的一點(diǎn)是高水平的讀者可研究一下二叉樹關(guān)于二叉樹，戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹算法常見練習(xí)在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。 常見數(shù)據(jù)結(jié)構(gòu) 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)（必須理解和掌握） 有序數(shù)據(jù)結(jié)構(gòu)：棧、隊(duì)列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間（儲(chǔ)存空間小） 無序數(shù)據(jù)結(jié)構(gòu)：集合、字典、散列表，無序...
摘要：每個(gè)列表中的數(shù)據(jù)項(xiàng)稱為元素。棧被稱為一種后入先出，的數(shù)據(jù)結(jié)構(gòu)。散列使用的數(shù)據(jù)結(jié)構(gòu)叫做散列表。不包含任何成員的集合稱為空集，全集則是包含一切可能成員的集合。因此二叉搜索樹需要平衡，即左右子樹高度要相近。 樓樓非計(jì)算機(jī)專業(yè)，但是對(duì)計(jì)算機(jī)也還算喜歡。個(gè)人理解若有偏差，歡迎各位批評(píng)指正！ 對(duì)于數(shù)據(jù)結(jié)構(gòu)和算法一直是我的薄弱環(huán)節(jié)，相信大多數(shù)前端工程師可能多少會(huì)有些這方面的弱點(diǎn)，加上數(shù)據(jù)結(jié)構(gòu)和算法本...
閱讀 2689·2021-11-16 11:53
閱讀 2755·2021-07-26 23:38
閱讀 2085·2019-08-30 15:55
閱讀 1766·2019-08-30 13:21
閱讀 3691·2019-08-29 17:26
閱讀 3319·2019-08-29 13:20
閱讀 887·2019-08-29 12:20
閱讀 3211·2019-08-26 10:21
