深度优先搜索

深度优先搜索(Depth-First Search, DFS, 台湾称“纵向优先搜寻”)是最简单的图搜索算法之一。这种算法遵循的原则是尽可能“深”地搜索一个图。可以说,当写一个程序需要遍历搜索一个图时,深度优先搜索是一个更加明显的算法,因为度优先搜索有着明显的递归算法的特点。虽然广度优先搜索直观上更加简单,但是相比程序实现的难度,深度优先搜索更加容易。
与广度优先搜索相同,深度优先搜索在运行过程中也将结点标识为三种状态:

  • 白色:未被发现的结点;
  • 灰色:已被发现,但与其相连的结点尚未全部发现的结点(下一轮进行发现的备选结点);
  • 黑色:已被发现,且与之相连的其他结点也已经发现。

对于每个结点u,深度优先搜索算法计算以下几项信息:

  • π[u]:深度优先森林中u的父结点,意味着u第一次被发现时所通过的上一级结点;
  • d[u]:发现结点u时的系统时间戳;
  • f[u]:遍历过结点u后的系统时间戳;
  • color[u]:u结点的颜色。

根据颜色的定义以及d[u],f[u]的定义,一个结点ud[u]之前是白色的,在d[u]f[u]之间是灰色的,而在f[u]之后是黑色的。

设图G = (V, E)V是顶点集,E是边集。s是起始节点。
则深度优先搜索(Depth-First Search, DFS)算法如下:
[code=’c#’]
// 系统时间戳
static int time = 0;

// 初始化整个图
foreach(Vertex u in V[G])
{
u.Color = DFSColor.WHITE;
u.D = 0;
u.F = int.MaxValue;
u.π = null;
}
foreach(Vertex u in V[G])
{
if(u.Color == DFSColor.WHITE)
{
DFSVisit(G, u);
}
}

void DFSVisit(Graph G, Vertex u)
{
u.Color = DFS.GRAY;
u.D = ++time;
foreach(Vertex v in u.Neighbors)
{
if(v.Color == DFSColor.WHITE)
{
v.π = u;
DFSVisit(G, v);
}
}
u.Color = DFSColor.BLACK;
u.F = ++time;
}
[/code]
深度优先搜索(Depth-First Search, DFS)的算法复杂度是O(V+E),其中O(V)时间用于第一步初始化,O(E)时间用于遍历(因为每个结点的邻接表只会访问一次)。

推荐文章

发表评论