sbash10
asked on
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.
¿What is a "cycle" for you?
You mean it's round? :-)
Or is it self-repeating?
Or is it self-repeating?
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?
What type of cycle are we talking about?
Can you give us an example of what you are talking about?
ASKER
Edited text of question.
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;
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;
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.