0

我试图判断一个图是否是强连接的。为了符合强连接的条件，图应具有以下属性：1）DFS 算法将声明所有节点都可以从起始顶点到达 2）当所有边的方向都反转时（转置图），所有节点都可以从起始顶点到达。

这是我的 DFS 实现：

 public void dfs(String startName) {
        Vertex v = getVertex(startName);
        v.dist = 0;
        dfsVertex(v);
    }

 List<Vertex> wasVisited;
 List<Edge> wasVisitedEdge;

    private void dfsVertex(Vertex v) {

        wasVisited.add(v);

        for(Edge e: v.adj){

            if(!wasVisitedEdge.contains(e)){

                Vertex w = e.dest;

                if(!wasVisited.contains(w)){

                    wasVisitedEdge.add(e);
                    w.prev = v;
                    wasVisited.add(w);
                    w.dist = v.dist + 1;
                    dfsVertex(w);
                }
            }



        }

    }

如何使用上述算法判断每个顶点之间是否存在路径？

感谢您的任何提示。

4

1 回答 1

0

所以你的目标是检查一个图是否是强连接的。这很有帮助，因为你可以简单地假设你被赋予了一个任意节点。您的算法所做的是通过连接边获取与查询节点相邻的每个节点

for(Edge e: v.adj)

检查是否已被搜索

if(!wasVisitedEdge.contains(e)) AND if(!wasVisited.contains(w))

如果尚未搜索，请将其添加到列表中

wasVisitedEdge.add(e); AND wasVisited.add(w);

标记有关如何到达新看到的节点的信息

w.prev = v; AND w.dist = v.dist + 1;

然后使用这些相邻节点搜索“新”节点。

dfsVertex(w);

但是，您的算法中有一个错误。请注意，您调用了：

wasVisited.add()

两次。一次用于“v”，一次用于“w”。这样做的问题是“w”成为下一个查询的“v”，因此在第一次调用原始根（或起始）节点后，您将保留列表中每个其他节点的副本

wasVisited

简单的解决方法是完全删除该行

wasVisited.add(w);

然后代码将正常工作。代码执行后

wasVisited

将包含可以从原始查询的根节点到达的每个节点。从这里您可以简单地检查图表中的每个节点是否存储在列表中。如果考虑到每个节点，则列表是强连接的。否则它不是强连接的。无论图是有向图还是无向图，该算法都应该有效。

于 2013-05-24T06:50:44.843 回答