Question

Write the program in JAVA.

Make an undirected, but disconnected graph of at least 15 vertices and 25 edges.

you may add function calls in your main to add edges between vertices - one function call per edge. You may choose any graph representation of your choice from the 3 ways we discussed in the class.

Write a program to do DFS traversal of the graph.

Also write a program to do BFS traversal of the same graph.

Draw your graph on a paper and upload it with you code.

run the each of the two programs and capture screen shots and submit them. Check that the program does indeed do the correct traversal (based on your hand drawn graph)

Answer 1

Let the graph with 15 vertices and 25 edges is as follows:

Java code for BFS travsersal and DFS traversal is as follows:

import java.util.*;
class Main
{
   // testing main method
   public static void main(String args[])
   {
       List<List<Integer>> graph=createGraph();
       bfs_traversal(graph);
       dfs_traversal(graph);
   }
  
   // method that creates the graph
   public static List<List<Integer>> createGraph()
   {
       List<List<Integer>> graph=new ArrayList<List<Integer>>();
       for(int i=0;i<15;i++)
       {
           graph.add(new ArrayList<Integer>());
       }
      
       graph.get(0).add(1);
       graph.get(0).add(2);
       graph.get(0).add(3);
      
       graph.get(1).add(0);
       graph.get(1).add(2);
       graph.get(1).add(3);
       graph.get(1).add(4);
      
       graph.get(2).add(0);
       graph.get(2).add(1);
       graph.get(2).add(3);
      
       graph.get(3).add(0);
       graph.get(3).add(1);
       graph.get(3).add(2);
       graph.get(3).add(4);
      
       graph.get(4).add(2);
       graph.get(4).add(3);
      
       graph.get(5).add(6);
       graph.get(5).add(8);
       graph.get(5).add(9);
      
       graph.get(6).add(5);
       graph.get(6).add(7);
       graph.get(6).add(8);
       graph.get(6).add(9);
       graph.get(6).add(10);
      
       graph.get(7).add(6);
       graph.get(7).add(9);
       graph.get(7).add(10);
      
       graph.get(8).add(5);
       graph.get(8).add(6);
       graph.get(8).add(9);
       graph.get(8).add(11);
      
       graph.get(9).add(5);
       graph.get(9).add(6);
       graph.get(9).add(7);
       graph.get(9).add(8);
       graph.get(9).add(10);
       graph.get(9).add(11);
      
       graph.get(10).add(6);
       graph.get(10).add(7);
       graph.get(10).add(9);
       graph.get(10).add(11);
      
       graph.get(11).add(8);
       graph.get(11).add(9);
       graph.get(11).add(10);
      
       graph.get(12).add(13);
       graph.get(12).add(14);
      
       graph.get(13).add(12);
       graph.get(13).add(14);
      
       graph.get(14).add(12);
       graph.get(14).add(13);
      
       return graph;
   }

   // method that prints the bfs traversal of given graph
   public static void bfs_traversal(List<List<Integer>> graph)
   {
       System.out.print("BFS Traversal: ");
       boolean [] visited=new boolean[graph.size()];
       for(int i=0;i<graph.size();i++)
       {
           if(!visited[i])
           {
               bfs(graph,i,visited);
           }
       }
       System.out.println();
   }
  
   public static void bfs(List<List<Integer>> graph,int index,boolean visited[])
   {
       Queue<Integer> queue=new LinkedList<Integer>();
       queue.add(index);
       visited[index]=true;
      
       while(!queue.isEmpty())
       {
           Integer node=queue.poll();
           System.out.print(node+" ");
           List<Integer> list=graph.get(node);
           for(int value: list)
           {
               if(!visited[value])
               {
                   visited[value]=true;
                   queue.add(value);
               }
           }
       }
   }
  
   // method that prints the dfs traversal of given graph
   public static void dfs_traversal(List<List<Integer>> graph)
   {
       System.out.print("DFS Traversal: ");
       boolean [] visited=new boolean[graph.size()];
       for(int i=0;i<graph.size();i++)
       {
           if(!visited[i])
           {
               dfs(graph,i,visited);
           }
       }
       System.out.println();
   }
  
   public static void dfs(List<List<Integer>> graph,int index,boolean visited[])
   {
       Stack<Integer> stack=new Stack<Integer>();
       stack.add(index);
       visited[index]=true;
      
       while(!stack.isEmpty())
       {
           Integer node=stack.pop();
           System.out.print(node+" ");
           List<Integer> list=graph.get(node);
           for(int value: list)
           {
               if(!visited[value])
               {
                   visited[value]=true;
                   stack.add(value);
               }
           }
       }
   }
}

Sample output

Mention in comments if any mistakes or errors are found. Thank you.