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