Question

Implement a method to take an adjacency matrix as input and print the breath-first traversal results of the graph starting from a node.

CODE:

______________________________________________________________________________________________

public class A5_Q1{

public static void breathFirst(int [] [] aMatrix, int source) {

// complete the code

}

public static void main (String[] args) {

int [] [] g = {{0,1,1,0}{0,0,1,1}{0,0,0,1}{1,0,0,0}};

breathFirst(g, 1);

}

}

_____________________________________________________________________________________________

Example of input and output:

>java A5_Q1

1->2->3 >0

Answer 1

Code For Above problem:

import java.util.LinkedList;
import java.util.Queue;

public class BreathFirstTraversal {

        public static void main(String[] args) {

                int[][] g = { { 0, 1, 1, 0 }, { 0, 0, 1, 1 }, { 0, 0, 0, 1 }, { 1, 0, 0, 0 } };

                breadthFirst(g, 1);

        }

        // Function to perform breadth first traversal
        static void breadthFirst(int[][] matrix, int source) {

                // boolean array to hold visited nodes
                boolean visited[] = new boolean[matrix.length];

                // Queue to hold the track of nodes
                Queue<Integer> q = new LinkedList<Integer>();
                // add source node to queue
                q.add(source);
                // make source node as visited
                visited[source] = true;

                // do until queue become empty(all nodes are visited)
                while (!q.isEmpty()) {
                        // take the next node from queue
                        source = q.poll();
                        // print that node
                        System.out.print(source + "->");

                        // for all nodes in matrix
                        for (int i = 0; i < matrix.length; i++) {
                                // if any node which is not previously visited and adjacent to current node
                                if (!(visited[i]) && matrix[source][i] == 1) {
                                        // add those nodes to queue
                                        q.add(i);
                                        // make that nodes as visited
                                        visited[i] = true;
                                }
                        }
                }

        }

}

Output Of Above Code:

1->2->3->0->

Image Of Code:

ܢܟ le import java.util.LinkedList; 2 import java.util. Queue; 3 4 public class BreathFirstTraversal { 5 60 public static void main(String[] args) { 7 8 int[][] g = { { 0, 1, 1, o }, { 0, 0, 1, 1 }, { 0, 0, 0, 1 }, { 1, 0, 0, 0 } }; 9 10 breadthFirst (g, 1); 11 12 13 14 // Function to perform breadth first traversal 150 static void breadthFirst(int[][] matrix, int source) { 16 17 // boolean array to hold visited nodes 18 boolean visited[] = new boolean[matrix. length]; 19 20 // Queue to hold the track of nodes 21 Queue<Integer q = new LinkedList<Integer>(); 22 // add source node to queue 23 q.add(source); 24 // make source node as visited 25 visited[source] = true; 26 27 // do until queue become empty(all nodes are visited) 28 while (!q. isEmpty()) { 29 // take the next node from queue 30 source = q.poll(); 31 // print that node 32 System.out.print(source + "->"); 33 34 // for all nodes in matrix 35 for (int i = 0; i < matrix.length; i++) { 36 11 if any node which is not previously visited and adjacent to current node 37 if (!(visited[i]) && matrix[source][i] == 1) { 38 // add those nodes to queue 39 q.add(i); 40 i/ make that nodes as visited 41 visited[i] = true; 42 43 44 45 446 47} 48 } }

Output Image:

1->2->3->->