Как реализовать поиск в глубину на ориентированном графе, чтобы посетить все вершины

Как мы выполняем поиск в глубину в ориентированном графе, используя матрицу смежности, в которой он исследует все вершины, начиная со случайной вершины? Я пытался реализовать dfs, но он изучал только вершины, которые достижимы из начальной вершины.

      public static void dfs(int [] [] adjMatrix, int startingV,int n)
      {

      boolean [] visited = new boolean[n];
      Stack<Integer> s = new Stack<Integer>();

      s.push(startingV);

      while(!s.isEmpty())
      {
          int vertex = s.pop();
          if(visited[vertex]==false)
          {
              System.out.print("
"+(v));
              visited[vertex]=true;
          }
          for ( int i = 0; i < n; i++)
          {
              if((adjMatrix[vertex][i] == true) && (visited[i] == false))
              {
                  s.push(vertex);
                  visited[I]=true;
                  System.out.print(" " + i);
                  vertex = i;
              }
          }
      }

}}

Всего 2 ответа


  1. В ориентированном графе может отсутствовать узел, из которого вы можете добраться до всех остальных узлов. Так что вы ожидаете в этом случае?

  2. Если есть хотя бы один узел, с которого вы можете связаться со всеми остальными узлами, которые вы только теперь знаете, какой это узел, вы можете выбрать случайный, пойти против направления входящего ребра, чтобы найти корневой узел, из которого вы можете добраться. все остальные узлы.


У вашего кода есть пара проблем, одна из которых заключается в том, что вы делаете int vertex = s.pop(); и позже s.push(vertex); с той же вершиной. Последний, вероятно, должен быть s.push(i); вместо.

Самый простой способ реализовать обход DF - просто использовать рекурсию. Тогда код распадается на

function dfs(v) {
  if v not visited before {
    mark v as visited;
    for every adjacent vertex a of v do {
      dfs(a);
    }
    do something with v; // this is *after* all descendants have been visited.
  }
}

Конечно, каждая рекурсивная реализация может быть эквивалентно реализована с использованием стека и итерации, но в вашем случае это будет несколько сложнее, потому что вам нужно будет не только сохранить текущую вершину в стеке, но и состояние итерации по его потомки (переменная цикла i в вашем случае).