Первый обход в ширину с использованием матрицы adj

ProgramBox

Первый обход в ширину с использованием матрицы adj

Post author:admin
Запись опубликована:9 мая, 2023
Post category:Вопросы по программированию

#java #breadth-first-search

#java #поиск по ширине в первую очередь

Вопрос:

Я пишу рекурсивный обход по ширине, глубине и глубине сначала для следующего графика:

введите описание изображения здесь

Насколько я понимаю, обход должен быть 0 1 3 6 4 5 2 … но я получаю это только для обхода в глубину, а для dfs (рекурсивный) и BFS я получаю 0 1 3 6 2 4 5. Я не знаю, какой из них правильный и что мне нужно сделать, чтобы исправить проблему.

Класс

     public void depthFirst(int vFirst,int n, int[] isvisited)
   {       //vFirst = 0, n = 6
  int v,i;
  // st is a stack
  st.push(vFirst);

  while(!st.isEmpty())
  {
      v = st.pop();
      if(isvisited[v]==0)
      {
          System.out.print(v);
          isvisited[v]=1;
      }
      for ( i = 0; i <= n; i  )
      {
          if((adjMatrix[v][i] == 1) amp;amp; (isvisited[i] == 0))
          {
              st.push(v);
              isvisited[i]=1;
              System.out.print(" "   i);
              v = i;
          }
      }
  }

}

 public void depthFirstRecursive(int w) {
    int j;     //w = 0;

    visited[w] = 1;
    if (w == 0) {
        System.out.print(w   " ");
    }

    for (j = 0; j <= 6; j  ) {
        if ((adjMatrix[w][j] == 1) amp;amp; (visited[j] == 0)) {
            System.out.print(j   " ");

            depthFirstRecursive(j);
        } 

    } 
}

public void breadthFirst(int first, int p) {
    int e;     // first = 0; p = 6
    int[] nodeVisited = new int[7];
    que.add(first);


   while (!que.isEmpty()) {
       e = que.remove();
       if(nodeVisited[e]==0)
          {
              System.out.print(e);
              nodeVisited[e]=1;
          }
       for (int i = 0; i <= p; i  )
          { 

              if((adjMatrix[e][i] == 1) amp;amp; (nodeVisited[i] == 0))
              {
                  que.add(e);
                  nodeVisited[i]=1;
                  System.out.print(" "   i);
                  e = i;
              } 
          }

   }



}


public static void main(String[] args) {



                        // 1  2  3  4  5  6  7
    int[][] adjMatrix = { {0, 1, 1, 0, 0, 0, 0},
                          {1, 0, 0, 1, 1, 1, 0},
                          {1, 0, 0, 0, 0, 0, 1},
                          {0, 1, 0, 0, 0, 0, 1},
                          {0, 1, 0, 0, 0, 0, 1},
                          {0, 1, 0, 0, 0, 0 ,0},
                          {0, 0, 1, 1, 1, 0, 0}  };


        new myGraphs(adjMatrix);
 }

1. Как определяются st и que ?

2. является ли ваш график направленным? в противном случае сложно получить один правильный результат для неориентированного графика.

3. @ThomasJungblut st — это стек, а que — очередь<int> = linkedlist<int>

4. @Ravi Я не думаю, что это направлено, приведенная выше матрица смежности показывает 1, если два числа соединены. Как или я должен сделать это направленным?

5. @RaviBhatt зачем ему ориентированный граф?

Ответ №1:

О следующем фрагменте в BFS:

 que.add(e);
nodeVisited[i]=1;
System.out.print(" "   i);
e = i;

Они почему вы меняете e и добавляете e в очередь? Мне это кажется неправильным.

1. вот как я могу выполнять поиск по матрице смежности, если бы я не изменил e, это привело бы к поиску только в столбце 0.

2. @TMan Нет. Вы изменяете e в первой строке цикла: e = que.remove(); и вот как работает BFS. Изучите BFS более глубоко.

3. хорошо, но должны ли все методы обхода выводиться одинаково?

4. @TMan, номер BFS должен посетить сначала вершину 0, затем все вершины, которые находятся на расстоянии 1 от 0. Такими вершинами являются 1 и 2. Далее, он должен посещать вершины с расстоянием, равным 2 от вершины 0. Таких вершин 3 4 5 6. Кажется, что ваш DFS дает правильный ответ.

5. Спасибо за ответы, действительно ценю это. Глядя на мой поиск в ширину, вы бы сказали, что я близок или далек от того, чтобы быть правым? Это доставляет мне намного больше проблем, чем должно быть.

Ответ №2:

Нерекурсивный BFS с использованием очереди:

 public int[] breadthFirstSearch(int[][] adjacencyMatrix, int start) {
    int totalNumberOfvertices = adjacencyMatrix.length;
    boolean[] visited = new boolean[totalNumberOfvertices];
    Queue<Integer> queue = new LinkedList<>();

    queue.add(start);
    visited[start] = true;

    List<Integer> list = new ArrayList<>();

    while (!queue.isEmpty()) {
        list.add(queue.peek());
        int currentFirstElementInQueue = queue.poll();

        for (int i = 0; i < adjacencyMatrix.length; i  ) {
            if ((adjacencyMatrix[currentFirstElementInQueue][i] == 1) amp;amp; (!visited[i])) {
                queue.add(i);
                visited[i] = true;
            }
        }
    }

    int[] result = new int[list.size()];
    int i = 0;
    Iterator<Integer> itr = list.iterator();
    while (itr.hasNext()) {
        result[i  ] = itr.next();
    }
    return resu<
}

Ответ №3:

 public void BFS(int start)
{
    int v=a.length;//a[][] is adj matrix declared globally
    boolean visited[]=new boolean[v];//indexing done from 1 to n
    LinkedList<Integer> queue=new LinkedList<Integer>();
    visited[start]=true;
    queue.add(start);
    while(queue.size()!=0)
    {
        int x=queue.remove();
        System.out.print(x " ");
        for (int i=1; i < v; i  ) 
            if((a[x][i] == 1) amp;amp; (!visited[i]))
            {
              queue.add(i);
              visited[i]=true;
             }
     }
}