BFS using Adjecency Matrix

Question

Question to find Bfs path ,, i am able to code bfs path if the graph have vertices marked as 0,1,2,3,4,,like this But can't able to apply adjacency matrix how to solve bfs for graph like 5,10,15,20 attached images what i have coded

solution

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Bfs {
        public static void bfsTraversal(int[][] adjMatrix) {
           Queue<Integer> pendingVertices = new LinkedList<>();
           boolean[] visited = new boolean[adjMatrix.length];
           visited[0] = true;
           pendingVertices.add(0);

           while (!pendingVertices.isEmpty()) {
              int currentVertex = pendingVertices.poll();
              System.out.print(currentVertex + " ");
              for (int i = 0; i < adjMatrix.length; i++) {
                  if (adjMatrix[currentVertex][i] == 1 && !visited[i]) {
                    pendingVertices.add(i);
                    visited[i] = true;
                  }
              }
           }
       }

       public static void main(String[] args) {
       Scanner s = new Scanner(System.in);
       int v = s.nextInt();
       int e = s.nextInt();
       int[][] adjMatrix = new int[v][v];
       for (int i = 0; i < e; i++) {
           int v1 = s.nextInt();
           int v2 = s.nextInt();
           adjMatrix[v1][v2] = 1;
           adjMatrix[v2][v1] = 1;
       }
       bfsTraversal(adjMatrix);
   }
}

Click here for Question for bfs like vertices 0,1,2,3,4...

Click here for ,How i want to solve this for bfs like vertices 5,10,15,20...

And i want to do the same for graph like this ,,can't get logic

Solved by mapping the input with 0,1,2,3.... and maintained a reverseMap

Click here to view the Solution

Answer 1

If you know the range of the numbers, you can let the numbers 5, 10, 15 and 20 be the IDs of the nodes and store the indices of the nodes in a seperate array. Suppose the name of the array is IndexLookupArray, if you want to lookup the index of a node with ID x you can find it in IndexLookupArray[x]. And the rest of the code should be the same. If the range of the numbers is unknown or if it's too big to fit in an array, you can store the indices in a hash map for example and do the same thing.

You can write something like this:

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Bfs {
        public static void bfsTraversal(int[][] adjMatrix) {
           Queue<Integer> pendingVertices = new LinkedList<>();
           boolean[] visited = new boolean[adjMatrix.length];
           visited[0] = true;
           pendingVertices.add(0);

           while (!pendingVertices.isEmpty()) {
              int currentVertex = pendingVertices.poll();
              System.out.print(currentVertex + " ");
              for (int i = 0; i < adjMatrix.length; i++) {
                  if (adjMatrix[currentVertex][i] == 1 && !visited[i]) {
                    pendingVertices.add(i);
                    visited[i] = true;
                  }
              }
           }
       }

       public static void main(String[] args) {
         Scanner s = new Scanner(System.in);

         int idx = 0;
         int range = s.nextInt();
         int v = s.nextInt();
         int e = s.nextInt();

         int[] IndexLookupArray = new int[range + 1]; // range + 1 since IndexLookupArray[range] should be accessible.
         int[][] adjMatrix = new int[v][v];

         Arrays.fill(IndexLookupArray, 0, range + 1, -1);

         for (int i = 0; i < e; i++) {
           int v1 = s.nextInt();
           if (IndexLookupArray[v1] == -1)
           {
             IndexLookupArray[v1] = idx;
             idx++;
           }
           v1 = IndexLookupArray[v1];

           int v2 = s.nextInt();
           if (IndexLookupArray[v2] == -1)
           {
             IndexLookupArray[v2] = idx;
             idx++;
           }
           v2 = IndexLookupArray[v2];

           adjMatrix[v1][v2] = 1;
           adjMatrix[v2][v1] = 1;
       }
       bfsTraversal(adjMatrix);
   }
}