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

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

0 голосов
/ 16 мая 2019

Как мы выполняем поиск в глубину в ориентированном графе, используя матрицу смежности, в которой он исследует все вершины, начиная со случайной вершины? Я попытался реализовать 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("\n"+(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 голос
/ 16 мая 2019

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

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

0 голосов
/ 16 мая 2019

В вашем коде есть пара проблем, одна из которых заключается в том, что вы делаете 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 в вашем случае).

...