Solved

# Graphs

Posted on 2000-04-05
382 Views
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
Question by:sbash10

LVL 3

Expert Comment

ID: 2688899
¿What is a "cycle" for you?
0

LVL 1

Expert Comment

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

LVL 47

Expert Comment

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

Author Comment

ID: 2690688
Edited text of question.
0

LVL 47

Expert Comment

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

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

LVL 2

Accepted Solution

yairy earned 5 total points
ID: 2702476
You should scan the graph with
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

### Suggested Solutions

HOW TO: Install and Configure VMware vSphere Hypervisor 6.5 (ESXi 6.5), Step by Step Tutorial with screenshots. From Download, Checking Media, to Completed Installation.
Find out what Office 365 Transport Rules are, how they work and their limitations managing Office 365 signatures.
It is a freely distributed piece of software for such tasks as photo retouching, image composition and image authoring. It works on many operating systems, in many languages.
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…