《图课件》由会员分享，可在线阅读，更多相关《图课件（113页珍藏版）》请在金锄头文库上搜索。
1、图的定义和术语图的存储结构图的遍历图的连通性问题有向无环图及其应用最短路径,第七章 图,7.1 图的定义和术语,一 、图的定义,本章介绍另一种非线性数据结构 图, 主要学习图的存储结构以及若干图的操作的实现。,图是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继。,图G由两个集合构成，记作G= (V, A) 其中V是顶点的非空有限集合， A 是边的有限集合，其中边是顶点的无序对或有序对(此时的图称为无向图或有向图)。,无向图G1=(V1, A1)， V1= v0 ,v1 ,v2 ,v3 ,v4 ， A1= (v0,v1) , (v0,v3) , (v1,v2) , (
2、v1,v4) , (v2,v3) , (v2,v4) ,无序对(vi ,vj)： 用连接顶点vi、vj的线段 表示，称为无向边；,有序对 ： 用以为vi起点(弧尾)、以vj为终点(弧头) 的有向线段表示，称为有向边或弧；,有向图G2=(V2, A2)， V2=v0 v1,v2,v3 ， A2= , , , ,完全图,有向完全图,稀疏图,权 网,稠密图,边,弧,有很少条边或弧的图,例1 交通图（公路、铁路） 顶点：地点边：连接地点的路交通图中的有单行道、双行道，分别用有向边、无向边表示； 例2 电路图 顶点：元件边：连接元件之间的线路 例3 通讯线路图 顶点：地点边：地点间的连线 例4 各种流程
3、图(如生产流程图) 顶点：工序边：各道工序之间的顺序关系,图的实例,ADT Graph数据对象V : V是具有相同特性的数据元素的集合，称为顶点集。,ADT 图 的 定 义,基本操作 :,CreateGraph(&G , V, VR ) / 按定义构造图初始条件:V是图的顶点集, VR 是图中弧的集合。 操作结果:按V和VR的定义构造图G 。,数据关系R : R=VRVR =v ,w V ，且p(v ,w ) , 表示从v到w 的弧，谓词p(v ,w )定义了弧的意义或信息。,DestroyGraph (&G ) / 销毁初始条件:图G存在。 操作结果:销毁图G 。,LocateVex(G,
4、u) / 定位初始条件:图G存在，u 和G中顶点有相同特性 。 操作结果: 若G中存在顶点u ，则返回该顶点在图中位置 ；否则返回其它信息。,GetVex(G, v)/ 求值初始条件:图G存在，v 是G中某个顶点。 操作结果:返回v的值。,PutVex(&G, v, value) / 赋值初始条件:图G存在，v 是G中某个顶点。 操作结果:对 v 赋值value。,FirstAdjVex(G, v) / 求第一个邻接点初始条件:图G存在，v 是G中某个顶点。 操作结果:返回 v 的第一个邻接点。若顶点v 在 G 中没有邻接顶点，则返回“空” 。,NextAdjVex(G, v, w) / 求下
5、一个邻接点初始条件:图G存在，v 是G中某个顶点， w 是 v 的邻接点 。 操作结果: 返回 v 的（相对于 w 的）下一个邻接点。若 w 是 v 的最后一个邻接点，则返回“空”。,InsertVex( / 插入顶点初始条件:图G存在，v和G中顶点有相同特性 。 操作结果: 在图G中增添新顶点v。,DeleteVex(&G, v) /删除顶点初始条件: 图G存在， v和G中顶点有相同特性 。 操作结果:删除G中顶点v及其相关的弧。,InsertArc(&G, v, w) /插入弧初始条件:图G存在，v 和w是G中两个顶点。 操作结果:在G中增添弧，若G是无向的， 则还增添对称弧。,Delet
6、eArc(&G, v, w) /删除弧初始条件:图G存在，v 和w是G中两个顶点。 操作结果:在G中删除弧，若G是无向的，则还删除对称弧。,DFSTraverse(G, v, Visit() /深度优先遍历初始条件:图G存在，v 是G中某个顶点，Visit是顶点的应用函数 。 操作结果: 从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。一旦Visit（）失败，则操作失败。,BFSTraverse(G, v, Visit() /广度优先遍历初始条件:图G存在，v 是G中某个顶点，Visit是顶点的应用函数 。 操作结果: 从顶点v起广度优先遍历图G，并对每个顶点调用函数V
7、isit一次且仅一次。一旦Visit（）失败，则操作失败。,2 顶点的度、入度、出度顶点v的度 TD(v)= 与v相关联的边的数目。在有向图中：顶点v的出度OD(v) =以v为起点有向边数；顶点v的入度ID(v) =以v为终点有向边数；TD(v) = OD(v) + ID(v),二、图的基本术语,1 邻接点及关联边 邻接点：边的两个顶点；关联边：若边e= (v, u), 则称边e与顶点v和u 相关联；,设图G的顶点数为n，边数为e 则图的所有顶点的度数之和 = 2*e （每条边对图的所有顶点的度数之和 “贡献” 2度）,路径、回路(环) 无向图G1=（V1，E1）中的顶点序列v1,v2, ,v
8、k,若(vi,vi+1)E1 ( i=1,2,k-1), v =v1, u =vk, 则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路；在G1中，v0,v1,v2,v3 是v0到v3的路径；v0,v1,v2,v3 , v0是回路； 有向图G2=（V2，E2）中的顶点序列v1,v2, ,vk, E2 (i=1,2,k-1),若v =v1, u =vk,则称该 序列是从顶点v到顶点u的路径；若v=u，则称该序 列为回路；在G2中， v0, v2, v3是v0到v3的路径 v0,v2,v3,v0是回路；,简单路径和简单回路在一条路径中,若所有顶点各不相同,则称该路径为简单路径；若除起点
9、和终点外,其余顶点各不相同的回路称为简单回路。,例,在图G1中，V0,V1,V2,V3 是简单路径；V0,V1,V2,V4,V1不是简单路径；,在图G2中，V0,V2,V3,V0是简单回路；,连通图（强连通图）在无（有）向图G=( V, E )中，若对任何两个顶点 v、u 都存在从v 到 u 的路径，则称G是连通图（强连通图）,非连通图,连通图,强连通图,非强连通图,设有两个图G=（V，E）、G1= （V1，E1）， 若V1 V，E1 E，E1关联的顶点都在V1中， 则称 G1是G的子图；,(a),(b),(c),5 子图,例 下列 (b)、(c) 是 (a) 的子图,(强)连通分量无向图G的
10、极大连通子图称为G的连通分量。极大连通子图意思是：该子图是 G 的连通子图，将G 的任何不在该子图中的顶点加入，子图不再连通；,非连通图,非连通分量,把顶点V3加入，子图还连通,有向图D 的极大强连通子图称为D 的强连通分量。极大强连通子图意思是：该子图是D强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。,V1,非强连通图,7 生成树包含无向图G 所有顶点的极小连通子图称为G 的生成树。极小连通子图意思是：该子图是G 的连通子图，在该子图中删除任何一条边，子图不再连通。,G的生成树,一棵n个顶点的生成树有且仅有足以构成树的n-1条边。,说明：,若在一棵生成树上删除一条边，就不
11、再连通。,若在一棵生成树上添加一条边，必定构成一个环。,不再连通,构成环,7.2 图的存储结构,由于图中任意两个顶点之间都可能存在联系，因此难以以数据元素在存储区中物理位置表示它们间的关系，仍可以借助数组表示之。另一方面，也可以用多重链表表示图。但由于图中顶点的度可能相差悬殊，会因此造成空间的浪费；反之，若按每个顶点的度设计不同的结点结构，又会造成操作上的不便。应根据具体的图和需要，设计恰当的结点结构和表结构。,图的存储结构至少要保存两类信息： 1)顶点的数据； 2)顶点间的关系。,如何表示顶点间的关系？,？,常用图的存储表示,一、图的数组(邻接矩阵)存储表示,二、图的邻接表存储表示,三、有向
12、图的十字链表存储表示,四、无向图的邻接多重表存储表示,邻接矩阵：图G的邻接矩阵是满足如下条件的n阶矩阵：,7.2.1 数组表示法(邻接矩阵表示),在数组表示法中， 用邻接矩阵表示顶点间的关系,网的邻接矩阵,typedef struct ArcCell / 弧的定义VRType adj;/VRType是顶点关系类型。对无权图，/用1或0表示相邻否；对带权图，则为权值类型。InfoType *info; / 该弧相关信息的指针 ArcCell , AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;,/ 图的数组(邻接矩阵)存储表示,#define INFINITY IN
13、T_MAX /最大值 #define MAX_VERTEX_NUM 20/最大顶点个数 typedef enumDG,DN,UDG, UDN graphkind；/有向图，有向网，无向图，无向网,typedef struct /图的定义VertexType vexsMAX_VERTEX_NUM; /顶点向量保存顶点数据AdjMatrix arcs; /邻接矩阵保存顶点间关系int vexnum, arcnum; /顶点数，弧数 GraphKind kind; /图的种类标志 MGraph;,无向图数组表示法特点： 1）无向图邻接矩阵是对称矩阵，同一条边表示了两次；,对有向图的数组表示法 可做类
14、似的讨论,2）顶点v的度：等于二维数组对应行（或列）中1的个数；,3）判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否非零；,4）顶点不变，在图中增加、删除边：只需对二维数组对应分量赋非零值或清零；,5）用二维数组存储顶点数为 n的图, 占用存储空间只与它的顶点数n有关，与边数e无关。适用于边稠密的图。,Status GreateUDN(MGraph /CreateUDN,算法7.2,3,4,5,9,2,7,图的基本操作,int LocateVex(MGraph G, VertexType u) / 初始条件:图G存在,u和G中顶点有相同特征/ 操作结果:若G中存在顶点u,则返回该顶点
15、在图中位置;否则返回-1int i;for(i=0;iG.vexnum;+i)if(strcmp(u,G.vexsi)=0)return i;return -1;,strcmp是比较两个字符串的大小,两个字符串相同时返回0,第一个字符串大于第二个字符串时返回一个正值,否则返回负值.,图的基本操作的实现(采用数组表示法)： 1）求无向图某顶点vi的度：(或有向图vi的出度) Ai0 到Ain-1中的非零个数，即数组A第i行的非零元素的个数；,2）求有向图某顶点vi 的 入度：A0i到An-1i 中的非零个数，即数组A中第i列的非零元素的个数；,3）求图中的总边数：扫描整个数组A，统计出数组中非零元素的个数。无向图的总边数为非零元素个数的一半，而有向图的总弧数为非零元素个数。,例,下标顶点头指针 编号,1 无向图的邻接表顶点通常按编号顺序将顶点数据存储在一维数组中；关联同一顶点的边用线性链表存储。,7.2.2 邻接表,该结点表示边（V4, Vj）,其中的j是Vj在一维数组中的位置,可见，在有向图的邻接表中不易找到指向该顶点的弧。,1,2 有向图的邻接表,4,0,3,3,
