3

我已经实现了一个联合查找算法，该算法查找并连接一个无向图，其顶点由整数表示。我想知道是否有人有任何伪代码或关于如何查看组件是否“连接”的想法，即有一条从一个节点到另一个节点的路径。例如，我有以下顶点：

7（源顶点）、9（目的顶点）和8（源顶点）、7（目的顶点）都是连通的。但是，像 3（源顶点）、5（目标顶点）之类的东西不会连接到前一组组件。谁能指导我正确的方向或给我一个如何测试的想法？谢谢！

4

2 回答 2

0

听起来好像您的图形是有向的，在这种情况下 union-find 对连通性并没有真正的帮助（如果我没记错的话，它通常用于确定Kruskal 算法中的最小生成树，但这是针对无向图的）。如果您的图碰巧是无向的，您可以使用Union-Find使用对所有节点的两次遍历来确定所有连接的组件：

  1. 对于每个节点联合该节点与它具有边缘的所有节点。
  2. 对于每个节点，找到代表节点并检查它是否被报告。如果不是，请报告并放入，例如，放入 a std::set<T>（用于T识别代表的类型）。

使用像 DFS 这样的搜索算法实际上可能更容易：

  1. 对于每个节点，检查它是否已经被访问过。
  2. 如果它没有被访问，它是一个新的连接组件的一部分：在节点上启动一个 DFS 并标记由此找到的每个节点（您也可以将遇到的所有节点报告为连接组件的一部分）。

该算法的优点是它也是 O(n)（在每个连接的组件仅由一个节点组成的最坏情况下，另一种算法是 O(n log n)）。两种算法都不能优雅地处理有向图。

于 2012-11-12T01:58:42.277 回答
0

是的，您所做的只是测试两个节点是否具有相同的根。如果在构建图形时使用路径压缩，结果会非常快。

我认为这是因为我正试图将其合并到 Kruskal 算法的实现中。在找到所有连接的组件后，我想对输出进行排序，以表示每个不相交集合中的每个不相交集合。很抱歉打扰您，但如果可能的话，您是否有任何伪代码来解释您的意思？

这些集合已经由一个公共根节点标识。 完成所有 unions后，每个唯一集合将有一个根。因此，您然后运行每个节点并调用Find它。这个怎么样：

typedef std::list< Node* > TNodeList;
typedef std::map< Node*, TNodeList > TSetMap;

TSetMap mysets;

// Assuming you have nodes stored in the list type I declared above...
for( TNodeList::iterator n = nodes.begin(); n != nodes.end(); n++ )
{
    Node *thisnode = *n;
    Node *rootnode = Find(thisnode);

    // Add to list for root.  Using the [] operator on map will create a new
    // list if none exists for that node.
    mysets[rootnode].push_back(thisnode);
}

现在你有了一张包含所有集合作为单独列表的地图，你可以做你喜欢的...

std::cout << "Number of disjoint sets: " << mysets.size() << std::endl;
int count = 0;

for( TSetMap::iterator s = mysets.begin(); s != mysets.end(); s++ )
{
    TNodeList & nl = s->second;
    std::cout << "Set " << ++count << " contains " << nl.size() << " nodes\n";
}

为了使所有这些调用Find高效，您应该在Union函数中实现路径压缩。

于 2012-11-12T01:31:41.170 回答