資訊專欄INFORMATION COLUMN
摘要：圖的實現如下采用鄰接表結構實現。由于本次示例的是無向圖，因此每個頂點都互相增加為鄰接點。然而由于本次示例的圖為無向圖，會出現重復遍歷的情況，例如頂點的鄰接點有，的鄰接點有。
圖的定義
圖就是由若干個頂點和邊連接起來的一種結構。很多東西都可以用圖來說明，例如人際關系，或者地圖。
其中圖還分為有向圖和無向圖。
如下就是有向圖
對于圖這種關系，可以通過兩種方式來存儲。
領接表將每個頂點與其相鄰的頂點存儲起來。
鄰接矩陣將頂點間的相鄰關系用0和1來表示，0表示不相鄰，1表示相鄰。
圖的實現如下采用鄰接表結構實現。
構造函數class Graph {
constructor() {
this.vertices = [];
this.adjList = new Map();
}
}
verrices存儲所有的頂點，adjList存儲頂點間的關系。
增addVertex(v) {
this.vertices.push(v);{1}
this.adjList.set(v, []);{2}
}
addEdge(v, w) {
this.adjList.get(v).push(w);
this.adjList.get(w).push(v);
}
addVertex函數為新增頂點。{2}是為新增的頂點初始化一個為空的鄰接點。
addEdge函數為關聯兩個頂點為鄰接點。由于本次示例的是無向圖，因此每個頂點都互相增加為鄰接點。
圖的遍歷分為廣度優先遍歷和深度優先遍歷。
廣度優先遍歷就是從一個頂點開始，一層一層的遍歷頂點。而深度優先遍歷，是從一個頂點開始，選擇一個路徑一直深入遍歷，直到到達該路徑的盡頭，再返回去，按照同樣的方式，遍歷其他頂點。
無論廣度優先還是深度優先，大致原理都是，創建一個字段，從一個頂點開始，將其鄰接點一個個存入該字段中，唯一的區別是，廣度優先遍歷，該字段用隊列存儲，而深度優先遍歷用棧存儲。
然而由于本次示例的圖為無向圖，會出現重復遍歷的情況，例如A頂點的鄰接點有B，B的鄰接點有A。因此需要創建一個類，來維護這些頂點哪些已經被遍歷過了，哪些還沒有遍歷。
class GraphStatus {
constructor() {
this.status = {};
}
detect(key) {
this.status[key] = true;
}
isDetected(key) {
return !!this.status[key];
}
}
如下是廣度優先遍歷
bfs(v, cb) {
const queue = [],
graphStatus = new GraphStatus();
queue.push(v);
while (queue.length > 0) {
const u = queue.shift();
graphStatus.detect(u);
this.adjList.get(u).forEach(item => {
if (!graphStatus.isDetected(item)) {
graphStatus.detect(item);
queue.push(item);
}
});
if (cb) {
cb(u);
}
}
}
如下是深度優先遍歷
dfs(v, cb) {
const stack = [],
colorStatus = new GraphStatus();
stack.push(v);
while (stack.length > 0) {
const u = stack.pop();
colorStatus.detect(u);
this.adjList.get(u).forEach(item => {
if (!colorStatus.isDetected(item)) {
colorStatus.detect(item);
stack.push(item);
}
});
cb(u);
}
}
最短路徑
基于廣度優先遍歷，可以很輕易的算出最短路徑。
findDepth(v) {
let queue = [],
colorStatus = new GraphStatus(),
vPath = { [v]: [v] },
vDepth = {},
depth = 0;
queue.push(v);
while (queue.length > 0) {
depth++;
const u = queue.shift();
colorStatus.detect(u);
// 相鄰頂點
const edgeVertex = this.adjList.get(u);
edgeVertex.forEach(item => {
if (!colorStatus.isDetected(item)) {
// 深度統計
vDepth[item] = depth;
// 路徑統計
vPath[item] = [...vPath[u], item];
colorStatus.detect(item);
queue.push(item);
}
});
}
return { depth: vDepth, path: vPath };
}
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/88999.html
摘要：實現一個非無限循環不自動切換的輪播圖只需要幾張圖片和兩個按鈕簡化部分兩個按鈕，幾張圖片假如有四張圖右側按鈕左側按鈕部分動態添加刪除的屬性部分已是最后一張圖這是第一張圖 實現一個非無限循環不自動切換的輪播圖只需要幾張圖片和兩個按鈕（簡化） HTML部分 兩個按鈕，幾張圖片（假如有四張圖） 右側按鈕 左側按鈕 CSS部分 動態...
摘要：條形圖條形圖提供了一種顯示以垂直長條表示的數據值的方式。這些屬性用于設置特定數據集的顯示效果。這樣做將使所有創建的氣泡圖在此之后創建新的默認值。重要的是要注意，圖表中的屬性是不可縮放的。它表示在氣泡圖上對應的氣泡的原始半徑以像素為單位。 條形圖 條形圖提供了一種顯示以垂直長條表示的數據值的方式。有時用于顯示代表某一趨勢的數據，并且可同時并排比較多個數據集。 { type: bar, d...
摘要：條形圖條形圖提供了一種顯示以垂直長條表示的數據值的方式。這些屬性用于設置特定數據集的顯示效果。這樣做將使所有創建的氣泡圖在此之后創建新的默認值。重要的是要注意，圖表中的屬性是不可縮放的。它表示在氣泡圖上對應的氣泡的原始半徑以像素為單位。 條形圖 條形圖提供了一種顯示以垂直長條表示的數據值的方式。有時用于顯示代表某一趨勢的數據，并且可同時并排比較多個數據集。 { type: bar, d...
摘要：在做可視化的很多時候，我們需要在主圖的一角設置一個縮略圖來掌握全局情況。，縮略圖的繪制完成，很簡單的例子，按照這個思路可以完成大部分可視化的縮略圖繪制。 在做可視化的很多時候，我們需要在主圖的一角設置一個縮略圖來掌握全局情況。本次將使用力導向圖作為例子，完成縮略圖的實現。 繪制的原理就是依靠主圖的數據再畫一個圖出來，無需再次計算，只改變圖形形態。 最終效果 主圖節點拖動，縮略圖跟著變化...
閱讀 2674·2021-11-25 09:43
閱讀 2586·2021-11-22 09:34
閱讀 2848·2021-11-12 10:34
閱讀 1439·2021-10-20 13:46
閱讀 2306·2019-08-30 13:21
閱讀 934·2019-08-30 11:21
閱讀 486·2019-08-30 11:20
閱讀 2190·2019-08-29 17:20
