如何在有向图上实现深度优先搜索以访问所有顶点

Question

如何使用邻接矩阵对有向图进行深度优先搜索，其中它从随机顶点开始探索所有顶点？我尝试实现 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;
}
}
}

} }

Answer 1

1. 在有向图中，可能没有节点可以到达所有其他节点。那么在这种情况下，您期望什么？

如果至少有一个节点可以

2. 到达所有其他节点，您现在只知道它是哪一个，则可以选择一个随机节点，逆向传入边缘的方向找到一个根节点，您可以从中访问所有其他节点。

Answer 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在您的例子中)。