Solved

Graphs

Posted on 2000-04-05
6
383 Views
Last Modified: 2010-04-16
How do you determine if there is a cycle in a given graph?The graph has nodes and edges so you have to make a program that will determine if a given graph has a cycle in it ,i.e you mark nodes as you pass through them ,if you encounter a node that has already been marked then you have detected a cycle.
0
Comment
Question by:sbash10
6 Comments
 
LVL 3

Expert Comment

by:vikiing
ID: 2688899
¿What is a "cycle" for you?
0
 
LVL 1

Expert Comment

by:nrico
ID: 2689133
You mean it's round? :-)
Or is it self-repeating?
0
 
LVL 48

Expert Comment

by:dbrunton
ID: 2689348
What type of graph are we talking about?

What type of cycle are we talking about?

Can you give us an example of what you are talking about?
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 

Author Comment

by:sbash10
ID: 2690688
Edited text of question.
0
 
LVL 48

Expert Comment

by:dbrunton
ID: 2691068
Walk through the graph creating a linked list as you go, adding each node to the end of the linked list.

As you add each node check to see if it is in the linked list.  If it is you have found a cycle.

rough psuedo-code

head : listptr;
current : listptr;
new : listprt;
newnode : node;
found : boolean;

found = false;
current = head;
while current.next <> nil do         { also must check top of list }
  begin
    if current.node = newnode then
       found = true;    { cycle found }
    current = current.next;
  end;   { end of list found }
if not found { we need to add node to end of list if not cycle }
  begin
     createnewlistptr(new);
     current.next = new;
  end;
0
 
LVL 2

Accepted Solution

by:
yairy earned 5 total points
ID: 2702476
You should scan the graph with
BFS (Breadth First Search) or
DFS (Depth first search).
Every node is signed.

(don't put into the queue(BFS), Stack(DFS) nighbours that where insert before)

If you encounter a nighbour node that
is already signed then its because there is a cycle.

0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

What does UTC stand for?  “Coordinated Universal Time” – Think of this as the true time on Planet Earth that never changes with the exception of minor leap seconds here and there to account for the changes in the planet's rotation.   What does th…
We need a new way to communicate time sensitive or critical info.   The best part of my role at xMatters is visiting our clients all over the world to learn about how they operate their businesses, share insights that xMatters has gleaned across…
This tutorial gives a high-level tour of the interface of Marketo (a marketing automation tool to help businesses track and engage prospective customers and drive them to purchase). You will see the main areas including Marketing Activities, Design …
As a trusted technology advisor to your customers you are likely getting the daily question of, ‘should I put this in the cloud?’ As customer demands for cloud services increases, companies will see a shift from traditional buying patterns to new…

911 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now