algorithm - 将网格转换为加权邻接列表

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

你就快到了:

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 并递增它来命名节点的注释:在我看来，这种方法有一些缺点，如下所示:

1. 如果节点名称不是加一的数字序列，则此方法将不起作用。换句话说，它不够通用。
2. 这会降低代码的可读性，因为节点的名称可能会与矩阵的索引混淆。

我建议采用以下方法:

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