文档介绍：图的遍历深度优先遍历和广度优先遍历
第1页，共44页，编辑于2022年，星期五
20、图的遍历深度优先遍历和广度优先遍历
掌握图的深度优先和广度优先遍历的性质和方法，以及基于邻接矩阵和邻接表存储结构的递归和非递归的算法实现
{ //图深度优先遍历递归算法。从结点v0出发，深度优先遍历图g，返回访问到的结点总数
int nNodes; //寄存访问到的结点数目 
访问v0;
为v0置已访问标志;
nNodes=1;
求出v0的第1个可达邻接点v;
while (v存在)
{
if (v未被访问过) nNodes=nNodes+DFS(g,v);
求出v0的下个可达邻接点v;
}
return nNodes;
}
第11页，共44页，编辑于2022年，星期五
1
2
5
4
3
1 2 3 4 5
1 0 1 0 0 1
2 1 0 0 1 0
3 0 0 0 0 1
4 1 0 0 0 0
5 0 0 0 0 0
所示图的邻接矩阵g
1 1
2 1
3 0
4 1
5 1
图 20‑1有向图
访问标识数组
visited
1
2
4
5
输出数组
resu
例如从1点深度优先遍历，先把1设置访问标志，并置入输出数组resu，然后从邻接矩阵的第一行，扫描各列，找到最近的邻接点2，将其设置访问标志，并进入输出数组，接着从邻接矩阵的2行扫描，找到第一个构成边的点是1，检查访问标识数组，发现1已经访问过，跳过，找第二个构成边 的点4，设置访问标识，进入输出数组，再从邻接矩阵的第4行扫描，寻找构成边的点，除1外在无其他点，返回2行，继续寻找，也无新点，返回1，找到5，将5置访问标志，进入输出数组，1行再无其他新点，遍历结束，返回遍历元素个数为4 。
第12页，共44页，编辑于2022年，星期五
2．邻接矩阵实现
这里我们为了突出主题、简化问题，假定图是用一般的邻接矩阵存储，邻接矩阵用简单的二维数组表示（静态），用0和1分别表示无边和有边。图结点用自然数编号。
long DFS1(int g[][CNST_NumNodes], long n, long v0,
char *visited,long *resu，long &top )
{//深度优先遍历图（递归）。图g为邻接矩阵，结点编号为
0~n. 返回实际遍历到的结点数目
//visited是访问标志数组，调用本函数前，应为其分配空间并初始化为全0(未访问)
//resu为一维数组，用于存放所遍历到的结点的编号，调用本函数前，应为其分配空间
第13页，共44页，编辑于2022年，星期五
long nNodes, i; 
nNodes=1;
resu[top++]=v0; //将访问到的结点依次存于resu[]
visited[v0]=1; //为v0置已访问标志
for (i=0; i<n; i++)
{//依次从v0的各个出点出发，深度优先遍历图
if (g[v0][i]!=0) //若<v0, i>是边
if (!visited[i]) //若结点i未被访问过
nNodes = nNodes+DFS1(g, n, i, visited,resu);
//从i起深度优先遍历图
}
return nNodes;
}
第1