java - 消除孤立顶点并对结果图的顶点重新排序的有效方法

Question

这个标题有点啰嗦，但是就到这里吧。我面临着从输入流中读取一堆无向边和多个顶点并输出一组边的问题。我输出的边集不能有任何“空白”——我的意思是我不能有 (1,2)、(2, 4) 和 (4, 5) 的边集作为顶点#3 永远不会在顶点集中被提及。

不允许使用此图，因为 2 将是“空白”

此图是允许的，因为连接图中没有“空白”。有 4 个顶点，它们从 1 到 4 编号。 该图的输出将是 [[1, 3][3, 4][4, 2][2, 1]]

到目前为止，我是如何解决这个问题的:

当我知道有多少个顶点时，我将它们的所有索引添加到包含所有孤立顶点的 HashSet 中。当我从输入流中读取边时，我从 HashSet 中删除了每条边的两个顶点。之后，我将它们添加到维度为 (|V|, 2) 的二维数组中。如果在我接收所有边之后有任何孤立的顶点，我会调用我的“重新排序方法”。

它的作用如下;

• 将二维矩阵和孤立顶点集作为输入
• 调用我的帮助方法 findMatrixProperties()，它通过嵌套循环一次遍历整个矩阵一个元素来找到矩阵的最大值以及不同顶点的数量。
• 然后我使用 (while matrixMax > nrOfVertices) 进入我的 while 循环
• 在我的 while 循环中，我遍历整个矩阵，将所有最大值替换为具有孤立顶点的 HashSet 的最小值。
• 完成矩阵的完整迭代后，我删除了孤立顶点集中的最小值并再次调用 findMatrixProperties()。

这是伪造的(程序本身是用 Java 编写的)

reorderMethod(matrix M, isolated vertex set I) 
  matrixProperties = findMatrixProperties(M) // matrixProperties is an instance of a helper class MatrixProperty which holds two integers, max and nrOfVertices
  while (max > nrOfVertices) 
    for row in M
      for col in M 
        if M[col, row] = max:
          M[col, row] = min(I)
    // Remove min(I) from I 
    matrixProperties = findMatrixProperties(M)

有什么方法可以提高效率吗？

Answer 1

如果我对你的问题的理解正确，你想找到一个图的顶点的规范重新编号，使得没有完全未连接的节点具有比连接节点更小的标签。

简单的答案是用标签较小的相连顶点的数量来标记每个顶点。 (这将从 0 而不是 1 开始对顶点进行编号，但您可以很容易地向每个标签添加一个。)

您似乎使用的是 boolean NxN 数组而不是邻接列表，所以这就是我编写以下伪代码的方式。不过，邻接表的更改微不足道。

我们首先要通过对每一行应用 or 运算符将 boolean 数组简化为 boolean vector 。一个节点连接到某个东西，除非它的整行都是假的，所以 boolean vector 足以告诉我们一个节点是否连接。显然，我们可以在扫描一行时遇到第一个 true 值时停止。然后我们将 boolean vector 重新解释为 0 和 1 的整数 vector ，并对 vector 做一些非常类似于累积和的事情，这样 vector 将包含每个条目的具有较小标签的连通分量的数量，这意味着如果忽略未连接的顶点，则生成的 vector 恰好是从旧标签到规范标签的转换。 (可以为所有顶点构造平移；下面的伪代码将通过从最后一个标签向下重新编号未连接的顶点来实现这一点。)

我使用了类似 python 的伪代码，因为 Java 对我来说不够伪:)

# M is an adjacency matrix; we assume that it is square.
# The function returns the translation vector
def renumber(M):
  ones = 0
  zeros = len(M) - 1
  trans = []
  for row in M:
    if any(row):
      # the edge is connected
      trans.append(ones)
      ones += 1
    else:
      # the edge is unconnected
      zeros -= 1
      trans.append(zeros)
  return trans