将二维数组转换为图形

Question

如何将二维数组转换为图形。数组的每个元素都与邻居相连（邻居是上、下、右和左）。

假设 2x2 数组是：

[
  [A, B]
  [C, D]
]

图表将是这样的：

图的邻接矩阵是这样的：

	A	B	C	D
A	0	1	1	0
B	1	0	0	1
C	1	0	0	1
D	0	1	1	0

图的邻接表是这样的：

A -> B,C
B -> A,D
C -> A,D
D -> B,C

为此需要什么算法？

我只是尝试在 JS 中将 2D 数组转换为图形。

我有一个名为 vertex 的类：

class Vertex {
  constructor(value) {
    this.value = value;
    this.neighbors = [];
  }

  /**
   *
   * @param {Vertex} v
   */
  addNeighborsVertex(v) {
    this.neighbors.push(v);
  }
}

例如二维数组：

let arr = [
    ["A","B"],
    ["C","D"]
]

一个可以接受二维数组并转换为图顶点并返回顶点列表的函数。每个顶点包含 arr 值及其邻居。邻居列表也包含顶点的实例。例如，元素“A”的顶点如下所示：

{
    value : "A",
    neighbors : [
        instanceOfVertexB,
        instanceOfVertexC
    ]
}

不允许重复。 “A”和“D”具有相同的邻居，即“B”。在这种情况下，顶点“A”和顶点“D”都拥有顶点“B”的相同实例。

我如何在js中做到这一点？

Answer 1

正如您在评论中所说，您不需要完整的代码，我不会提供完整的代码，而只是提供一种简单方法的想法，如何做到这一点

• 创建一个

  allvertices: Map<string, Vertex>

  来存储所有现有顶点
• 迭代整个输入数组

对于迭代时的每个顶点：

• 从地图中获取当前顶点。

  let v = allvertices.get(vertexname);
  

  如果顶点已包含在地图中，则返回该顶点；如果不包含，则返回

  undefined

  。

• 如果

  v

  是

  undefined

  ，则创建一个

  v = new Vertex(vertexname)

  并将其添加到地图

  allvertices.set(vertexname, v);
  

• 获取当前顶点的所有

  let neighbours = [arr[row-1][col],arr[row+1][col],arr[row][col-1],arr[row][col+1]]

  。您不必关心 JS 中的越界索引。访问数组不存在的索引不会抛出错误，而只是返回

  undefined

对于

neighbours

数组中不是

undefined

的每个邻居：

• 检查它是否已存在于

  allvertices

  地图中。如果没有创建它并将其添加到

  allvertices

  （如上）

• 将其添加到顶点的邻居列表中

  v

  v.addNeighbour(neighbour);
  

这样，您将为输入数组的每个条目创建一个

Vertex

，并且引用将始终转到同一节点，即，按照要求，您不会有重复项...

另一种更简单的方法，不需要额外的映射（但需要输入数组的两次迭代）

• 迭代

  arr

  一次，对于每个顶点，将数组中当前的

  string

  替换为

  Vertex

  类的实例

  arr[row][col] = new Vertex(arr[row][col]);
  

• 再次迭代你的

  arr

  ，并将所有邻居添加到当前顶点

  let neighbours = [arr[row-1][col],arr[row+1][col],arr[row][col-1],arr[row][col+1]]
  for (let n of neighbours) {
    if (n !== undefined) {
      arr[row][col].addNeighbour(n);
    }
  }