Question

Given an undirected graph G = (V,E), consisting of n vertices and m edges, with each edge labeled from the set {0,1}.

Describe and analyze the worst-case time complexity of an efficient algorithm to find any cycle consisting of edges whose labels alternate 0,1.

Answer 1

Approach: Run a DFS from every unvisited node. Depth First Traversal can be used to detect a cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is joining a node to itself (self-loop) or one of its ancestor in the tree produced by DFS.

To find the back edge to any of its ancestor keep a visited array and if there is a back edge to any visited node then there is a loop and return true.

Algorithm:

Create the graph using the given number of edges and vertices.

Create a recursive function that that current index or vertex, visited and recursion stack.

Mark the current node as visited and also mark the index in recursion stack.

Find all the vertices which are not visited and are adjacent to the current node. Recursively call the function for those vertices, If the recursive function returns true return true.

If the adjacent vertices are already marked in the recursion stack then return true.

Create a wrapper class, that calls the recursive function for all the vertices and if any function returns true, return true.

Else if for all vertices the function returns false return false.

Complexity Analysis:

• Time Complexity: O(n+m).
  The program does a simple DFS Traversal of the graph which is represented using adjacency list. So the time complexity is O(n+m).
• Space Complexity: O(n).
  To store the visited array O(n) space is required.