Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Graphs

Posted on 2000-04-05
6
Medium Priority
?
389 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
On Demand Webinar: Networking for the Cloud Era

Did you know SD-WANs can improve network connectivity? Check out this webinar to learn how an SD-WAN simplified, one-click tool can help you migrate and manage data in the cloud.

 

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 10 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

New feature and membership benefit!

New feature! Upgrade and increase expert visibility of your issues with Priority Questions.

Question has a verified solution.

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

When trying to connect from SSMS v17.x to a SQL Server Integration Services 2016 instance or previous version, you get the error “Connecting to the Integration Services service on the computer failed with the following error: 'The specified service …
Are you an Exchange administrator employed with an organization? And, have you encountered a corrupt Exchange database due to which you are not able to open its EDB file. This article will explain all the steps to repair corrupt Exchange database.
In this brief tutorial Pawel from AdRem Software explains how you can quickly find out which services are running on your network, or what are the IP addresses of servers responsible for each service. Software used is freeware NetCrunch Tools (https…
In response to a need for security and privacy, and to continue fostering an environment members can turn to for support, solutions, and education, Experts Exchange has created anonymous question capabilities. This new feature is available to our Pr…

722 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