广度优先树

首先给定图$G$和目标搜索点$s$的情况下，定义前驱子图$G_{\pi }=(V_{\pi },E_{\pi })$，其中点集Vπ={v∈V∣v.π≠NIL}⋃{s}V_\pi=\{v\in V|v.\pi\ne NIL\}\bigcup\{s\}Vπ​={v∈V∣v.π​=NIL}⋃{s}，Eπ={(v.π,v)∣v∈V−{s}}E_\pi=\{(v.\pi,v)|v\in V-\{s\}\}Eπ​={(v.π,v)∣v∈V−{s}}。

可以看出前驱子图表达的是由目标点出发进行搜索，过程中组成的从中心向外的辐射结构，因为边是否在前驱子图内都由点的前驱所决定，如果前驱子图是一棵树而不是森林（不含孤立点，任意点都有最短路包含在前驱子图中），那么前驱子图是一棵广度优先树。

引理6. 有/无向图$G=(V,E)$中，$BFS$在每个节点所构建的$\pi$属性使得前驱子图成为一棵广度优先树。

$v.\pi =u$存在当且仅当该前驱到该点的边在图中存在，且该点定义距离目标点不是无穷，所以如果$v$可以由目标点到达，那么这些点$v$就共同构成了$V_{\pi }$。通过递归运用上节的广搜准确性定理获得了路径是图中的最短路径。

广度优先树的计算也是递归利用上述定理所完成的：

void Graph::PrintPath(char s, char v)
{
    if (v == s)
        cout << s << ' ';
    else if (G[index[v]]._pi == nullptr)
        cout << "NO Path" << endl;
    else
    {
        PrintPath(s, G[index[v]]._pi->_name);
        cout << v << ' ';
    }
}

利用前驱性质最终输出目标点到输入点的节点路径。

DFS(深度优先搜索)

深度优先搜索中定义了另一种前驱子图，其中改动是深搜的点集不包含搜索目标点，这与广搜宽搜的应用场景有很大关系：

• 广搜的应用更多的是查找距离某点最近的距离；
• 而宽搜的目的是作为子程序找到一个答案使其最优；

所以前者搜索从一个目标点出发搜索到数据就结束，而后者更多的是全图搜索，图很可能不是连续的，这也意味着有多个搜索目标点。

搜索算法原理实现

搜索中还需要再每个节点添加“时间戳”表示什么时候开始当前节点、什么时候回溯到当前节点，具体的需要做：

• 当前所有节点颜色定义为白色；
• 从任意一个点开始搜索，开始时将当前节点状态记录开始时间戳并赋为灰色；
• 在灰色节点的白色相邻节点开始继续调用搜索函数；
• 当程序回溯到某个灰色节点时赋为黑色并记录结束时间戳；

可以发现每个节点只有一次机会被搜索开始和搜索回溯，所以时间戳最大值为$2|V|$且开始时间戳$u.d$和结束时间戳$u.f$满足$u.d<u.f$。

并且可以得到在时间轴上：

• $t<u.d$时节点未被搜索为白色
• $t<u.d$时节点的临近节点正在被搜索为灰色
• $t>u.d$时节点已被搜索为黑色

程序实现为：

void Graph::DFS()
{
    for (auto i : G)
    {
        i._color = WHITE;
        i._pi = nullptr;
    }
    time = 0;
    for (auto i : G)
        if (i._color == WHITE)
            DFSVisit(i._name);
}
void Graph::DFSVisit(char u)
{
    G[index[u]]._d = ++time;
    G[index[u]]._color = GRAY;
    for (auto v = G[index[u]]._first; v; v = v->NEXT)
        if (G[index[v->adjvex]]._color == WHITE)
        {
            G[index[v->adjvex]]._pi = &G[index[u]];
            DFSVisit(v->adjvex);
        }
    G[index[u]]._color = BLACK;
    G[index[u]]._f = ++time;
}

上半部分DFS()方法主要任务是将节点初始化且搜索完整个图，图中存在不连通的子图造成单点搜索不能覆盖全图；下半部分DFSVisit()方法阐述了上面搜索步骤。

相关性质

由下图的搜索（先进入$s$进行搜索在进入$t$）可以发现在时间轴上搜索过程描述了一种括号化的结构。

[定理]括号化定理：在有向或无向图$G$中进行深搜，对于搜索过程中的任意两个节点u和v满足三种情况之一：

• $[u.d,u.f]$与$[v.d,v.f]$区间不重合，两个节点不存在父子关系；
• $[u.d,u.f]$在$[v.d,v.f]$区间内部，$u$是$v$的前驱子图某棵树（也有可能是只有一棵树）中的后代；
• 第二种情况的镜像；

当$u.d<v.d$情况下有两种情况：

1. 当$v.d<u,f$的时候v在搜索中的时候u仍为灰色，说明v是其后代且u的时间戳结束时v的状态是已经被搜索完毕，所以$v.f<u.f$证明其是子区间且为后代；
2. 当$v.d>u.f$时，根据不等式有$u.d<u.f<v.d<v.f$，得到两区间完全分离；

镜像情况类似。

[推论]相应的可以类推到v是u的后代当且仅当$u.d<v.d<v.f<u.f$不等式存在时成立。

[定理]白色路径定理：在有向或无向图$G$中进行深搜，u是v的后代当且仅当在时刻$u.d$存在一条白色节点组成的路径从u到v。

$\Rightarrow$：$u=v$时刻，算法设计中先定义时间再覆盖灰色所以自身还是白色成立；$v$为任意后代都满足上述类推$u.d<v.d$那么后续节点都为白色。

$\Leftarrow$：假定$v$不为$u$的后代且是搜索之后第一个不是$u$后代的节点，但存在一条白色路径，这样的话设$w=v.\pi$，那么有$w.f\le u.f$（推论成立，等号存在当且仅当$u=w$），因为$w=v.\pi$所以作为前驱要满足$v.f<w.f$同理推得v的时间戳区间被限制在u的区间内则满足定理的条件。