BFS с использованием Матрицы Adjecency - PullRequest
Новая
       65

BFS с использованием Матрицы Adjecency

0 голосов
/ 07 марта 2020

Вопрос, чтобы найти путь Bfs, я могу закодировать путь Bfs, если у графа есть вершины, помеченные как 0,1,2,3,4, вот так Но не могу применить матрицу смежности, как чтобы решить BFS для графа, как 5,10,15,20 прикрепленных изображений, что я кодировал

решение 

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

Нажмите здесь для Вопрос для bfs как вершины 0,1,2,3,4 ...

Нажмите здесь, чтобы узнать, как я хочу решить эту проблему для bfs как вершины 5,10,15,20 ...

И я хочу сделать то же самое для графа, как это, не могу получить логи c

Решено путем сопоставления ввода с 0, 1,2,3 .... и поддерживается обратная карта

Нажмите здесь, чтобы посмотреть решение

1 Ответ

0 голосов
/ 07 марта 2020

Если вам известен диапазон чисел, вы можете присвоить номерам 5, 10, 15 и 20 идентификаторы узлов и сохранить индексы узлов в отдельном массиве. Предположим, что именем массива является IndexLookupArray, если вы хотите найти индекс узла с идентификатором x, вы можете найти его в IndexLookupArray [x]. И остальной код должен быть таким же. Если диапазон чисел неизвестен или если он слишком большой, чтобы поместиться в массив, вы можете, например, сохранить индексы на карте ha sh и сделать то же самое.

Вы можете написать что-то вроде это: 

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