没有合适的资源?快使用搜索试试~ 我知道了~
数据结构 第七章-图2PPT课件.pptx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 173 浏览量
2021-10-08
07:36:51
上传
评论
收藏 947KB PPTX 举报
温馨提示
试读
64页
数据结构 第七章-图2PPT课件.pptx
资源推荐
资源详情
资源评论
【重点掌握】:
1. 图的两种遍历方法:遍历的定义、深度优先搜索遍历和
广度优先搜索遍历的算法;
2. 应用图的遍历算法判断图的连通性及求图的生成树;
3. 用 Prim 、 Kruskal 算法求图的最小生成树;
4. 用 Dijkstra 算法求解单源最短路径问题;用 Floyd 算
法求所有顶点间的最短路径问题;
5. 利用 AOV 网进行拓扑排序;利用 AOE 网求关键路径问
题;
【掌 握】:
6. 掌握图的定义和术语;
7. 图的各种存储结构及其构造算法、在实际问题中的求解
效率。
第 1 页 / 共 99 页
7.3 图 的 遍 历
7.3 图的遍历:从图的某顶点出发,访问图中所有顶点,
并且每个顶点仅访问一次。
图结构的遍历复杂性:
( 1 )在图结构中,没有一个“自然”的首结点,图中的任意
一个顶点都可以作为第一个被访问的结点
( 2 )在非连通图中,从一个顶点出发,只能访问它所在的
连通分量上的所有顶点,因此,还需考虑如何选取下一个出
发点以访问图中的其余连通分量
( 3 )在图结构中,如果有回路存在,那么一个顶点被访问
后,有可能沿回路又回到该顶点,考虑如何避免重复访问
( 4 )在图结构中,一个顶点可以和其他多个顶点邻接,当
这样的顶点访问过后,考虑如何选取下一个要访问的顶点的
问题
第 2 页 / 共 99 页
图的遍历方法有深度优先遍历和广度优先遍历两种。
7.3.1 深度优先搜索
方法:
( 1 )从图的某一顶点 V
0
出发,访问此顶点;
( 2 )依次从 V
0
的未被访问的邻接点出发,深度优先遍历
图,直至图中所有和 V
0
相通的顶点都被访问到。 若此时
图中尚有顶点未被访问,则另选图中一个未被访问的顶点作
起点,重复上述过程,直至图中所有顶点都被访问到。
第 3 页 / 共 99 页
V0
V7
V6 V5 V4 V3
V2
V1
若图的存储结构为邻接表,则
访问邻接点的顺序不唯一,
深度优先序列不是唯一的
V0
V1
V3
V2
V7
V6
V5
V4
V0,V1,V3,V4,V7,V2,V5,V6,
※ 求图 G 以 V0 为起点的的深度优先序列(设存储结构为邻
接矩阵)
第 4 页 / 共 99 页
void DFS(Graph G, int v)
{/* 从第 v 个顶点出发,递归地深度优先遍历图 G*/
/* v 是顶点在一维数组中的位置,假设 G 是非空图 */
visited[v] =1;
Visit(v); /* 访问第 v 个顶点 */
for ( w=FirstAdjVex(G, v); w; w=NextAdjVex(G, v,
w) )
if (!visited[w]) DFS(G, w);
/* 对 v 的尚未访问的邻接顶点 w 递归调用 DFS*/
}
辅助数组: int
visited[Max_Vertex_Num] ;
访问标志数组 , 全局变量,初始时所有分
量全为 0 , visited[v]=1 表示顶点 v 已被
访问 .
visited
0
1
2
3
4
……
0
0
0
0
0
深度优先遍历算法 :
7.3 图 的 遍 历
第 5 页 / 共 99 页
剩余63页未读,继续阅读
资源评论
加油学习加油进步
- 粉丝: 1395
- 资源: 52万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功