vertex or set of vertices reachable from all other vertices in a directed graph

 

Given a directed graph how to find vertex(call it "special vertex") that can be reached from all other vertices? It is not necessary that other vertices have to be reachable from this special vertex.

I would assume the graph is acyclic (ie a DAG)

  • 1) do topological ordering over the graph 2) check the indegree of the last vertex. If it equals n-1 then it is a special vertex. Of course here topological ordering without transitive closure is useless.

  • One can argue that a vertex is special vertex if it is a leaf in the DAG.

  • Reverse the arcs of the directed graph and run DFS on any vertex, If all other vertices are reachable, then this is a special vertex for the original graph.

    • 链接地址: http://www.djcxy.com/p/70686.html

    上一篇: 有没有一种简单的方法来按值删除列表元素？

    下一篇: 顶点或从有向图中所有其他顶点可到达的顶点集