java - 仅使用深度优先搜索获取相邻顶点

Question

如何仅使用深度优先搜索来获取相邻顶点？

我正在使用深度优先搜索算法来搜索有向图，我的问题是我想让它只返回起始顶点的邻居，而不是继续进行直到到达死胡同。

假设我有顶点(A、B、C、D)和边 ((A -> B), (A -> C), (C -> D))我想要顶点 A 的所有邻居，而不是获取 B 和 C，它还包括 D，即使 D 不与 A 相邻？

  public void dfs(int x)  // depth-first search
  {                                 // begin at vertex 0
  vertexList[x].wasVisited = true;  // mark it
  displayVertex(x);                 // display it
  theStack.push(x);                 // push it

  while( !theStack.isEmpty() )      // until stack empty,
     {
     // get an unvisited vertex adjacent to stack top
     int v = getAdjUnvisitedVertex( theStack.peek() );
     if(v == -1)                    // if no such vertex,
        theStack.pop();
     else                           // if it exists,
        {
        vertexList[v].wasVisited = true;  // mark it
        displayVertex(v);                 // display it
        theStack.push(v);                 // push it
        }
     }  // end while

  // stack is empty, so we're done
  for(int j=0; j<nVerts; j++)          // reset flags
     vertexList[j].wasVisited = false;
  }  // end dfs
  // ------------------------------------------------------------
  // returns an unvisited vertex adj to v
public int getAdjUnvisitedVertex(int v)
  {
  for(int j=0; j<nVerts; j++)
     if(adjMat[v][j]==1 && vertexList[j].wasVisited==false)
        return j;
        System.out.println("Found unvisited vertex");
  return -1;
  }  // end getAdjUnvisitedVertex()

我知道我可以在创建顶点时存储顶点的邻居，但这意味着如果我将来必须进行更改，我将不得不进行很多更改，如果有人对如何引导我朝正确的方向有任何想法，我将非常感激!

Answer 1

如果您将图表示为邻接矩阵，那么您应该可以从与顶点 A 对应的行中获取所有非零条目。

for(int j=0; j<nVerts; j++)
 if(adjMat[v][j]==1) System.out.println("vertex " + j);

所以你不需要 dfs。