BFS 使用邻接矩阵

Question

寻找 Bfs 路径的问题，，如果图形的顶点标记为 0,1,2,3,4,我可以编写 bfs 路径，像这样但是不能应用邻接矩阵如何解决像 5,10,15,20 这样的图形的 bfs 附上我编码的图片

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...

我想对这样的图做同样的事情，无法理解逻辑

通过将输入映射为 0,1,2,3.... 并维护一个 reverseMap

来解决

Click here to view the Solution

Answer 1

如果你知道数字的范围，你可以让数字5、10、15和20作为节点的ID，并将节点的索引存储在一个单独的数组中。假设数组的名称是 IndexLookupArray，如果你想查找 ID 为 x 的节点的索引，你可以在 IndexLookupArray[x] 中找到它。其余的代码应该是一样的。如果数字的范围未知或者它太大而不适合数组，您可以将索引存储在哈希映射中并执行相同的操作。

你可以这样写：

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);
   }
}

BFS 使用邻接矩阵

BFS using Adjecency Matrix

java

algorithm

graph

breadth-first-search