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

Question

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

不允许使用此图，因为 2 将是 "blank"

此图是允许的，因为连接图中没有 "blanks"。有 4 个顶点，编号从 1 到 4。 此图的输出将是 [[1, 3][3, 4][4, 2][2, 1]]

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

当我知道有多少个顶点时，我将它们的所有索引添加到包含所有孤立顶点的 HashSet 中。当我从输入流中读取边时，我从 HashSet 中删除了每条边的两个顶点。之后，我将它们添加到维度为 (|V|, 2) 的二维数组中。如果在我获取所有边之后有任何孤立的顶点，我调用我的 "reorder-method"。

它的作用如下;

将二维矩阵和孤立顶点集作为输入
调用我的 help-method findMatrixProperties()，它通过嵌套循环一次遍历整个矩阵一个元素来找到矩阵的最大值以及不同顶点的数量。
然后我进入我的 while 循环 (while matrixMax > nrOfVertices)
在我的 while 循环中，我遍历整个矩阵，将所有 max-values 替换为具有孤立顶点的 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 开始对顶点进行编号，但您可以很容易地向每个标签添加一个。）

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

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

我使用了类似 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

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

Efficient way to eliminate isolated vertices and reorder the vertices of resulting graph

java

algorithm

graph-theory

multidimensional-array