如果图表存储为Adajacency List,为什么DFS在O(V + E)中运行？

Question

DFS工作程序和运行复杂性.

Answer 1

深度优先搜索或DFS,因为它通常被称为图形/树遍历算法.

这个怎么运作

考虑如下所示的图表

现在让我们深入了解这些数字是如何出现的.

我们从起始节点开始并将其标记为已访问,然后我们将其添加到堆栈的顶部.我们总是在堆栈顶部寻找元素的非访问邻居.

第一步后:

Stack = A
Output = A
Visited = A

现在我们有3个邻居A,如果没有提供选择它们的顺序,我们可以选择任何一个邻居.我们移动到B并将其推到堆栈的顶部并将其标记为已访问并添加到序列中.

Stack = A,B
Output = A,B
Visited = A,B

现在B再次只有两个邻居,所以我们移动到它的下一个邻居,将它移动到堆栈顶部,将其添加到序列并将其标记为已访问.

Stack = A,B,D
Output = A,B,D
Visited = A,B,D

现在D没有更多的邻居并且是叶子节点,所以我们从堆栈的顶部弹出D.

Stack = A,B
Output = A,B,D
Visited = A,B,D

现在我们在堆栈的顶部有B,我们已经访问过D,所以我们移动到它的下一个邻居是F,所以我们将F添加到堆栈的顶部,将其标记为已访问并将其添加到序列中.

Stack = A,B,F
Output = A,B,D,F
Visited = A,B,D,F

现在F只有一个邻居,所以我们继续前进.我们遵循给出的节点E的相同过程

Stack = A,B,F,E
Output = A,B,D,F,E
Visited = A,B,D,F,E

现在,E的直接邻居节点是A,但是我们已经访问过A并且没有从E到哪里,所以我们从堆栈的顶部弹出它.

Stack = A,B,F
Output = A,B,D,F,E
Visited = A,B,D,F,E

同样地,我们也访问了F的所有邻居,因此我们从堆栈顶部弹出F.

Stack = A,B
Output = A,B,D,F,E
Visited = A,B,D,F,E

我们没有从B遍历的路径,因此我们也从堆栈中弹出B

Stack = A
Output = A,B,D,F,E
Visited = A,B,D,F,E

现在A的下一个邻居是C,所以我们将C添加到堆栈的顶部并将其标记为已访问.

Stack = A,C
Output = A,B,D,F,E,C
Visited = A,B,D,F,E,C

G是我们节点C的直接邻居,因此我们将它添加到堆栈的顶部并将其标记为已访问

Stack = A,C,G
Output = A,B,D,F,E,C,G
Visited = A,B,D,F,E,C,G

由于G是叶子节点,因此我们没有路径,所以我们从堆栈中弹出它

Stack = A,C
Output = A,B,D,F,E,C,G
Visited = A,B,D,F,E,C,G

因为我们已经遍历了C以外的所有节点,所以我们也从堆栈中弹出它们

Stack = A
Output = A,B,D,F,E,C,G
Visited = A,B,D,F,E,C,G

A的下一个邻居是E,但我们已将其标记为已访问,因此我们没有来自A的路径,因此我们从堆栈中弹出A并且堆栈变空为我们提供DFS序列.

Stack = null
Output = A,B,D,F,E,C,G
Visited = A,B,D,F,E,C,G

PS:对于任何语法错误,我们深表歉意