0

I have to design an algorithm as from BFS or DFS to do the following, given G=(V,E) a directed graph:

Check whether there is at most one simple path from s to any other vertex u in V. This algorithm has to be on O(|V|+|E|).

And from the previous algorithm, I have to design another one O(|V||E|) algorithm to check whether there is at most one simple path between any two vertices u and v.

I hope you can help me! Thanks a lot in advance!

Dominique Fortin
  • 2,212
  • 15
  • 20
Stratford
  • 325
  • 1
  • 2
  • 11

1 Answers1

2

Hint: What if all the edges on the path from s to u are cut edges (bridge)? What if any of them are not cut edge? :)

Note: We can find all the bridges in a graph O(V+E) time

Fallen
  • 4,435
  • 2
  • 26
  • 46
  • Nice solution!I read up on the wiki link, but the linear time algorithm described there, I couldn't get it.Could it maybe describe it in simple terms? – Aravind Jul 07 '13 at 14:54
  • @Aravind: You can look at [here](http://stackoverflow.com/questions/11218746/bridges-in-a-connected-graph) By the way if you like the solution, why not vote it up? :) That's how another one can find the answer interesting :) Thanks! – Fallen Jul 07 '13 at 15:13
  • Thanks @MuhammedHedayet!! This is very useful. With the code you posted before, I can find all the bridges, but, how can I determine whether the path between _s_ to any vertex which is only composed of bridges? – Stratford Jul 07 '13 at 16:20
  • @Stratford: A simple solution can be like the following: first mark all the edges those are bridge. And while finding the bridges you can find the parent for every node. So you can start from **u** to reach **s** following the parent node at every step. While following the path, simply check if the edge from **a** to **b** is a bridge or not, where **a** and **b** are two vertices on the path from **u** to **s** and **b** is parent of **a**. – Fallen Jul 07 '13 at 17:41