Graphs

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.
sbash10Asked:
Who is Participating?

Improve company productivity with a Business Account.Sign Up

x
 
yairyConnect With a Mentor Commented:
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
 
vikiingCommented:
¿What is a "cycle" for you?
0
 
nricoCommented:
You mean it's round? :-)
Or is it self-repeating?
0
Get your problem seen by more experts

Be seen. Boost your question’s priority for more expert views and faster solutions

 
dbruntonCommented:
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
 
sbash10Author Commented:
Edited text of question.
0
 
dbruntonCommented:
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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.