将网格转换为加权邻接表

Question

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;
};

谁能帮我填充图中的邻接关系？

谢谢！

Answer 1

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)

我只提供了算法。您应该能够将其转换为代码。

下面提供的算法的命名约定非常简单明了。如果您遇到任何问题，请发表评论。

Answer 2

你快完成了：

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;
};

将网格转换为加权邻接表

Converting a grid into a weighted adjacency list

algorithm

matrix

adjacency-list

undirected-graph

weighted-graph