Unauthorized Cycles

Question

For an undirected graph G = (V, E) with n vertices (| V | = n), how do you find if it contains a cycle in O (n)?

Answer 1

I think the depth of the first search solves it. If an unexplored edge leads to a previously visited node, then the graph contains a loop. This condition also makes it O (n), since you can examine a maximum of n edges without setting it to true or without unknown edges.

Answer 2

In fact, searching for depth at first (or even wide) is not enough. You need a more spectacular more complex algorithm.

For example, suppose that there exists a graph with nodes {a, b, c, d} and edges {(a, b), (b, c), (b, d), (d, c)}, where an edge ( x, y) is an edge from x to y. (looks something like this, with all edges pointing down).

(a) | | (b) / \ (d) | | | \ / (c) 

Then, doing the depth of the first search, you can visit node a, then b, then c, then go back to c, then visit d, and finally visit c again and end the loop when that doesn't happen. A similar thing happens with the first.

What you need to do is keep track of which sites you are visiting in the middle. In the above example, when the algorithm reaches (d), it completed a visit to (c), but not (a) or (b). So revising the finished node is fine, but visiting the unfinished node means you have a loop. The usual way to do this is to color each node white (not yet visited), gray (visiting descendants) or black (completing the visit).

here is some kind of pseudo code!

 define visit(node n): if n.colour == grey: //if we're still visiting this node or its descendants throw exception("Cycle found") n.colour = grey //to indicate this node is being visited for node child in n.children(): if child.colour == white: //if the child is unexplored visit(child) n.colour = black //to show we're done visiting this node return 

then starting a visit (root_node) will throw an exception if and only if there is a loop (initially all nodes should be white).

Sorry, if you already know all this, it is possible that you meant the depth of the first search anyway, but I hope this helps.

Answer 3

A connected, undirected graph G without cycles is a tree! Any tree has exactly n - 1 edges, so we can just cross the list of edges of the graph and count the edges. If we count n - 1 edges, we will return yes, but if we reach the nth edge, we will return no. This takes O (n) time, because we are looking at no more than n edges.

But if the graph is not connected, we will need to use DFS. We can go around the edges, and if any unexplored edges lead to the visited peak, then it has a loop.

Answer 4

You can solve this problem with DFS. Difficulty of time: O (n)

The essence of the algorithm is that if the connected component / graph does NOT contain a CYCLE, it will always be TREE. See here for proof.

Assume that the graph does not have a cycle, i.e. is a tree. And if we look at the tree, each edge from node:

1. Either reaches his only parent, who is one level taller than him.

2.or reaches his children who are on the same level below.

So, if a node has any other edge that does not belong to the two described above, it will obviously associate the node with one of its ancestors different from its parent. This will form a cycle.

Now that the facts are clear, all you have to do is start DFS for the graph (given that your graph is connected, otherwise it is done for all invisible vertices) and IF you find a neighbor from the node that VISITED, not his parent, then my friend on the graph has a CYCLE, and you SHOULD.

You can track the parent by simply passing the parent parameter as a parameter when you do DFS for your neighbors. And since you only need to study the n edges, the time complexity will be O (n).

Hope the answer helped.

Answer 5

By the way, if you know that this is connected, then it’s just this tree (thus, there are no cycles) if and only if |E|=|V|-1 . Of course, this is not a small amount of information :)

Answer 6

Answer: in fact, the first search in width (or depth search at first does not matter). Details are in the analysis.

Now, how fast is the algorithm?

First, imagine that the graph has no cycles. The number of edges is then equal to O (V), the graph is the forest, the goal is achieved.

Now imagine that the graph has cycles, and your search algorithm completes and reports success in the first one. The graph is not oriented, and therefore, when the algorithm checks the edge, there are only two possibilities: either he visited the other end of the edge, or he has, and then, this edge closes the circle. And as soon as he sees another vertex of the edge, this vertex is "checked", therefore there are only O (V) of these operations. The second case will be achieved only once throughout the algorithm.

Answer 7

I believe that the assumption that the graph is connected may be few in number. so you can use the proof shown above that the runtime is O (| V |). if not, then | E | > | V |. Reminder: DFS O run time (| V | + | E |) .

Answer 8

Here is the code I wrote in C based on DFS to find out if a given graph is / cyclic or not. with some output at the end. Hope this will be helpful :)

 #include<stdio.h> #include<stdlib.h> /****Global Variables****/ int A[20][20],visited[20],v=0,count=0,n; int seq[20],s=0,connected=1,acyclic=1; /****DFS Function Declaration****/ void DFS(); /****DFSearch Function Declaration****/ void DFSearch(int cur); /****Main Function****/ int main() { int i,j; printf("\nEnter no of Vertices: "); scanf("%d",&n); printf("\nEnter the Adjacency Matrix(1/0):\n"); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&A[i][j]); printf("\nThe Depth First Search Traversal:\n"); DFS(); for(i=1;i<=n;i++) printf("%c,%d\t",'a'+seq[i]-1,i); if(connected && acyclic) printf("\n\nIt is a Connected, Acyclic Graph!"); if(!connected && acyclic) printf("\n\nIt is a Not-Connected, Acyclic Graph!"); if(connected && !acyclic) printf("\n\nGraph is a Connected, Cyclic Graph!"); if(!connected && !acyclic) printf("\n\nIt is a Not-Connected, Cyclic Graph!"); printf("\n\n"); return 0; } /****DFS Function Definition****/ void DFS() { int i; for(i=1;i<=n;i++) if(!visited[i]) { if(i>1) connected=0; DFSearch(i); } } /****DFSearch Function Definition****/ void DFSearch(int cur) { int i,j; visited[cur]=++count; seq[count]=cur; for(i=1;i<count-1;i++) if(A[cur][seq[i]]) acyclic=0; for(i=1;i<=n;i++) if(A[cur][i] && !visited[i]) DFSearch(i); } 

