0

我得到了以下练习：有一个未加权、有向、弱连接的图，有 n 个节点（n < 1 000 000）。我们想遍历整个图，从最少的节点开始。问题是：我从哪些节点开始遍历？我找不到有关此特定主题的任何内容。但是，我设法想出了一个算法，但效率不够：

  • 我将图形存储在邻接列表中（对于二维矩阵，n 可能太高）
  • 我从每个节点 i 开始一个 BFS，并将它到达的节点存储在x[i][...]( x = List<List<int>>)
  • 我检查是否有x[i].Count == n
  • 我检查是否有(x[i] union x[j]).Count == n
  • 我检查是否有(x[i] union x[j] union x[k]).Count == n ......所以我将所有可能的 2、3、4...... x 子集的并集，并检查它的计数是否为 n。

如果 n 不太高，它可以正常工作，但我需要一个更有效的算法来获得更大的 n。

任何帮助表示赞赏（你会让我能够再次入睡）！:)

4

1 回答 1

0

查找没有任何传入边的节点。循环遍历这些节点，对于每个节点 v，开始遍历图。记住您访问了哪些节点（通过将它们放入哈希表或标记它们）。当您到达您已经访问过的节点时停止遍历。

您将需要一个邻接列表表示，其中每个节点都有一个传入边缘列表和一个传出边列表。然后做这样的事情：

Set nodesToVisit = emptySet;
for i=1 to n:
    if incoming[i].size() == 0:
        nodesToVisit.add(i)

Set visited = emptySet;
for v in nodesToVisit:
    nodesToVisit.remove(v)
    if(v is not in visited):
        visit(v);
        visited.add(v);
        for u in outgoing[v]:
            nodesToVisit.add(u)
于 2013-03-29T00:41:51.210 回答