0

I know that this question has been asked some times. But I just can't understand yet and those questions are too old to reply...

I Read about Kahn's Algorithm
Also about DFS
Plus Tarjan's strongly connected components algorithm
But i Just can't understand the process to make it work.
All I've done so far is to initialized and feed the graph.
And found the shortest path from vertéx A to B.

Community
  • 1
  • 1
PlayHardGoPro
  • 2,791
  • 10
  • 51
  • 90

1 Answers1

1

A simple DFS with a little modification will do.

Hint: We do a DFS traversal of the given graph. For every visited vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph.

Also Note: cycles detection in undirected graphs follow algorithm which is totally different from the directed graphs. Cycle in directed graphs are diffent.

(hope you are comfortable with DFS).

Raman
  • 2,735
  • 1
  • 26
  • 46
  • Actually no. Could you give me a short help about it, please ? I'm reading everything I can find but maybe just the main idea. I'm studying it by my own so its not that easy for me. – PlayHardGoPro Jul 01 '15 at 20:32
  • Are you comfortable with DFS in graphs? – Raman Jul 01 '15 at 20:34
  • Unfortunately I'm not comfortable with DFS yet.. Couldnt find anyone to give me a hands up with it. That's why I decided to ask here. Could you give me some help, just with the basic maybe. Like, DO I have to use stack/queue ? Do I use a matrix ? Thanks – PlayHardGoPro Jul 01 '15 at 20:40
  • 1
    No, just a recursive call. Why not read a book or search google? You could also watch tutorial videos on youtube for further clarification. I often do that. – Raman Jul 01 '15 at 20:44
  • +1 I'm already doing it. If I don't use any of this. How do I mark a vertex as parent of other(s) vertex ? How do I mark it as visited ? – PlayHardGoPro Jul 01 '15 at 20:57
  • Why is it totally different for directed graphs? Surely it's exactly the same, except your DFS only follows outgoing edges. – Oliver Charlesworth Jul 01 '15 at 21:07
  • @Oliver Charlesworth: AFAIK ,undirected graphs are nothing but directed graphs with backedges. However that back edge could not be counted as a cycle. Hence the algorithms are different. Correct me If I am wrong. – Raman Jul 01 '15 at 21:13
  • @oliver-charlesworth: Moreover A single DFS on directed graph doesn't guarantee the complete graph traversal (even if it is connected). – Raman Jul 01 '15 at 21:22
  • How do I mark a vertex as parent of other(s) vertex ? How do I mark it as visited, vector ? – PlayHardGoPro Jul 01 '15 at 21:28
  • @ARBY: Agreed on traversability, for that you're going to need to know the source nodes (but as you point out, you're going to need to have something like this anyway for the general disjoint case). However, in terms of the DFS, I believe it's just a case of deciding which edges to follow at any given node. – Oliver Charlesworth Jul 01 '15 at 22:24