数据结构第七章.ppt

《数据结构第七章.ppt》由会员分享，可在线阅读，更多相关《数据结构第七章.ppt（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构第七章第七章 图图1主要讨论的问题：图的定义主要讨论的问题：图的定义;图的存储结构图的存储结构;图的图的遍历遍历;最小生成树最小生成树;拓扑排序拓扑排序;最短路径最短路径;关键路径关键路径.7.1图的定义和术语图的定义和术语.图是一种较为复杂的数据结构图是一种较为复杂的数据结构.复杂性主要体现复杂性主要体现:图中任意两个数据元素之间图中任意两个数据元素之间的都可能有关系的都可能有关系.图的应用非常广泛图的应用非常广泛:表示一座城市的交通联系的情况；表示一座城市的交通联系的情况；用用有值图有值图可以表示两座城市之间的距离、车费、或班可以表示两座城市之间的距离、车费、或班次数目次数

2、目;表示城市之间建立的通讯网络表示城市之间建立的通讯网络;可以描述化学可以描述化学结构式结构式;图中两点之间的最短距离问题。图中两点之间的最短距离问题。2.图的定义图的定义 图图G是由两个集合是由两个集合V(G)和和E(G)组成的组成的,记为记为G=(V,E).其中其中:V(G)是是顶点顶点的非空有限的非空有限集集;E(G)是是边边的有限集合的有限集合,边是顶点的边是顶点的无序对或有序对无序对或有序对.有向图有向图 有向图有向图G是由两个集合是由两个集合V(G)和和E(G)组成组成的的 其中其中:V(G)是顶点的非空有限集是顶点的非空有限集.E(G)是是有向边有向边(也称弧也称弧)的有限集合的

3、有限集合,弧弧是顶点是顶点的有序对的有序对,记为记为,v,w是顶点是顶点,v为为弧弧尾尾,w为为弧头弧头.注意：注意：3.无向图无向图 无向图无向图G是由两个集合是由两个集合V(G)和和E(G)组成的组成的.其中其中:V(G)是顶点的非空有限集是顶点的非空有限集.E(G)是是边的有限集合边的有限集合,边是顶点的无序对边是顶点的无序对,记为记为(v,w)或或(w,v)，并且并且(v,w)=(w,v).图的其它相关术语图的其它相关术语 完全图完全图;有向完全图有向完全图;权权;网网;子图子图;邻接点邻接点;顶点顶点的度的度;入度入度;出度出度;路径路径;路径长度路径长度;回路回路(环环);简简单路

4、径单路径,连通图连通图;连图分量连图分量;强连通图强连通图;强连通分强连通分量量;连通图的生成树连通图的生成树.4.回忆广义表和树的存储结构回忆广义表和树的存储结构.7.2图的存储结构图的存储结构.数组表示法数组表示法(邻接矩阵邻接矩阵)-n个顶点用个顶点用n阶方阵表示阶方阵表示.用一个顶点表记用一个顶点表记录图中各顶点信息录图中各顶点信息,邻接矩阵表示各顶点之间邻接矩阵表示各顶点之间的关系的关系.设图设图A=(V,E)是一个有是一个有n个顶点的图个顶点的图,则图的邻接则图的邻接矩阵是一个二维数组矩阵是一个二维数组A.Edgenn.思考思考:无向图和有向图的邻接矩阵的特点无向图和有向图的邻接矩

5、阵的特点.5.在有向图中在有向图中,统计第统计第i行行1的个数可得顶点的个数可得顶点i的出的出度度,统计第统计第j列列1的个数可得顶点的个数可得顶点j的入度的入度.在无向图中在无向图中,统计第统计第i行行(列列)1的个数可得顶点的个数可得顶点i的度的度.6.网络的邻接矩阵网络的邻接矩阵7.无向图的邻接表无向图的邻接表 邻接表表示法邻接表表示法.把同一个顶点发出的边链接在同一个把同一个顶点发出的边链接在同一个边链表边链表中中,链表的每一个结点代表一条边链表的每一个结点代表一条边,叫做叫做边结点边结点,结点中结点中保存有与该边相关联的另一顶点的顶点保存有与该边相关联的另一顶点的顶点下标下标和指向和

6、指向同一链表中下一个边结点的同一链表中下一个边结点的指针指针.8.有向图的邻接表与逆邻接表有向图的邻接表与逆邻接表邻接表表示法邻接表表示法.在有向图的邻接表中在有向图的邻接表中,第第 i 个边链表链接的边都是个边链表链接的边都是顶点顶点 i 发出的边发出的边.也叫做也叫做出边表出边表.在有向图的逆邻接表中在有向图的逆邻接表中,第第 i 个边链表链接的边都是个边链表链接的边都是进入进入顶点顶点 i 的边的边.也叫做也叫做入边表入边表.9.网络网络(带权图带权图)的邻接表的邻接表邻接表表示法邻接表表示法.在邻接表的边链表中在邻接表的边链表中,各个边结点的链入顺序任各个边结点的链入顺序任意意,视边结

7、点输入次序而定视边结点输入次序而定.思考思考:n个顶点的无向图边结点个数个顶点的无向图边结点个数,有向图呢有向图呢(不考虑逆邻接表不考虑逆邻接表)?10.邻接矩阵与邻接表的适用场合邻接矩阵与邻接表的适用场合.邻接矩阵能非常方便地判断任意两个顶点之邻接矩阵能非常方便地判断任意两个顶点之间的关系间的关系.而邻接表则能非常方便地判断任意而邻接表则能非常方便地判断任意一个顶点有多少个相邻的邻接点一个顶点有多少个相邻的邻接点.7.3图的遍历图的遍历 从已给的连通图中某一顶点出发从已给的连通图中某一顶点出发,沿着一些沿着一些边边访遍访遍图中所有的顶点图中所有的顶点,且使每个顶点仅被访且使每个顶点仅被访问一次问一次,就叫做图的遍历就叫做图的遍历.为了避免重复访问为了避免重复访问,可设置一个标志顶点是可设置一个标志顶点是否被访问过的辅助数组否被访问过的辅助数组visited,它的初始状态它的初始状态为为0.11