Software Design
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
User Name:
Password:
Remember me
Go Back   Dev Shed ForumsProgramming Languages - MoreSoftware Design

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Rate Thread Display Modes
 
Unread Dev Shed Forums Sponsor:
  #1  
Old July 10th, 2003, 11:40 PM
me_no_xpert me_no_xpert is offline
Junior Member
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Jun 2003
Location: India
Posts: 19 me_no_xpert User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: < 1 sec
Reputation Power: 0
cycle detection graph

hi folks,
the "?" is how to detect a cycle in a graph.
Ofcourse there is this time-tested method of using DFS.

I figured a way out by determining the indegree of every vertex in the graph. if there is a cycle , at 1 stage of the algorithm , there will be no vertex of in-degree 0. which wud mean there is a cycle

My question is, is there a better way to detect the cycle?

Reply With Quote
  #2  
Old July 11th, 2003, 06:05 AM
jakuza's Avatar
jakuza jakuza is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Oct 2002
Posts: 65 jakuza User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 46 m 52 sec
Reputation Power: 7
Thumbs up

Your way have O(n) as complexity indicator, it's not so bad!

Reply With Quote
  #3  
Old June 3rd, 2004, 03:19 AM
haddu haddu is offline
Registered User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Jun 2004
Posts: 1 haddu User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: < 1 sec
Reputation Power: 0
I'm not shure this is correct,
consider the graph A->B , B->C, C->B
Then A's indegree is 0,
the cycle is between B and C

Reply With Quote
Reply

Viewing: Dev Shed ForumsProgramming Languages - MoreSoftware Design > cycle detection graph


Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump


Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 





© 2003-2008 by Developer Shed. All rights reserved. DS Cluster 4 hosted by Hostway
Stay green...Green IT