广度优先搜索
如图所示：是一个有向图的广度遍历过程。
广度优先搜索.png
/* 定义边的遍历状态 和边的种类 */
typedef enum { UNDISCOVERED, DISCOVERED, VISITED } VStatus;
/* s作为遍历的起点 */
void Graph::bfs(int s) {
/* 重置所有顶点的遍历状态(UNDISCOVERED) */
reset();
/* 初始化记录遍历路径的parent数组 */
parent.resize(n);
for (int i = 0; i < n; i++)
parent[i] = -1;
int v = s;
do
if (status(v) == UNDISCOVERED)
BFS(v);
while( s != (v = (++v % n)) );
}
/* 广度优先搜索算法（单个连通域）*/
void Graph::BFS(int v) {
std::queue<int> queue;
status(v) = DISCOVERED;
queue.push(v);
while(!queue.empty()) {
int v = queue.front();
queue.pop();
for (int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) {
if (UNDISCOVERED == status(u)) {
parent[u] = v; /* 记录遍历的父节点 */
queue.push(u);
status(u) = DISCOVERED; /* 更新顶点的遍历状态 */
}
status(v) = VISITED;
}
}
}
/* 顶点i中相对于顶点j的的下一邻接点 */
int nextNbr(int i, int j) {
while( (-1 < --j) && !(existEdge(i, j)) )
;
return j;
}
复杂度
除了作为输入的图本身外，BFS搜索所使用的空间，主要消耗在用于维护顶点访问次序的辅助队列，用于记录顶点和边状态的标识位向量。累计O(n) + O(n) +O(e) = O(n+e)
在时间方面，bfs本身对所有顶点的枚举供需要O(n)时间，而在BFS()的调用中，每个顶点，每条边均只耗费O(1)时间，累计O(n+e)。综合起来，总体是O(n+e)
深度优先搜索
深度优先搜索选取下一顶点的关键策略，可概括为：优先选取最后一个被访问到的顶点的邻居
于是，以顶点s为基点的DFS搜索，将首先访问顶点s；再从s所有尚未访问到的邻居中任取其一，并以此为基点，递归的执行DFS搜索。故各顶点的访问次序类似于树的先序遍历；
1.png
2.png
3.png
/* 定义边的遍历状态 和边的种类 */
typedef enum { UNDISCOVERED, DISCOVERED, VISITED } VStatus;
void Graph::dfs(int s)
{
/* 重置所有顶点的遍历状态 */
reset();
/* 初始化记录遍历路径的parent数组 */
parent.resize(n);
for (int i = 0; i <= n; i++)
parent[i] = -1;
/* 逐一检查所有顶点 */
int v = s;
do
if (UNDISCOVERED == status(v)) // 一旦遇到尚未发现的顶点
DFS(v); // 即从该定点出发启动一次DFS
while(s != (v = (++v % n))); // 按序号检查，不重不漏
}
/* 深度优先搜索DFS算法(单个连通域) */
void Graph::DFS(int v) {
status(v) = DISCOVERED;
for (int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) {
if (status(u) == UNDISCOVERED) {
parent[u] = v;
DFS(u);
}
}
status(v) = VISITED;
}
算法的实质功能，由子算法DFS()递归完成。每一递归实例中，都先将当前节点v标记为DISCOVERED(已发现)状态，再逐一核对其各邻居u的状态并做相应处理。待其所有邻居均已处理完毕之后，将顶点v置VISITED(访问完毕)，便可回溯。
若顶点u尚处于UNDISCOVERED(未发现)状态，则将边(v, u)归类为树边，并将v记作u的父节点。然后将u作为当前节点，继续递归遍历。(若顶点u处于DISCOVERED状态，则意味着在此处发现一个有向回路)
