如何在不违反0 (|V | + |E|)的情况下在dfs树中存储节点级别

Question

是否有一种方法来存储每个顶点的水平在DFS树它属于它?

时间复杂度为O(|V| + |E|)

Answer 1

这是来自维基百科的标准DFS伪代码:

1  procedure DFS(G,v):
2      label v as discovered
3      for all edges from v to w in G.adjacentEdges(v) do
4          if vertex w is not labeled as discovered then
5              recursively call DFS(G,w)

添加级别:

1  procedure DFS(G,v,level):
2      label v as discovered
3      v.level = level
4      for all edges from v to w in G.adjacentEdges(v) do
5          if vertex w is not labeled as discovered then
6              recursively call DFS(G,w,level+1)

首先调用DFS(G,v,0)