What I want to achive is when given a directed graph, find out if there is one node that can reach every other node and if there is one node that can be reached by every other. Time complexity should be O(n+m).
I'm into finding all strongly connected parts in the graph and then check the connectivity among those. Can that be an appropriate solution or do I have to rethink it all? Maybe you guys have a better solution.
Or just start a dfs search from every Vertex in your directed Graph (that results in a spanning tree in a undirected Graph). If you can reach evry vertex you have found a Vertex that is connected to every other. for the second case just invert the directions and do it again if you find one then it is reachable from every node
I don't believe that the suggestion to use a spanning tree is appropriate. The spanning tree merely gets you a connected component and that component which is a subgraph of the original graph need not contain the path that you are seeking. (You can construct a counterexample from a graph with 3 nodes and 3 edges)
I believe that you will want to look up and understand is a topological sort. This is a sort that embeds a partial order into a total order - again more terms to look up. You will need to think about what to do with cycles.
I hope that that is enough of a hint to get you started and yet still leaves you with a bit of thinking to do.
Enjoy!
From what I can understand of the problem I think that a spanning tree is ideal.
If, after running your spanning tree algorithm, you end up with a forest of trees (say forest A and
forest B) then you know all vertices in A can reach and be reached from all other vertices in A,
The same holds for B. Therefore if you cannot find a single spanning tree you do not have a
single vertex from which all other nodes can be reached and conversely you also cannot reach
any particular vertex from all other vertices.
(unless the OP is just looking for connections that are only one edge removed from the
specifed vertex)
matfud
> I'm into finding all strongly connected parts in the
> graph and then check the connectivity among those.
> Can that be an appropriate solution or do I have to
> rethink it all? Maybe you guys have a better solution.
I think this sounds like the right approach. You can compute the strongly connected components in O(n+m) which meets your professor's requirement. The rest is easy.
> I believe that you will want to look up and
> understand is a topological sort. This is a sort that
> embeds a partial order into a total order - again
> more terms to look up. You will need to think about
> what to do with cycles.
Am I right that a topological sort gives you something like an activity chain? That doesn't help to determine if you have a vertex that is connected to each other.
> Wouldn't it be possiblity to calculate a spanning
> forest and see if you can connect the tree start
> point with the end points of an other?
You can't just check the endpoints, you need to check the intermediate nodes as well. The OP's problem isn't completely clear, but if we interpolate slightly, it essentially boils down to computing the transitive closure of a graph. This is an O(n^3) problem (well, technically its as hard as matrix mul, which for practical purposes is O(n^3)).
In certain cases however, you can speed this up by using exactly the technique the OP mentioned. Quickly compute the strongly connected components, and if they are quite large you will have a much smaller graph to compute the transitive closure on. Of course, if there are no strongly connected components, it will still be O(n^3).