const grid = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8]
]
在上面的網格中，從左到右遍歷的成本為 10，從上到下的成本為 25。我想在一個無向加權鄰接串列中表示這一點，如下所示：
const weightedAdjList = {
0: {1: 10, 3: 25},
1: {2: 10, 4: 25},
2: {5: 25},
3: {4: 10, 5: 25},
4: {5: 10, 7: 25},
5: {8: 25},
6: {7: 10},
7: {8: 10},
8: {}
}
就我的代碼而言，這是：
const matrixToAdjList = (matrix) => {
const graph = {};
let i = 0;
for (let r = 0; r < matrix.length; r ) {
for (let c = 0; c < matrix[0].length; c ) {
if (!(i in graph)) graph[i] = {}
i
}
}
// populate(graph);
return graph;
};
誰能幫我填充圖中的鄰接關系？
謝謝！
uj5u.com熱心網友回復：
你快到了：
const matrixToAdjList = (matrix) => {
const graph = {};
let i = 0;
for (let r = 0; r < matrix.length; r ) {
for (let c = 0; c < matrix[0].length; c ) {
if (!(i in graph)) graph[i] = {}
if (c < matrix[0].length-1) {
graph[i][matrix[r][c 1]] = 10 // move right
}
if (r < matrix.length-1) {
graph[i][matrix[r 1][c]] = 25 // move down
}
i
}
}
return graph;
};
關于如何使用i和遞增它來命名節點的注釋：這種方法有一些缺點，IMO，如下所示：
- 如果節點名稱不是加一的數字序列，則此方法將行不通。換句話說，它不夠通用。
- 它使代碼的可讀性降低，因為節點的名稱可能與矩陣的索引混淆。
我建議采用以下方法：
const matrixToAdjList = (matrix) => {
const graph = {};
const R, C = matrix.length, matrix[0].length
for (let r = 0; r < R; r ) {
for (let c = 0; c < C; c ) {
const node = matrix[r][c]
// if (!(node in graph)) graph[node] = {} this check is redundant. we visit each node only once. I assume that the node names are unique, otherwise this algo wouldn't work.
graph[node] = {}
if (c < C-1) {
graph[node][matrix[r][c 1]] = 10 // move right
}
if (r < R-1) {
graph[node][matrix[r 1][c]] = 25 // move down
}
}
}
return graph;
};
uj5u.com熱心網友回復：
initGraph (V)
1: for i = 0 to V
2: G.i = {}
addEdge(u, v, w)
1: e = {v:w}
2: insert e in G.u
MatrixToAdjacencyList (M)
1: // max(M) returns the maximum element in M
2: initGraph(max(M))
3:
4: for i = 0 to M.r
5: for j = 0 to M.c
6: if i != M.r-1: addEdge(M[i], M[i 1], 10)
7: if j != M.c-1: addEdge(M[i], M[j 1], 25)
我只提供了演算法。您應該能夠將其轉換為代碼。
下面提供的演算法的命名約定非常簡單。如果您遇到任何問題，請發表評論。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/412202.html
標籤：