广度优先搜索(BFS)
自顶点s的广度优先搜索(Breadth-First Search)
(1) 访问顶点s
(2) 依次访问s所有尚未访问的邻接顶点
(3) 依次访问以上被访问过顶点的尚未访问的邻接顶点
(4) 如此反复,直至没有尚未访问的邻接顶点
template <typename Tv, typename Te> // 顶点类型、边类型
void Graph<Tv, Te>::BFS(int v, int & clock) {
Queue<int> Q;
status(v) = DISCOVERED;
Q.enqueue(v); // 初始化
while (!Q.empty()) {
int v = Q.dequeue();
dTime(v) = ++clock; // 取出队首顶点v
for (int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) { // 考察v的每一个邻接顶点u
if (UNDISCOVERED == status(u)) { // 若u尚未被发现
status(u) = DISCOVERED;
Q.enqueue(u); // 发现该顶点
status(v, u) = TREE;
parent(u) = v; // 引入树边
} else { // 若u已被发现(正在队列中),或已访问完毕(已出队列)
status(v, u) = CROSS; // 将(v, u)归类于跨边
}
}
status(v) = VISITED; // 当前顶点访问完毕
}
}
template <typename Tv, typename Te> // 顶点类型、边类型
void Graph<Tv, Te>::bfs(int s) { // s为起始顶点
reset();
int clock = 0;
int v = s; // 初始化
do { // 逐一检查所有顶点,一旦遇到尚未发现的顶点
if (UNDISCOVERED == status(v))
BFS(v, clock); // 即从该顶点出发启动一次BFS
} while (s != (v = (++v % n))); // 按序号访问,不漏不重
}
深度优先搜索(DFS)
自顶点s的深度优先搜索(Depth-First Search)
(1) 访问顶点s
(2) 若s尚有未被访问的邻居,则任取一u,递归执行DFS(u)
(3) 否则,返回
template <typename Tv, typename Te> // 顶点类型、边类型
void Graph<Tv, Te>::DFS(int v, int & clock) {
dTime(v) = ++clock;
status(v) = DISCOVERED; // 发现当前顶点v
for (int u = firstNbr(v); -1 < u; u = nextNbv(v, u)) { // 枚举v的每一个相邻顶点u
switch(status(u)) { // 视其状态分别处理
case UNDISCOVERED: // u尚未发现,意味着支撑树可在此拓展
status(v, u) = TREE;
parent(u) = v;
DFS(u, clock);
break; // 递归
case DISCOVERED: // u已被发现但尚未访问完毕,应属被后代指向的祖先
status(v, u) = BACKWARD;
break;
default: // u已访问完毕,视承袭关系分为前向边或跨边
status(v, u) = dTime(v) < dTime(u) ? FORWARD : CROSS;
break;
}
}
status(v) = VISITED;
fTime(v) = ++clock; // 至此,当前顶点v访问完毕
}
顶点的活动期 active[u] = (dTime[u], fTime[u])
括号引理(Parenthesis Lemma):给定有向图G = (V, E)及其任一DFS森林,则
u是v的后代 iff active[u] ⊆ active[v]
u是v的先代 iff active[u] ⊇ active[v]
u与v无关 iff active[u] ∩ active[v] = Ø
网友评论