Question

Use Java if possible please:

Write an algorithm using pseudo code to determine if an undirected graph has any cycle. Analyze the complexity of your algorithm. Write an algorithm using pseudo code to determine if an undirected graph is connected or not. Analyze the complexity of your algorithm. (i) (ii)

Answer 1

Please find my answer for Q1.

Please repost others in separate post.

We do a DFS traversal of the given graph. For every visited vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph. If we don’t find such an adjacent for any vertex, we say that there is no cycle. The assumption of this approach is that there are no parallel edges between any two vertices.

Time Complexity: The program does a simple DFS Traversal of graph and graph is represented using adjacency list. So the time complexity is O(V+E)

Java Program:

Please find my answer for Q1.

Please repost others in separate post.

We do a DFS traversal of the given graph. For every visited vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph. If we don’t find such an adjacent for any vertex, we say that there is no cycle. The assumption of this approach is that there are no parallel edges between any two vertices.

Time Complexity: The program does a simple DFS Traversal of graph and graph is represented using adjacency list. So the time complexity is O(V+E)

Java Program:

import java.util.*;

//This class represents a directed graph using adjacency list

//representation

public class Graph

{

   private int V; // No. of vertices

   private LinkedList<Integer> adj[]; // Adjacency List Represntation

   // Constructor

   Graph(int v) {

       V = v;

       adj = new LinkedList[v];

       for(int i=0; i<v; ++i)

           adj[i] = new LinkedList();

   }

   // Function to add an edge into the graph

   void addEdge(int v,int w) {

       adj[v].add(w);

       adj[w].add(v);

   }

   // A recursive function that uses visited[] and parent to detect

   // cycle in subgraph reachable from vertex v.

   Boolean isCyclicUtil(int v, Boolean visited[], int parent)

   {

       // Mark the current node as visited

       visited[v] = true;

       Integer i;

       // Recur for all the vertices adjacent to this vertex

       Iterator<Integer> it = adj[v].iterator();

       while (it.hasNext())

       {

           i = it.next();

           // If an adjacent is not visited, then recur for that

           // adjacent

           if (!visited[i])

           {

               if (isCyclicUtil(i, visited, v))

                   return true;

           }

           // If an adjacent is visited and not parent of current

           // vertex, then there is a cycle.

           else if (i != parent)

               return true;

       }

       return false;

   }

   // Returns true if the graph contains a cycle, else false.

   Boolean isCyclic()

   {

       // Mark all the vertices as not visited and not part of

       // recursion stack

       Boolean visited[] = new Boolean[V];

       for (int i = 0; i < V; i++)

           visited[i] = false;

       // Call the recursive helper function to detect cycle in

       // different DFS trees

       for (int u = 0; u < V; u++)

           if (!visited[u]) // Don't recur for u if already visited

               if (isCyclicUtil(u, visited, -1))

                   return true;

       return false;

   }

   // Driver method to test above methods

   public static void main(String args[])

   {

       // Create a graph given in the above diagram

       Graph g1 = new Graph(5);

       g1.addEdge(1, 0);

       g1.addEdge(0, 2);

       g1.addEdge(2, 0);

       g1.addEdge(0, 3);

       g1.addEdge(3, 4);

       if (g1.isCyclic())

           System.out.println("Graph contains cycle");

       else

           System.out.println("Graph doesn't contains cycle");

       Graph g2 = new Graph(3);

       g2.addEdge(0, 1);

       g2.addEdge(1, 2);

       if (g2.isCyclic())

           System.out.println("Graph contains cycle");

       else

           System.out.println("Graph doesn't contains cycle");

   }

}