Question

JAVA

LAB 1 2 5 7 6 9 3 8 . Write code to implement an adjacency matrix (2d matrix) which represents the graph. Your code should contain a function called addEdgelint i, int j). Use this function to add the appropriate edges in your matrix. Write code to implement Depth-First-Search (DFS) and Breadth-First-Search (BFS) of your graph. Let 0 be the source Node . Traverse the graph using DFS, print the Nodes as they are visited. . Traverse the graph using BFS, print the Nodes as they are visited.

Answer 1

// Java program to represent a graph as adjacency matrix and traverse the graph using DFS and BFS using start node as 0

import java.util.LinkedList;

public class Graph {

      

       private int n;

       private int graph[][];

      

       // constructor

       public Graph(int n)

       {

             this.n = n;

             graph = new int[n][];

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

                    graph[i] = new int[n];

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

                    for(int j=0;j<n;j++)

                           graph[i][j] = 0;

       }

      

       // method to add an edge from ith node to jth node

       public void addEgde(int i, int j)

       {

             graph[i][j] =1;

       }

      

       // method to display the adjacency matrix

       public void display()

       {

             for(int i=0;i<graph.length;i++)

             {

                    for(int j=0;j<graph[i].length;j++)

                           System.out.print(graph[i][j]+" ");

                    System.out.println();

             }

       }

      

       // method to traverse the graph using DFS from starting from the vertex

       public void DFS(int vertex)

       {

             boolean visited[] = new boolean[n];

             DFS(vertex,visited);

       }

      

       //helper method to implement DFS traversal

       private void DFS(int src,boolean visited[])

       {

             visited[src]=true;

             System.out.print(src+" ");

             for(int i=0;i<graph[src].length;i++)

             {

                    if((graph[src][i] == 1) && (!visited[i]))

                           DFS(i,visited);

             }

       }

      

       // method to traverse the graph using BFS from starting from the vertex

       public void BFS(int vertex)

       {

             boolean visited[] = new boolean[n];

             LinkedList<Integer> queue = new LinkedList<Integer>();

             visited[vertex]=true;

             queue.addLast(vertex);

            

             while(!queue.isEmpty())

             {

                    int node = queue.poll();

                    System.out.print(node+" ");

                   

                    for(int i=0;i<graph[node].length;i++)

                    {

                           if((graph[node][i] == 1) && (!visited[i]))

                           {

                                 visited[i] = true;

                                 queue.addLast(i);

                           }

                    }

             }

       }

       public static void main(String[] args) {

            

            

             Graph g = new Graph(10); // create the graph object

             // add edges to graph

             g.addEgde(0, 1);

             g.addEgde(1, 0);

             g.addEgde(0, 6);

             g.addEgde(6, 0);

             g.addEgde(1, 4);

             g.addEgde(4, 1);

             g.addEgde(1, 7);

             g.addEgde(7, 1);

             g.addEgde(2, 5);

             g.addEgde(5, 2);

             g.addEgde(3, 7);

             g.addEgde(7, 3);

             g.addEgde(5, 9);

             g.addEgde(9, 5);

             g.addEgde(6, 7);

             g.addEgde(7, 6);

             g.addEgde(7, 9);

             g.addEgde(9, 7);

             g.addEgde(7, 8);

             g.addEgde(8, 7);

             // print the adjacency matrix

             System.out.println("Adjacency matrix : ");

             g.display();

             // dfs traversal from vertex 0

             System.out.println("\nDFS from vertex 0: ");

             g.DFS(0);

             // bfs traversal from vertex 0

             System.out.println("\nBFS from vertex 0 : ");

             g.BFS(0);

       }

}

//end of program

Output:

Adjacency matrix: 0 1 0 0 0 0 1 0 0 0 10 00 10 0 1 0 0 0 0 0 0 0 10 0 0 0 0 0 00 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0010000 0 0 1 1 0 00 0 0 0 1 0 0 0101 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 000 00 10 10 0 DFS from vertex 0: 0 1 47 3 6 8 9 5 2 BFS from vertex 0: 0164 7 3 89 5 2