6

我如何使用BFS 或 DFS算法设计算法以确定非连通图的连通分量，该算法必须能够表示每个连通分量的顶点集。

这是我的方法：

1) 将所有顶点初始化为未访问。

2）从任意顶点v开始对图进行DFS遍历。如果DFS遍历没有访问所有顶点，则返回false。

3）反转所有弧（或找到图的转置或反转）

4）在反向图中将所有顶点标记为未访问。

5）从相同的顶点v开始对反向图进行DFS遍历（与步骤2相同）。如果 DFS 遍历没有访问所有顶点，则返回 false。否则返回真。

这个想法是，如果每个节点都可以从顶点 v 到达，并且每个节点都可以到达 v，那么图是强连接的。在步骤 2 中，我们检查是否所有顶点都可以从 v 到达。在步骤 4 中，我们检查是否所有顶点都可以到达 v（在反转图中，如果所有顶点都可以从 v 到达，那么所有顶点都可以到达原始图中的 v）。

知道如何改进此解决方案吗？

4

4 回答 4

3

怎么样

  • 让vertices=输入
  • 让results= 空列表
  • 虽然有顶点vertices：
    • 创建一个集合S
    • 选择一个任意未探索的顶点，并将其放入S.
    • 从该顶点运行 BFS/DFS，找到每个顶点后，将其vertices从S.
    • 添加S到results
  • 返回results

完成后，您将获得一个顶点集列表​​，其中每个集合都是通过从某个顶点进行图形搜索（使每个集合中的顶点连接）而制成的。假设一个无向图，这应该可以正常工作（在我的脑海中）。

于 2013-11-01T23:16:11.550 回答
1

这可以在 O(V+E) 的时间复杂度中使用 BFS 或 DFS 轻松完成。

// this is the DFS solution
numCC = 0;
dfs_num.assign(V, UNVISITED); // sets all vertices’ state to UNVISITED
for (int i = 0; i < V; i++) // for each vertex i in [0..V-1]
   if (dfs_num[i] == UNVISITED) // if vertex i is not visited yet
      printf("CC %d:", ++numCC), dfs(i), printf("\n");

上述 3 个连接组件的代码输出将类似于：

// CC 1: 0 1 2 3 4
// CC 2: 5
// CC 3: 6 7 8
于 2016-08-27T05:36:32.853 回答
0

解决此问题的标准方法是从每个节点开始运行 DFS。

首先将所有节点标记为未访问。然后，以任何顺序遍历节点。对于每个节点，如果它尚未标记为在连接的组件中，则从该节点运行 DFS 并将所有可到达的节点标记为在同一个 CC 中。如果节点已被标记，则跳过它。然后，这会一次发现一个 CC 图中的所有 CC。

此外，这是非常有效的。如果有 m 个边和 n 个节点，则第一步的运行时间为 O(n)（将所有节点标记为未访问），第二步的运行时间为 O(m + n)，因为每个节点和边最多被访问两次。因此，总运行时间为 O(m + n)。

希望这可以帮助！

于 2013-11-01T23:42:46.207 回答
0

由于您似乎正在使用有向图，并且您想要找到连接的组件（非强连接），因此您必须首先将您的图转换为无向图。所以对于每个顶点，在相反的方向添加一个临时顶点。然后，您可以使用一个简单的 DFS 从尚未访问的每个顶点开始查找连接的组件。最后，您可以删除临时顶点。

于 2013-11-02T01:16:53.280 回答