Question

Write a complete Java program which takes vertices and edges of an undirected graph from the input file input.txt (the graph as adjacency matrix) ,(adjacent vertics of every vertex ),(DFS traversal of the graph),(BFS traversal of the graph),(Graph is connected or not connected)

Answer 1

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Arrays;
import java.util.Scanner;

class Operation{
    // declare global variables
    int Graph[][];
    int count,vertex, queue[],visited[];
    int front=0, rear=-1,row,col,m,n;
    //constructor
    Operation(String filename)  throws Exception{
        
        Scanner sc = new Scanner(new BufferedReader(new FileReader(filename)));
        // fetch no of  vertex
        //the first line of text file contains the number vertex
        if(sc.hasNextLine()){
            String[] line = sc.nextLine().trim().split(" ");
            vertex=Integer.parseInt(line[0]);
                        count=vertex;
        }
                
                Graph=new int[vertex][vertex];
                queue=new int[vertex];
                visited=new int[vertex];
        
        while(sc.hasNextLine()) {
                        String[] line = sc.nextLine().trim().split(" ");
                        m = Integer.parseInt(line[0]);
                        n = Integer.parseInt(line[1]);                          
                        Graph[m-1][n-1]=1;
                        Graph[n-1][m-1]=1;
        } 
                
                // print the adjacencymatrix
                System.out.println("\nAdjacency matrix of the graph:");
                for(int i=0;i<this.vertex;i++){
                        for(int j=0;j<this.vertex;j++){
                                System.out.print(Graph[i][j]+" ");
                        }
                        System.out.print("\n");
                }
    }
    
    // find dfs of a graph from given vertex
    // check also ifgraph is  connected or not
    // if DFS from a vertex visits all the vertices
    // thenit is connected
    void DFS(int v){
        int k;
                System.out.print((v+1)+"  ");
       //mark current vertex as visited
        visited[v]=1;
        count--;
        
        //check for each vertex
        for(k=0;k<vertex;k++){
           if(visited[k]==0 && Graph[v][k]==1){
                DFS(k);
                   }
                }
    }
 
        // do traversal using bfs
        void BFS(int v) {
                rear++;
                queue[rear] = v;
                while(front<=rear){
                        v=queue[front];
                        for(int i=0;i<vertex;i++){
                                if(Graph[v][i]==1  && visited[i]==0){
                                        rear++;
                                        queue[rear]=i;
                                        visited[i]=1;
                                }
                        }
                        visited[v]=1;
                        System.out.print("  "+(v+1));
                        front++;
                }
        }
        
        
    
    //reset visited Array
    void reset(){
        for(int i=0; i<visited.length;i++)
            visited[i]=0;
    }
    
}
public class Main{
        public static void main(String[] args) {
                // filename
                String filename="graph.txt";
                Scanner sc=new Scanner(System.in);
                int start;
                //declare object
                Operation obj;
                
                try {
                        obj=new Operation(filename);
                        
                        //  take input of  start vertex for dfs
                        System.out.print("\nEnter the starting  vertex to perform DFS: ");
                        start=sc.nextInt();
                        // call DFS
                        System.out.print("\nDFS from vertex "+start+": ");
                        obj.DFS(start-1);
                        
                        // check if graph is conected or not
                        if(obj.count==0)
                                System.out.print("\n\nGraph is connected.");
                        else
                                System.out.print("\n\nGraph is not connected.");
                        
                        // reset visited array
                        obj.reset();
                        
                        //  take input of  start vertex for bfs
                        System.out.print("\n\nEnter the starting  vertex to perform BFS: ");
                        start=sc.nextInt();
                        // call BFS
                        System.out.print("\nBFS from vertex "+start+": ");
                        obj.BFS(start-1);
                        System.out.print("\n");
                        
                }catch (Exception e){
                        e.printStackTrace();
                }
        }
}

___________________________________________________________________

5
1 2
1 4
2 3
3 5
4 5

___________________________________________________________________

Adjacency matrix of the graph:
0 1 0 1 0
1 0 1 0 0
0 1 0 0 1
1 0 0 0 1
0 0 1 1 0

Enter the starting  vertex to perform DFS: 1

DFS from vertex 1: 1  2  3  5  4

Graph is connected.

Enter the starting  vertex to perform BFS: 1

BFS from vertex 1:   1  2  4  3  5

___________________________________________________________________

Note: If you have queries or confusion regarding this question, please leave a comment. I would be happy to help you.