Cor*_*oss 11 algorithm graph depth-first-search graph-algorithm
好的,这是我在Stack Overflow上的第一篇文章,我已经阅读了一段时间,真的很欣赏这个网站.我希望这是可以接受的问题.所以我一直在阅读Intro to Algorithms(Cormen.麻省理工学院出版社),我完全依赖于图算法.我一直在研究用于广度和深度优先详细搜索的正式算法.
这是深度优先搜索的伪代码:
DFS(G)
-----------------------------------------------------------------------------------
1 for each vertex u ? G.V
2 u.color ? WHITE // paint all vertices white; undiscovered
3 u.? ? NIL
4 time ? 0 // global variable, timestamps
5 for each vertex u ? G.V
6 if u.color = WHITE
7 DFS-VISIT(G,u)
DFS-VISIT(G, u)
-----------------------------------------------------------------------------------
1 u.color ? GRAY // grey u; it is discovered
2 time ? time + 1
3 u.d ? time
4 for each v ? G.Adj[u] // explore edge (u,v)
5 if v.color == WHITE
6 v.? ? u
7 DFS-VISIT(G,v)
8 u.color ? BLACK // blacken u; it is finished
9 time ? time + 1
10 u.f ? time
该算法是递归的,它从多个源开始(将在未连接的图中发现每个顶点).它有几个属性,大多数语言特定的实现可能会遗漏.它区分了3种不同的"颜色"顶点.它最初将所有这些都描绘成白色,然后当它们被"发现"(在DFS-VISIT中访问)时,它们将被涂成灰色.DFS-VISIT算法在当前顶点的邻接列表上递归调用自身循环,并且当它没有任何边缘到任何白色节点时仅绘制顶点黑色.
另外还保留了每个顶点的另外两个属性ud和uf是发现顶点(涂成灰色)或顶点完成(涂成黑色)时的时间戳.第一次绘制节点时,它的时间戳为1,并且每次绘制另一个时,它都会递增到下一个整数值(无论是灰色还是黑色).u.π也被维护,它只是指向发现u的节点的指针.
Algorithm Non-Recursive-DFS(G)
-----------------------------------------------------------------------------------
1 for each vertex u ? G.V
2 u.color ? WHITE
3 u.? ? NIL
4 time = 0
5 for each vertex u ? G.V
6 if u.color = WHITE
7 u.color ? GRAY
8 time ? time + 1
9 u.d ? time
7 push(u, S)
8 while stack S not empty
9 u ? pop(S)
10 for each vertex v ? G.Adj[u]
11 if v.color = WHITE
12 v.color = GRAY
13 time ? time + 1
14 v.d ? time
15 v.? ? u
16 push(v, S)
17 u.color ? BLACK
18 time ? time + 1
19 u.f ? time
*编辑10/31/12*令人尴尬的是,我的算法长期不正确,它在大多数情况下都有效,但不是全部.我刚刚得到了一个问题的流行问题徽章,我看到Irfy在下面的答案中发现问题的地方,所以这就是信用额度.我只是在这里修复它,以备将来需要它的人使用.
有没有人看到上述算法的缺陷？到目前为止,我还不是图论的专家,但我认为我对递归和迭代有很好的把握,我相信这应该是一样的.我希望它在功能上等同于递归算法.即使不需要,它也应该保留第一个算法的所有属性.
当我开始写它时,我不认为我会有一个三重循环,但事实就是如此.当我环顾谷歌时,我已经看到了其他迭代算法,它只有一个双嵌套循环,但是,它们似乎没有从多个来源继续.(即他们不会发现未连接图的每个顶点)
两种算法都很好.第二个是从递归到基于堆栈的直接转换.所有变异状态都存储在堆栈中.G在执行算法期间永远不会改变.
算法将根据算法访问每个节点的顺序为每个断开连接的区域生成生成树.树将通过引用父节点(u.?)和段树(u.d和u.f)来表示.
子节点将具有对其父节点的引用(或者NULL如果它是根节点),并且它的range(child.d .. child.f)包含在其父节点范围内.
parent.d < child.d < child.f < parent.f
child.? = parent
编辑:我在翻译中发现了一个错误.您实际上并没有将当前状态推入堆栈,而是将来的方法参数.此外,您不会为弹出的节点着色GRAY并设置f字段.
这是对原始第一个算法的重写:
algorithm Stack-DFS(G)
for each vertex u ? G.V
u.color ? WHITE
u.? ? NIL
time ? 0
S ? empty stack
for each vertex u ? G.V
if u.color = WHITE
# Start of DFS-VISIT
step ? 1
index ? 0
loop unconditionally
if step = 1
# Before the loop
u.color ? GRAY
time ? time + 1
u.d ? time
step ? 2
if step = 2
# Start/continue looping
for each vertex v ? G.Adj[u]
i ? index of v
if i ? index and v.color = WHITE
v.? ? u
# Push current state
push((u, 2, i + 1), S)
# Update variables for new call
u = v
step ? 1
index ? 0
# Make the call
jump to start of unconditional loop
# No more adjacent white nodes
step ? 3
if step = 3
# After the loop
u.color ? BLACK
time ? time + 1
u.right ? time
# Return
if S is empty
break unconditional loop
else
u, step, index ? pop(S)
可能有一些地方可以优化,但至少应该现在可以工作.
结果:
Name d f ?
q 1 16 NULL
s 2 7 q
v 3 6 s
w 4 5 v
t 8 15 q
x 9 12 t
z 10 11 x
y 13 14 t
r 17 20 NULL
u 18 19 r