Solved

Graphs

Posted on 2000-04-05
6
387 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 48

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
Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

 

Author Comment

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

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: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering 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

This article describes how to import an Outlook PST file to Office 365 using a third party product to avoid Microsoft's Azure command line tool, saving you time.
Containers like Docker and Rocket are getting more popular every day. In my conversations with customers, they consistently ask what containers are and how they can use them in their environment. If you’re as curious as most people, read on. . .
Exchange organizations may use the Journaling Agent of the Transport Service to archive messages going through Exchange. However, if the Transport Service is integrated with some email content management application (such as an antispam), the admini…

710 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