0

说，我有一个分别包含顶点和边列表的图形对象。G={V,E}

G={[3, 4, 1, 2, 5, 6],[3->4, 1->2, 1->5, 5->4, 5->6]}

假设图表是unweighted and undirected我需要找出是否所有的，Vertices are interconnected with eachother即没有单独的节点或互连的节点是孤立的。

1 -- 2

|

5 -- 4 -- 3

| 

6

它与使用 DFS 或 BFS 遍历图形有关吗？请帮我解决这个问题，谢谢。

4

4 回答 4

1
  1. 以一个verticle为起点
  2. 从那个verticle启动BFS/DFS
  3. 检查是否所有的verticles都被访问过
于 2012-09-10T09:50:30.930 回答
1

是的，可以使用 BFS/DFS 解决问题。您可以在这两个和任何起始节点中选择任何搜索算法，如果通过搜索技术（DFS 或 BFS）您没有到达至少一个节点，则意味着存在一个或多个断开连接的组件以及一些单独的节点或互连节点被隔离。但这并不能告诉您存在多少断开连接的组件，为此您必须使用其他未访问的节点再次开始遍历。

于 2012-09-10T10:45:48.937 回答
0

在 Python 中计算图的连通分量的算法中已经回答了一个类似的问题。

由于您询问图形是否已连接，因此您将以下函数添加到脚本中：

def isGraphConnected(graph):
    return get_connected_components_number(graph)==1
于 2012-09-10T09:52:30.387 回答
0

您也可以使用生成树来实现此结果。在wiki中它被定义为：

In the mathematical field of graph theory, a spanning tree T of a connected, undirected graph G is a tree composed of all the vertices and some (or perhaps all) of the edges of G.

生成树

图片 : 生成树（来源：维基百科）

如果你想找到最小生成树 Prim 的算法可以是一个不错的选择。代码片段示例：

MST-Prim(G,r)
01 for each vertex u element of G.V
02    u.key :=infinity
03    u.parent := NIL
04 r.key := 0
05 init(Q, G.V)   // Q is a priority queue
06 while not isEmpty(Q)
07    u := extractMin(Q)   // add u to T
08    for each v element of u.adj do
09        if v element of Q and w(u,v) < v.key then
10        v.key := w(u,v)
11          modifyKey(Q,v)
12          v.parent := u

更新：

Prim 算法的解释可以在这里找到。

有关最小生成树的更多信息，请参见此处。

于 2012-09-10T09:22:48.123 回答