我在这个问题上花了很多时间。但是，我只能为树找到具有非递归方法的解决方案：树的非递归方法，或图的递归方法，图的递归方法。
许多教程（我在这里不提供这些链接）也没有提供方法。或者教程完全不正确。请帮我。
更新：
真的很难形容：
如果我有一个无向图：
1
/ | \
4 | 2
3 /
1-- 2-- 3 --1是一个循环。
在这一步：'将弹出顶点的邻居推入堆栈'，顶点应该被推入的顺序是什么？
如果压入顺序为2, 4, 3, 则栈中的顶点为：
| |
|3|
|4|
|2|
_
弹出节点后，我们得到结果：1 -> 3 -> 4 -> 2而不是1--> 3 --> 2 -->4.
这是不正确的。我应该添加什么条件来停止这种情况？
没有递归的 DFS 与BFS基本相同——但使用堆栈而不是队列作为数据结构。
线程迭代 DFS 与递归 DFS 和不同的元素顺序处理两种方法以及它们之间的区别（并且存在！您不会以相同的顺序遍历节点！）
迭代方法的算法基本上是：
DFS(source):
s <- new stack
visited <- {} // empty set
s.push(source)
while (s is not empty):
current <- s.pop()
if (current is in visited):
continue
visited.add(current)
// do something with current
for each node v such that (current,v) is an edge:
s.push(v)
这不是一个答案，而是一个扩展评论，展示了算法在@amit 对当前版本问题中的图表的回答中的应用，假设 1 是起始节点，其邻居按 2、4、 3：
1
/ | \
4 | 2
3 /
Actions Stack Visited
======= ===== =======
push 1 [1] {}
pop and visit 1 [] {1}
push 2, 4, 3 [2, 4, 3] {1}
pop and visit 3 [2, 4] {1, 3}
push 1, 2 [2, 4, 1, 2] {1, 3}
pop and visit 2 [2, 4, 1] {1, 3, 2}
push 1, 3 [2, 4, 1, 1, 3] {1, 3, 2}
pop 3 (visited) [2, 4, 1, 1] {1, 3, 2}
pop 1 (visited) [2, 4, 1] {1, 3, 2}
pop 1 (visited) [2, 4] {1, 3, 2}
pop and visit 4 [2] {1, 3, 2, 4}
push 1 [2, 1] {1, 3, 2, 4}
pop 1 (visited) [2] {1, 3, 2, 4}
pop 2 (visited) [] {1, 3, 2, 4}
因此，应用按 2、4、3 顺序推送 1 的邻居的算法会导致访问顺序为 1、3、2、4。无论 1 的邻居的推送顺序如何，2 和 3 在访问顺序中都是相邻的，因为无论哪个被访问first 将推送尚未访问过的另一个，以及已访问过的 1。
DFS 逻辑应该是：
1）如果当前节点未被访问，则访问该节点并将其标记为已访问
2）对其所有未访问的邻居，将它们压入堆栈
例如，让我们在 Java 中定义一个 GraphNode 类：
class GraphNode {
int index;
ArrayList<GraphNode> neighbors;
}
这是没有递归的DFS：
void dfs(GraphNode node) {
// sanity check
if (node == null) {
return;
}
// use a hash set to mark visited nodes
Set<GraphNode> set = new HashSet<GraphNode>();
// use a stack to help depth-first traversal
Stack<GraphNode> stack = new Stack<GraphNode>();
stack.push(node);
while (!stack.isEmpty()) {
GraphNode curr = stack.pop();
// current node has not been visited yet
if (!set.contains(curr)) {
// visit the node
// ...
// mark it as visited
set.add(curr);
}
for (int i = 0; i < curr.neighbors.size(); i++) {
GraphNode neighbor = curr.neighbors.get(i);
// this neighbor has not been visited yet
if (!set.contains(neighbor)) {
stack.push(neighbor);
}
}
}
}
我们可以使用相同的逻辑递归地进行 DFS、克隆图等。
很多人会说，非递归 DFS 就是带栈的 BFS，而不是队列。这不准确，让我再解释一下。
递归 DFS 使用调用堆栈来保持状态，这意味着您无需自己管理单独的堆栈。
但是，对于大型图，递归 DFS（或任何递归函数）可能会导致深度递归，这可能会使您的问题因堆栈溢出而崩溃（不是这个网站，真实的东西）。
DFS 与 BFS 不同。它具有不同的空间利用率，但是如果您像 BFS 一样实现它，但使用堆栈而不是队列，您将使用比非递归 DFS 更多的空间。
考虑一下：
// From non-recursive "DFS"
for (auto i&: adjacent) {
if (!visited(i)) {
stack.push(i);
}
}
并将其与此进行比较：
// From recursive DFS
for (auto i&: adjacent) {
if (!visited(i)) {
dfs(i);
}
}
在第一段代码中，您将所有相邻节点放入堆栈中，然后再迭代到下一个相邻顶点，这会产生空间成本。如果图表很大，它可以产生显着的差异。
如果您决定在弹出堆栈后通过再次迭代邻接列表来解决空间问题，那将增加时间复杂度成本。
一种解决方案是在您访问项目时将项目一项一项添加到堆栈中。为此，您可以在堆栈中保存一个迭代器以在弹出后恢复迭代。
在 C/C++ 中，一种懒惰的方法是使用更大的堆栈大小编译程序并通过 增加堆栈大小ulimit，但这真的很糟糕。在 Java 中，您可以将堆栈大小设置为 JVM 参数。
递归是一种使用调用栈来存储图遍历状态的方法。您可以显式使用堆栈，例如通过具有 type 的局部变量std::stack，那么您将不需要递归来实现 DFS，而只需一个循环。
Python 代码。时间复杂度为O ( V + E )，其中V和E分别是顶点和边的数量。空间复杂度为 O( V )，因为最坏的情况是存在一条包含每个顶点且没有任何回溯的路径（即搜索路径是线性链）。
堆栈存储形式为 (vertex, vertex_edge_index) 的元组，以便 DFS 可以从紧跟从该顶点处理的最后一条边的边处的特定顶点恢复（就像递归 DFS 的函数调用堆栈）。
示例代码使用一个完整的有向图，其中每个顶点都连接到每个其他顶点。因此没有必要为每个节点存储一个显式的边列表，因为图是一个边列表（图G包含每个顶点）。
numv = 1000
print('vertices =', numv)
G = [Vertex(i) for i in range(numv)]
def dfs(source):
s = []
visited = set()
s.append((source,None))
time = 1
space = 0
while s:
time += 1
current, index = s.pop()
if index is None:
visited.add(current)
index = 0
# vertex has all edges possible: G is a complete graph
while index < len(G) and G[index] in visited:
index += 1
if index < len(G):
s.append((current,index+1))
s.append((G[index], None))
space = max(space, len(s))
print('time =', time, '\nspace =', space)
dfs(G[0])
输出：
time = 2000
space = 1000
请注意，这里的时间是测量V操作而不是E。该值为numv *2 因为每个顶点都被考虑两次，一次是在发现时，一次是在完成时。
好的。如果您仍在寻找 java 代码
dfs(Vertex start){
Stack<Vertex> stack = new Stack<>(); // initialize a stack
List<Vertex> visited = new ArrayList<>();//maintains order of visited nodes
stack.push(start); // push the start
while(!stack.isEmpty()){ //check if stack is empty
Vertex popped = stack.pop(); // pop the top of the stack
if(!visited.contains(popped)){ //backtrack if the vertex is already visited
visited.add(popped); //mark it as visited as it is not yet visited
for(Vertex adjacent: popped.getAdjacents()){ //get the adjacents of the vertex as add them to the stack
stack.add(adjacent);
}
}
}
for(Vertex v1 : visited){
System.out.println(v1.getId());
}
}
实际上，stack 并不能很好地处理发现时间和完成时间，如果我们想用 stack 实现 DFS，并且想要处理发现时间和完成时间，我们需要求助于另一个记录器堆栈，我的实现如下所示下面，测试正确，下面是 case-1、case-2 和 case-3 图。
from collections import defaultdict
class Graph(object):
adj_list = defaultdict(list)
def __init__(self, V):
self.V = V
def add_edge(self,u,v):
self.adj_list[u].append(v)
def DFS(self):
visited = []
instack = []
disc = []
fini = []
for t in range(self.V):
visited.append(0)
disc.append(0)
fini.append(0)
instack.append(0)
time = 0
for u_ in range(self.V):
if (visited[u_] != 1):
stack = []
stack_recorder = []
stack.append(u_)
while stack:
u = stack.pop()
visited[u] = 1
time+=1
disc[u] = time
print(u)
stack_recorder.append(u)
flag = 0
for v in self.adj_list[u]:
if (visited[v] != 1):
flag = 1
if instack[v]==0:
stack.append(v)
instack[v]= 1
if flag == 0:
time+=1
temp = stack_recorder.pop()
fini[temp] = time
while stack_recorder:
temp = stack_recorder.pop()
time+=1
fini[temp] = time
print(disc)
print(fini)
if __name__ == '__main__':
V = 6
G = Graph(V)
#==============================================================================
# #for case 1
# G.add_edge(0,1)
# G.add_edge(0,2)
# G.add_edge(1,3)
# G.add_edge(2,1)
# G.add_edge(3,2)
#==============================================================================
#==============================================================================
# #for case 2
# G.add_edge(0,1)
# G.add_edge(0,2)
# G.add_edge(1,3)
# G.add_edge(3,2)
#==============================================================================
#for case 3
G.add_edge(0,3)
G.add_edge(0,1)
G.add_edge(1,4)
G.add_edge(2,4)
G.add_edge(2,5)
G.add_edge(3,1)
G.add_edge(4,3)
G.add_edge(5,5)
G.DFS()
我认为您需要使用visited[n]布尔数组来检查当前节点是否被访问过。
递归算法对 DFS 非常有效，因为我们尝试尽可能深入，即。一旦我们找到一个未探索的顶点，我们将立即探索它的第一个未探索的邻居。找到第一个未探索的邻居后，您需要立即跳出 for 循环。
for each neighbor w of v
if w is not explored
mark w as explored
push w onto the stack
BREAK out of the for loop
在递归过程中使用堆栈并通过调用堆栈实现 -
想法是将一个顶点推入堆栈，然后将其相邻的顶点推入该顶点的索引处，该顶点存储在邻接列表中，然后继续此过程，直到我们无法在图中进一步移动，现在如果我们不能在图中向前移动，然后我们将删除当前位于堆栈顶部的顶点，因为它无法将我们带到任何未访问的顶点上。
现在，使用堆栈我们处理了这样一个点，即只有当所有可以从当前顶点探索的顶点都已被访问时，顶点才会从堆栈中删除，这是由递归过程自动完成的。
(0 (1 (2 (4 4) 2) (3 3) 1) 0) (6 (5 5) (7 7) 6)
上面的括号显示了顶点在堆栈中添加和从堆栈中删除的顺序，因此只有当所有可以访问的顶点都完成后，顶点的括号才会关闭。
（这里我使用了邻接列表表示，并通过使用 C++ STL 实现为列表的向量（向量 > AdjList））
void DFSUsingStack() {
/// we keep a check of the vertices visited, the vector is set to false for all vertices initially.
vector<bool> visited(AdjList.size(), false);
stack<int> st;
for(int i=0 ; i<AdjList.size() ; i++){
if(visited[i] == true){
continue;
}
st.push(i);
cout << i << '\n';
visited[i] = true;
while(!st.empty()){
int curr = st.top();
for(list<int> :: iterator it = AdjList[curr].begin() ; it != AdjList[curr].end() ; it++){
if(visited[*it] == false){
st.push(*it);
cout << (*it) << '\n';
visited[*it] = true;
break;
}
}
/// We can move ahead from current only if a new vertex has been added on the top of the stack.
if(st.top() != curr){
continue;
}
st.pop();
}
}
}
我认为这是一个关于空间的优化 DFS，如果我错了，请纠正我。
s = stack
s.push(initial node)
add initial node to visited
while s is not empty:
v = s.peek()
if for all E(v,u) there is one unvisited u:
mark u as visited
s.push(u)
else
s.pop
下面的 Java 代码会很方便：-
private void DFS(int v,boolean[] visited){
visited[v]=true;
Stack<Integer> S = new Stack<Integer>();
S.push(v);
while(!S.isEmpty()){
int v1=S.pop();
System.out.println(adjLists.get(v1).name);
for(Neighbor nbr=adjLists.get(v1).adjList; nbr != null; nbr=nbr.next){
if (!visited[nbr.VertexNum]){
visited[nbr.VertexNum]=true;
S.push(nbr.VertexNum);
}
}
}
}
public void dfs() {
boolean[] visited = new boolean[adjLists.size()];
for (int v=0; v < visited.length; v++) {
if (!visited[v])/*This condition is for Unconnected Vertices*/ {
System.out.println("\nSTARTING AT " + adjLists.get(v).name);
DFS(v, visited);
}
}
}