---

/ * Output result:

 majid@majid-K53SC:~/Desktop$ gcc BFS.c majid@majid-K53SC:~/Desktop$ ./a.out ************************************ Enter no of Vertices: 10 Enter the Adjacency Matrix(1/0): 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 The Depdth First Search Traversal: a,1 c,2 d,3 f,4 b,5 e,6 g,7 h,8 i,9 j,10 It is a Not-Connected, Cyclic Graph! majid@majid-K53SC:~/Desktop$ ./a.out ************************************ Enter no of Vertices: 4 Enter the Adjacency Matrix(1/0): 0 0 1 1 0 0 1 0 1 1 0 0 0 0 0 1 The Depth First Search Traversal: a,1 c,2 b,3 d,4 It is a Connected, Acyclic Graph! majid@majid-K53SC:~/Desktop$ ./a.out ************************************ Enter no of Vertices: 5 Enter the Adjacency Matrix(1/0): 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 The Depth First Search Traversal: a,1 d,2 b,3 c,4 e,5 It is a Not-Connected, Acyclic Graph! */ 

Answer 9

Simple DFS does the job of checking whether a given undirected graph has a loop or not.

Here the C ++ code is the same.

The idea used in the above code is :

If a node that has already been discovered / visited is found again and not the parent node, then we have a loop.

This can also be explained as shown below (mentioned by @ Rafał Dowgird

If an unexplored edge leads to a previously visited node, then the graph contains a loop.

Answer 10

An undirected graph is acyclic (i.e., forest) if there are no back edges in DFS. Since the trailing edges are those edges ( u , v ) connecting the vertex u with the ancestor v in the depth tree, therefore, no trailing edges mean that there are only edges of the tree, therefore there is no cycle. Therefore, we can just mix DFS. If you find the trailing edge, there is a cycle. The complexity is O(V ) instead of O(E + V ) . Since, if there is a trailing edge, he must before |V | different edges. This is because in the acyclic (non-oriented) forest |E| ≤ |V | + 1 |E| ≤ |V | + 1 |E| ≤ |V | + 1 .

Answer 11

As others have said ... A deep first search will help solve this problem. In general depth, the first search takes O (V + E), but in this case you know that a graph has at most O (V) edges. That way, you can just start DFS, and as soon as you see that the new front increases the counter. When the counter reaches V, you do not need to continue, because the graph has a certain cycle. Obviously, this takes O (v).

Answer 12

I believe that using DFS correctly also depends on how you are going to represent your graph in the code. For example, suppose you use adjacent lists to track neighboring nodes, and your graph has 2 vertices and only one edge: V = {1,2} and E = {(1,2)}. In this case, starting from vertex 1, DFS will mark it as a VISITOR and will put 2 in the queue. After that, it will be pop-top 2, and since 1 is adjacent to 2, and 1 is VISITED, DFS will conclude that there is a loop (which is incorrect). In other words, in Undirected graphs (1,2) and (2,1) there is one and the same edge, and you should code in such a way that DFS does not take into account their different edges. Saving the parent node for each node visited will help deal with this situation.

Answer 13

Recently, I began to study graphics. I wrote a piece of code in java that could determine if a graph has loops. I used DFT to search for cycles in the chart. Instead of recurssion, I used the stack to move the chart.

At a high level, DFT using the stack is performed in the following steps

• Visit Node
• If the node is not in the visit list, add it to the list and push it to the top of the stack
• Mark the node at the top of the stack as the current node.
• Repeat the above for each adjacent node of the current Node
• If all nodes have been visited, pull the current node from the stack

I performed the DFT from each node of the Graph and during the traversal, if I came across a vertex that I visited earlier, I checked if the vertex had a stack depth greater than one. I also checked if node had an edge for itself and if there were several edges between nodes. The stack version that I originally wrote was not very elegant. I read the pseudo code on how to do this using recursion, and that was neat. Here is the Java implementation. The LinkedList array is a graph. with each node and adjacent vertices indicated by the index of the array, and each element, respectively

 class GFG { Boolean isCyclic(int V, LinkedList<Integer>[] alist) { List<Integer> visited = new ArrayList<Integer>(); for (int i = 0; i < V; i++) { if (!visited.contains(i)) { if (isCyclic(i, alist, visited, -1)) return true; } } return false; } Boolean isCyclic(int vertex, LinkedList<Integer>[] alist, List<Integer> visited, int parent) { visited.add(vertex); for (Iterator<Integer> iterator = alist[vertex].iterator(); iterator.hasNext();) { int element = iterator.next(); if (!visited.contains(element)) { if (isCyclic(element, alist, visited, vertex)) return true; } else if (element != parent) return true; } return false; } 

}

Answer 14

You can use the advanced graphics library and circular dependencies . It has a loop search solution with back_edge function.

Answer 15

An undirected graph without a loop has | E | <| V |. -one

 public boolean hasCycle(Graph g) { int totalEdges = 0; for(Vertex v : g.getVertices()) { totalEdges += v.getNeighbors().size(); } return totalEdges/2 > g.getVertices().size - 1; }