Re: [algogeeks] Re: Cycle in Undirected and Directed Graphs

[Anand]

Back edges are the key to finding a cycle in an undirected graph.
Condition for Back edge is vertex(u,v):v that we are trying to explore from
(u) should not be the parent of u.
http://codepad.org/t7Y5wshb


On Tue, Jun 15, 2010 at 5:25 AM, Rohit Saraf wrote:

> @vivek : was that a joke?
>
> --
> Rohit Saraf
> Second Year Undergraduate,
> Dept. of Computer Science and Engineering
> IIT Bombay
> http://www.cse.iitb.ac.in/~rohitfeb14
>
>
> On Mon, Jun 14, 2010 at 11:40 AM, souravsain  wrote:
>
>> @sharad: Do you have some article that explains cycle detection in
>> bfs? Will be of help if you can share that or book or so which
>> explains cycle detection via bfs.
>>
>> @amit: Both in directed and undirected graphs you can find a cycle in
>> O(|v|) time using a dfs. See "Algorithm Design Manual" Second Edition,
>> chapter 5 by Stiev. S. Skiena. Its a very good explanation.
>>
>> On Jun 14, 6:19 am, Rohit Saraf  wrote:
>> > In any directed graph just check if dfs has a back edge. For
>> > undirected, check if there is a nontree edge
>> >
>> > --
>> > --
>> > Rohit Saraf
>> > Second Year Undergraduate,
>> > Dept. of Computer Science and Engineering
>> > IIT 
>> > Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Cycle in Undirected and Directed Graphs

[Rohit Saraf]

@vivek : was that a joke?
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14


On Mon, Jun 14, 2010 at 11:40 AM, souravsain  wrote:

> @sharad: Do you have some article that explains cycle detection in
> bfs? Will be of help if you can share that or book or so which
> explains cycle detection via bfs.
>
> @amit: Both in directed and undirected graphs you can find a cycle in
> O(|v|) time using a dfs. See "Algorithm Design Manual" Second Edition,
> chapter 5 by Stiev. S. Skiena. Its a very good explanation.
>
> On Jun 14, 6:19 am, Rohit Saraf  wrote:
> > In any directed graph just check if dfs has a back edge. For
> > undirected, check if there is a nontree edge
> >
> > --
> > --
> > Rohit Saraf
> > Second Year Undergraduate,
> > Dept. of Computer Science and Engineering
> > IIT Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Cycle in Undirected and Directed Graphs

[souravsain]

@sharad: Do you have some article that explains cycle detection in
bfs? Will be of help if you can share that or book or so which
explains cycle detection via bfs.

@amit: Both in directed and undirected graphs you can find a cycle in
O(|v|) time using a dfs. See "Algorithm Design Manual" Second Edition,
chapter 5 by Stiev. S. Skiena. Its a very good explanation.

On Jun 14, 6:19 am, Rohit Saraf  wrote:
> In any directed graph just check if dfs has a back edge. For
> undirected, check if there is a nontree edge
>
> --
> --
> Rohit Saraf
> Second Year Undergraduate,
> Dept. of Computer Science and Engineering
> IIT Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.