Solved

Graphs

Posted on 2000-04-05
6
388 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
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 49

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
Ready to get started with anonymous questions?

It's easy! Check out this step-by-step guide for asking an anonymous question on Experts Exchange.

 

Author Comment

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

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

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

With the rising number of cyber attacks in recent years, keeping your personal data safe has become more important than ever. The tips outlined in this article will help you keep your identitfy safe.
This article is written by John Gates, CISSP. Gates, the SNUG President-Elect, currently holds the position of Manager of Information Systems at Lake Park High School in Roselle, Illinois.
NetCrunch network monitor is a highly extensive platform for network monitoring and alert generation. In this video you'll see a live demo of NetCrunch with most notable features explained in a walk-through manner. You'll also get to know the philos…
Add bar graphs to Access queries using Unicode block characters. Graphs appear on every record in the color you want. Give life to numbers. Hopes this gives you ideas on visualizing your data in new ways ~ Create a calculated field in a query: …

627 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