首页 文章

如何使用递归深度优先搜索算法判断所有顶点之间是否存在路径？

提问于
浏览 次
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);
                }
            }



        }

    }

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

谢谢你的任何提示 .

graph depth-first-search

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

    将包含可从原始查询根节点到达的每个节点 . 从这里，您只需检查图表中的每个节点是否都存储在列表中 . 如果考虑每个节点，则列表强烈连接 . 否则它没有强烈连接 . 无论图形是指向还是未指向，该算法也应该起作用 .

    回复于

相关问题