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

x

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

Commented:
¿What is a "cycle" for you?
0

Commented:
You mean it's round? :-)
Or is it self-repeating?
0

Commented:
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

Author Commented:
Edited text of question.
0

Commented:
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

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

found = false;
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.