购买油烟机就看大吸力.doc

一、深度优先搜索
二、广度优先搜索
图的遍历
遍历定义:从已给的连通图中某一顶点出发,沿着一些边访遍图中所有的顶点,且使每个顶点仅被访问一次,就叫做图的遍历,它是图的基本运算。
遍历实质:找每个顶点的邻接点的过程。
图的特点:图中可能存在回路,且图的任一顶点都可能与其它顶点相通,在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。
解决思路:可设置一个辅助数组 visited [n ],用来标记每个被访问过的顶点。它的初始状态为0,在图的遍历过程中,一旦某一个顶点i 被访问,就立即改 visited [i]为1,防止它被多次访问。
图常用的遍历:
怎样避免重复访问?
一、深度优先搜索( DFS )
:——从某顶点出发,沿某条路一直走下去,一旦不好走,就退回去再走。
Depth_First Search
v1
v1
v2
v3
v8
v7
v6
v4
v5
DFS 结果
例1:
→
→
→
→
→
→
→
v2
v4
v8
v5
v3
v6
v7
例2:
v2 → v1 → v3 → v5 →
DFS 结果
v4 → v6
起点
起点
遍历步骤
(遍历)步骤:
归纳:
(1) 访问起始点 v,并设已访问标志;
(2) 若v的第1个邻接点没访问过,深度遍历此邻接点;
(3) 若当前邻接点已访问过,再找v的下一个邻接点重新遍历。
效果:
(1) 对连通图
(2) 对非连通图
遍历了整个图。
遍历了图的一个连通分量。
讨论2: DFS算法如何编程?
void ExtMGraph <T>::DFS (int v, void *visit())
{
visit(v);
visited[v]=1;
for( j=0; j<n; j++)
if ( A[v, j] && ! visited[j] ) DFS (j, visit);
return;
}
——可以用递归算法!
//设A[n][n]为邻接矩阵,v为起始顶点(编号)
//访问(例如打印)顶点v
// DFS
A[v,j] =1
有邻接点
visited [j ]=0
未访问过
//访问后立即修改辅助数组标志
//从v所在行从头搜索邻接点
建议:在递归函数中增加一计数器sum,初值为n,每访问一次就减1,减到0则return,可避免递归时间过长。
深度优先
二、广度优先搜索( BFS )
:——仿树的层次遍历过程。
Breadth_First Search
v1
v1
v2
v3
v8
v7
v6
v4
v5
BFS 结果
例1:
→
→
→
→
v2
v3
→
v4
v5
→
v6
v7
→
v8
例2:
v3 →
BFS 结果
v4 → v5 →
起点
遍历步骤
起点
v2 → v1 → v6 →
v9 → v8 → v7
(遍历)步骤:
简单归纳:
在访问了起始点v之后,依次访问 v的邻接点;
然后再依次访问这些顶点中未被访问过的邻接点;
直到所有顶点都被访问过为止。
广度优先搜索是一种分层的搜索过程