《数据结构(第7章)图》由会员分享，可在线阅读，更多相关《数据结构(第7章)图（119页珍藏版）》请在金锄头文库上搜索。
1、第七章 图,计算机与信息技术学院,2018/9/2,数据结构 page 2,信阳师范学院计算机与信息技术学院,第七章 图,2018/9/2,数据结构 page 3,信阳师范学院计算机与信息技术学院,7.1 基本术语,图是顶点集和边集组成的二元组G=,E中每条边是V中一对顶点(u,v)间的联系,如果是无序对，那么称该图为无向图，否则为有向图。 邻接点：边的两个顶点互为邻接点 关联边：若有边e= (v, u), 则称顶点v、u关联边e,2018/9/2,数据结构 page 4,信阳师范学院计算机与信息技术学院,顶点V的度 = 与V相关联的边的数目在有向图中： 顶点V的出度 = 以V为起点有向边数顶
2、点V的入度 = 以V为终点有向边数顶点V的度 = V的出度+V的入度设图G的顶点数为n，边数为e图的所有顶点的度数之和 = 2*e（每条边对图的所有顶点的度数和“贡献”2度）,顶点的度、入度和出度,2018/9/2,数据结构 page 5,信阳师范学院计算机与信息技术学院,在图G=中，若有顶点序列v1,v2, ,vk,且E(有向图)或(vi,vi+1)E(无向图)，其中i=1,2,k-1,v=v1,u=vk,则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路。,路径、回路,2018/9/2,数据结构 page 6,信阳师范学院计算机与信息技术学院,简单路径、简单回路 在一条路径中,
3、 除起点和终点外,若其余顶点各不相同,则称该路径为简单路径。 由简单路径组成的回路称为简单回路。 例如在上面的无向图中，V0,V1,V2,V3是简单路径V0,V1,V2,V4,V1不是简单路径；在下面的有向图中，V0,V2,V3,V0是简单回路。,2018/9/2,数据结构 page 7,信阳师范学院计算机与信息技术学院,连通图、强连通图在无（有）向图G=中，若对任何两个顶点u、v都存在从u到v的路径，则称G是连通图(强连通图)。,(b)非连通图,(c)强连通图,(a)连通图,V0,V3,V2,V1,V4,V5,(d)非强连通图,2018/9/2,数据结构 page 8,信阳师范学院计算机与信
4、息技术学院,连通分量、强连通图分量无（有）向图的极大连通子图称为其(强)连通分量。,非连通图，有两个连通分量,非强连通图,有两个强连通分量,2018/9/2,数据结构 page 9,信阳师范学院计算机与信息技术学院,生成树 一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。,(a)连通图G1,(b)连通图G1的一个生成树,2018/9/2,数据结构 page 10,信阳师范学院计算机与信息技术学院,如果在一棵生成树上添加一条边，必定构成一个环。 一棵有n个顶点的生成树有且仅有n-1条边。 如果一个图有n个顶点和小于n-1条边，则是非连通图。 如果一个图
5、有n个顶点和多于n-1条边，则一定有环。 有n-1条边的图不一定是生成树。 生成树可能不惟一。,生成树的有关性质,2018/9/2,数据结构 page 11,信阳师范学院计算机与信息技术学院,无向图及其生成树,无向图G,2018/9/2,数据结构 page 12,信阳师范学院计算机与信息技术学院,赋权图,2018/9/2,数据结构 page 13,信阳师范学院计算机与信息技术学院,有向图的强连通子图,1,3,2,4,15,2,20,5,4,6,2018/9/2,数据结构 page 14,信阳师范学院计算机与信息技术学院,例1 交通图（公路、铁路） 顶点：地点 边：连接地点的公路 交通图中的单行
6、道双行道，分别用有向边、无向边表示,图的应用示例,例2 电路图 顶点：元件 边：连接元件之间的线路,例3 通讯线路图 顶点：地点 边：地点间的连线,例4 各种流程图 如产品的生产流程图 顶点：工序 边：各道工序之间的顺序关系,2018/9/2,数据结构 page 15,信阳师范学院计算机与信息技术学院,7.2 图的存储结构,图的存储结构至少要保存两类信息：1)顶点的数据2)顶点间的关系,约定:G=是图, V=v0,v1,v2, vn-1 ,设顶点的角标为它的编号,2018/9/2,数据结构 page 16,信阳师范学院计算机与信息技术学院,7.2.1 图的数组表示法,在数组表示法中， 用邻接矩
7、阵表示顶点间的关系,2018/9/2,数据结构 page 17,信阳师范学院计算机与信息技术学院,注：用两个数组分别存储顶点表和邻接矩阵 #define INFINITY INT_MAX /最大值 #define MAX_VERTEX_NUM 20 /假设的最大顶点数 Typedef enum DG, DN, AG, AN GraphKind; /有向/无向图，有向/无向网,图的邻接矩阵表示法（参见教材P161）,Typedef struct ArcCell /弧（边）结点的定义VRType adj; /顶点间关系，无权图取1或0；有权图取权值InfoType *info; /该弧相关信息的指
8、针 ArcCell, AdjMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM ;,2018/9/2,数据结构 page 18,信阳师范学院计算机与信息技术学院,对于n个顶点的图或网，空间效率=O(n2),Typedef struct /图的定义 VertexType vexs MAX_VERTEX_NUM ; /顶点表，用一维向量即可(n) AdjMatrix arcs; /邻接矩阵n*n Int Vernum, arcnum; /顶点总数n，弧（边）总数e GraphKind kind; /图的种类标志 MGraph;,2018/9/2,数据结构 page 19,信阳
9、师范学院计算机与信息技术学院,Status CreateUDN(Mgraph /输入n个顶点值，存入一维向量,例：用邻接矩阵生成无向网的算法（参见教材P162）,for(i=0; iG.vexnum; +i) /对邻接矩阵n*n个单元初始化for(j=0;jG.vexnum;+j) G.arcsij=INFINITY, NULL;,2018/9/2,数据结构 page 20,信阳师范学院计算机与信息技术学院,对于n个顶点e条弧的网， 建网时间效率 = O(n+n2+e*n),for(k=0;kG.arcnum;+k) /给邻接矩阵有关单元赋初值(循环次数弧数escanf( /如果弧有信息则填入
10、G.arcsij = G.arcs j i； /无向网是对称矩阵,return OK; / CreateUDN,2018/9/2,数据结构 page 21,信阳师范学院计算机与信息技术学院,1）无向图的邻接矩阵是对称矩阵，同一条边表示了两次； 2）顶点v的度：等于二维数组对应行（或列）中值为1的元素个数； 3）判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否为1； 4）顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值1或清0；,数组表示法的特点（无向图）,2018/9/2,数据结构 page 22,信阳师范学院计算机与信息技术学院,5）设图的顶点数为 n ,用有n个元素的一维数
11、组存储图的顶点,用邻接矩阵表示边,则G占用的存储空间为：n+n2；图的存储空间占用量只与它的顶点数有关，与边数无关；适用于边稠密的图；,数组表示法的特点（无向图）,2018/9/2,数据结构 page 23,信阳师范学院计算机与信息技术学院,1) 有向图的邻接矩阵不一定是对称的； 2) 顶点v的出度：等于二维数组对应行中值为1的元素个数； 3）顶点v的入度：等于二维数组对应列中值为1的元素个数；,数组表示法的特点（有向图）,2018/9/2,数据结构 page 24,信阳师范学院计算机与信息技术学院,网的数组表示法,8,2,7,3,4,9,6,2,2,1,V3,2,V2,V4,V1,V6,V5
12、,2018/9/2,数据结构 page 25,信阳师范学院计算机与信息技术学院,7.2.2 图的邻接表存储结构,例,0,1,2,3,4,顶点：通常按编号顺序将顶点数据存储在一维数组中。 关联同一顶点的边：用线性链表存储,该结点表示边（V0,V1）,其中的1是V1的序号，即一维数组中的下标。,2018/9/2,数据结构 page 26,信阳师范学院计算机与信息技术学院,网的邻接链表表示,2018/9/2,数据结构 page 27,信阳师范学院计算机与信息技术学院,7.2.2 邻接表的类型定义,typedef struct VertexType data;ArcNode *firstarc; Ad
13、jListMaxVnum;,typedef struct ArcNodeint adjvex;double weight;struct ArcNode *nextarc; ArcNode;,2018/9/2,数据结构 page 28,信阳师范学院计算机与信息技术学院,7.2.2(续) 图的邻接表表示,typedef struct int vexnum,arcnum;AdjList vertices; AGraph;,2018/9/2,数据结构 page 29,信阳师范学院计算机与信息技术学院,有向图的邻接表表示,例,顶点：通常按编号顺序将顶点数据存储在一维数组中以同一顶点为起点的弧：用线性链表
14、存储,2018/9/2,数据结构 page 30,信阳师范学院计算机与信息技术学院,有向图的逆邻接表表示,例,顶点：通常按编号顺序将顶点数据存储在一维数组中。 以同一顶点为终点的弧：用线性链表存储。,7.2.3 有向图的十字链表表示,将有向图的邻接表和逆邻接表结合起来得到的链表。 在十字链表中，顶点结点存储数据元素，弧结点存储弧及其上的信息。,弧结点,2018/9/2,数据结构 page 32,信阳师范学院计算机与信息技术学院,v0,v1,v3,0,0,1,2,3,1,0,2,2,0,3,0,3,1,3,2,2,3,逆邻接链表,2018/9/2,数据结构 page 33,信阳师范学院计算机与信
15、息技术学院,v0,v1,v3,0,0,1,2,3,1,0,2,2,0,3,0,3,1,3,2,2,3,十字链表,2018/9/2,数据结构 page 34,信阳师范学院计算机与信息技术学院,7.2.4 无向图的邻接多重表表示,无向图的邻接多重表表示中，每条边只表示一次。,v0,v1,v2,v3,0,1,2,3,0,1,0,3,（v0,v1）,（v0,v3）,2,1,v3,4,2,3,4,1,4,2,2018/9/2,数据结构 page 35,信阳师范学院计算机与信息技术学院,v0,v1,v2,v3,0,1,2,3,0,1,0,3,（v0,v1）,（v0,v3）,2,1,v4,4,2,3,4,1,4,2,2018/9/2,数据结构 page 36,信阳师范学院计算机与信息技术学院,7.3 图的遍历,从图的某个顶点出发，访问图中的所有顶点，且使每个顶点仅被访问一次。这一过程叫做图的遍历。图的遍历操作是求解图的连通性问题、拓扑排序等问题的基础。遍历方法:深度优先遍历和广度优先遍历,
