数据结构第讲图的定义与存储结构精品文稿.ppt

《数据结构第讲图的定义与存储结构精品文稿.ppt》由会员分享，可在线阅读，更多相关《数据结构第讲图的定义与存储结构精品文稿.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构第讲图的定义与存储结构第1 页，本讲稿共45 页课程先后关系如图：c1c9c4c2c12c10c11c5c3c6c7c8c1c9c4c2c12c10c5c3c6c7c8c11第2 页，本讲稿共45 页第7章 图7.1 图的定义和术语7.2 图的存储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及其应用7.6 最短路径第3 页，本讲稿共45 页7.1 图的定义和术语1.基本术语(1)顶点 图中的数据元素通常称为顶点。V是顶点的有穷非空集合；VR是两个顶点之间的关系的集合。(2)有向图 若称 VR表示从v到w的一条弧，且称v为弧尾或初始点，称w为弧头或终端结点，则该图称为有向

2、图。第4 页，本讲稿共45 页(3)无向图 若VR，必有VR，即VR是对称的，则以无序对（v,w)代替这两个有序对，表示v和w之间的一条边，则该图称为无向图。第5 页，本讲稿共45 页(4)权/网 有时图的边或弧具有与它相关的数，这些数称为权值（通常表示顶点间的距离或耗费），则带权值的图称为网。(5)子图 假设有两个图 G=（V，VR）和 G=（V，VR），若 V 是 V 的子集，且 VR 是 VR 的子集，则称 G 为 G 的子图。第6 页，本讲稿共45 页G1的子图G2的子图第7 页，本讲稿共45 页(6)完全图 假设用 n 表示图中顶点的数目，用 e 表示边或弧的数目。忽略自身弧/边，即

3、若vi,vj VR，则 vivj。对于无向图，有(n(n-1)/2 条边的无向图称为完全图。对于有向图，有 n(n-1)条弧的有向图称为有向完全图。(7)稀疏图/稠密图 边或弧很少（如enlogn）的图称稀疏图，反之称稠密图。第8 页，本讲稿共45 页(8)邻接点 对于无向图G=(V,E)，若边(v,v)E，则称顶点 v 和 v 互为邻接点，即 v 和 v 相邻接。或称边（v,v）依附于顶点v 和 v，或称（v,v）和顶点 v 和 v 相关联。对于有向图G=(V，E)，若弧 E，则称顶点 v 邻接到顶点 v，或称顶点 v 邻接自顶点 v，或弧和顶点 v，v 相关联。(a)(b)第9 页，本讲稿

4、共45 页顶点的入度/出度 以顶点 v 为头的弧的数目称 v 的入度，记为ID(v)；以顶点 v 为尾的弧的数目称 v 的出度，记为 OD(v)。顶点 v 的度 TD（v）=ID（v）OD（v）(9)顶点v的度(Degree)是和v相关联的边的数目，记为 TD（v）。(a)(b)第10 页，本讲稿共45 页(10)路径(Path)无向图G=(V,E)中，从顶点v到v的路径是顶点序列(v=vi0,vi1,vim=v)，其中(vij-1,vij)E，1jm。若G是有向图，则路径也是有向的，顶点序列应满足：E，1jm。路径的长度是路径上的边或弧的数目。第11 页，本讲稿共45 页(11)回路/环/简

5、单路径 第一个顶点和最后一个顶点相同的路径称为回路/环。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。第12 页，本讲稿共45 页(12)连通图/连通分量 在无向图G中，如果从顶点 V 到顶点 V 有路径，则称 V 和 V 是连通的。若图中任意两个顶点 vi、vjV，vi 和 vj 都是连通的，则称 G 是连通图。无向图中的极大连通子图称之为连通分量。第13 页，本讲稿共45 页左图：连通图下图：非连通图，但有 三个连通分量第14 页，本讲稿共45 页(13)强连通图/强连通分量 在有向图 G 中，若对于每一对vi、v

6、jV，vivj，从 vi 到 vj 和从 vj 到 vi 都存在路径，则称 G 是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。第15 页，本讲稿共45 页非强连通图 两个强连通分量第16 页，本讲稿共45 页 一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。如果在一棵生成树上添加一条边，必定构成一个环，因为这条边使得它依附的那两个顶点之间有了第二条路径。(14)生成树第17 页，本讲稿共45 页 如果一个有向图恰有一个顶点的入度为 0，其余顶点的入度均为 1，则是一棵有向树。一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只

7、有足以构成若干棵不相交的有向树的弧。(15)生成森林第18 页，本讲稿共45 页2.图的抽象类型定义ADT Graph 数据对象V：V是具有相同特性的数据元素的集 合，称为顶点集。数据关系R：R=VR VR=|v,wV且P(v,w)，表示从v到w的弧，谓词P(v,w)定义了 弧的意义或信息 基本操作P：ADT Graph第19 页，本讲稿共45 页基本操作CreateGraph(&G,V,VR);/按V和VR的定义构造图GDestroyGraph(&G);/销毁图GLocateVex(G,u);/若G中存在顶点u，则返回该顶点/在图中位置；否则返回其它信息GetVex(G,v);/返回 v 的

8、值PutVex(&G,v,value);/对 v 赋值valueFirstAdjVex(G,v);/返回v的第一个邻接点。/若v在G中没有邻接点，则返回“空”第20 页，本讲稿共45 页NextAdjVex(G,v,w);/返回v的(相对于w的)下一/个邻接点。若w是v的最后一个邻接点，则“空”InsertVex(&G,v);/在图G中增添新顶点v。DeleteVex(&G,v);/删除G中顶点v及其相关的弧InsertArc(&G,v,w);/在G中增添弧，若G/是无向的，则还增添对称弧DeleteArc(&G,v,w);/在G中删除弧，若G/是无向的，则还删除对称弧第21 页，本讲稿共45

9、 页DFSTraverse(G,v,Visit();/从顶点v起深度优先遍历图G，并对每个顶点调用/函数 Visit一次且仅一次。BFSTraverse(G,v,Visit();/从顶点v起广度优先遍历图G，并对每个顶点调用/函数 Visit一次且仅一次。第22 页，本讲稿共45 页第7章 图7.1 图的定义和术语7.2 图的存储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及其应用7.6 最短路径第23 页，本讲稿共45 页7.2 图的存储结构n 图的数组(邻接矩阵)存储表示n 图的邻接表存储表示n 有向图的十字链表存储表示n 无向图的邻接多重表存储表示第24 页，本讲稿共45

10、 页1.图的数组(邻接矩阵)存储表示 邻接矩阵是用于描述图中顶点之间关系(即弧或边的权)的矩阵。假设图中顶点数为n，则邻接矩阵Ann：1 若Vi和Vj之间有弧或边 Aij=0 反之第25 页，本讲稿共45 页 CADB CABDCBAA=0 1 1 11 0 1 11 1 0 11 1 1 0A B C DA B C CBAB=0 1 01 0 01 1 0第26 页，本讲稿共45 页注意：1)图中无邻接到自身的弧，因此邻接矩阵主对角线为全零。2)无向图的邻接矩阵必然是对称矩阵。3)无向图中，顶点的度是邻接矩阵对应行（或列）的非零元素之和；有向图中，对应行的非零元素之和是该顶点的出度；对应列的

11、非零元素之和是该顶点的入度；则该顶点的度是对应行和对应列的非零元素之和。第27 页，本讲稿共45 页V1V2V3V4V5V65485931567网的邻接矩阵 反之权值 若Vi和Vj之间有弧或边Aij=第28 页，本讲稿共45 页图的数组（邻接矩阵）存储表示#define INFINITY INT_MAX/最大值#define MAX_VERTEX_NUM 20/最大顶点个数typedef enum DG,DN,UDG,UDN GraphKind;/图类型（有向图/网,无向图/网）typedef struct ArcCell VRType adj;/VRType是顶点关系类型。对无权图，用1或0

12、 表示相邻否；对带权图，则为权值类型。InfoType*info;/指向该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM;/描述顶点的数组 AdjMatrix arcs;/邻接矩阵 int vexnum,arcnum;/图的当前顶点数和弧(边)数 GraphKind kind;/图的种类标志 MGraph;第29 页，本讲稿共45 页构造图的算法 Status CreateGraph(Mgraph&G)/采用数组(邻接矩阵)表示法，构造图G。s

13、canf(&G.kind)；switch(G.kind)case DG：return CreateDG(G)；/构造有向图G case DN：return CreateDN(G)；/构造有向网G case UDG：return CreateUDG(G)；/构造无向图Gcase UDN：return CreateUDN(G)；/构造无向网Gdefault：return ERROR；/CreateGraph第30 页，本讲稿共45 页采用数组表示法，构造无向网GStatus CreateUDN(MGraph&G)sacnf(&G.vexnum,&G.arcnum,&IncInfo);for(i=0

14、;iG.vexnum;+i)scanf(&G.vexsi);/构造顶点向量for(i=0；iG.vexnum；+i)/初始化邻接矩阵 for(j=0;jG.vexnum;+j)G.arcsij=INFINITY,NULL;/adj,infofor(k=0；kG.arcnum；+k)/构造邻接矩阵 scanf(&v1，&v2，&w)；/输入一条边依附的顶点及权值 i=LocateVex(G,v1);j=LocateVex(G,v2);/v1和v2在G中位置 G.arcsij.adj=w；/弧的权值 if(IncInfo)Input(*G.arcsij.info);G.arcsji=G.arcsi

15、j;/置的对称弧 return OK;/CreateUDN 第31 页，本讲稿共45 页2.图的邻接表存储表示 类似树的孩子链表。即对图中的每个顶点vi建立一个单链表，表中结点表示依附于该顶点vi的边或弧。邻接点域 链域 数据域指示与顶点vi邻接的点在图中的位置指示下一条边或弧的结点存储和边或弧相关的信息数据域 链域指向链表第一个结点存储顶点vi和其他有关信息表结点表头结点第32 页，本讲稿共45 页V1V3V2V4V1V3V2V4例如：1 3 4 4 3 2 1 4 4 3 2 121 113 4 4 2第33 页，本讲稿共45 页注意：在无向图的邻接表中，1）第i个链表中结点数目为顶点i的

16、度；2）所有链表中结点数目的一半为图中边数；3）占用的存储单元数目为n+2e。在有向图的邻接表中，1）第i个链表中结点数目为顶点i的出度；2）所有链表中结点数目为图中弧数；3）占用的存储单元数目为n+e。第34 页，本讲稿共45 页 为求出每一个顶点的入度，必须另外建立有向图的逆邻接表。有向图的逆邻接表与邻接表类似，只是它是从入度考虑结点，而不是从出度考虑结点。2 4 4 3 2 1 1 逆邻接表 3V1V3V2V4第35 页，本讲稿共45 页图的邻接表存储表示#define MAX_VERTEX_NUM 20typedef struct ArcNode int adjvex;/该弧所指向的顶

17、点的位置 struct ArcNode*nextarc;/指向下一条弧的指针 InfoType*info;/该弧相关信息的指针 ArcNode;typedef struct VNode VertexType data;/顶点信息 ArcNode*firstarc;/指向第一条依附该顶点的弧 VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数 int kind;/图的种类标志 ALGraph;第36 页，本讲稿共45 页3.有向图的十字链表存储表示 十字链表是有向图的另

18、一种链式存储结构。可以理解成有向图的邻接表和逆邻接表的结合，在十字链表中，有两种结点结构：尾域tailvex头域headvex链域hlink链域tlink信息域info数据域data链域firstin链域firstout顶点结点弧结点第37 页，本讲稿共45 页尾域tv 指示弧尾顶点在图中的位置头域hv 指示弧头顶点在图中的位置链域h 指向弧头相同的下一条弧链域t 指向弧尾相同的下一条弧信息域 指向该弧的相关信息尾域tailvex头域headvex链域hlink链域tlink信息域info数据域data链域firstin链域firstout数据域 存储和顶点相关信息链域fin 指向以该顶点为弧

19、头的第一个弧结点链域fout 指向以该顶点为弧尾的第一个弧结点第38 页，本讲稿共45 页v1v2v3v4 0 1 2 3 1 0/2 0v3v1 v4v2/0 3/1 3/2 30 2/3 2例：data firstin firstouttailvexheadvex hlinktlink/第39 页，本讲稿共45 页有向图的十字链表存储表示#define MAX_VERTEX_NUM 20typedef struct ArcBox int tailvex,headvex;/该弧的尾和头顶点的位置 struct ArcBox*hlink,*tlink;/分别指向下一个弧头相同 和弧尾相同的弧的

20、指针域 InfoType*info;/该弧相关信息的指针 ArcBox;typedef struct VexNode VertexType data;ArcBox*firstin,*firstout;/分别指向该顶点第一条入弧 和出弧 VexNode;typedef struct VexNode xlistMAX_VERTEX_NUM;/表头向量 int vexnum,arcnum;/有向图的当前顶点数和弧数 OLGraph;第40 页，本讲稿共45 页4.无向图的邻接多重表存储表示 在无向图的邻接表中，每条边（Vi，Vj）由两个结点表示，一个结点在第 i 个链表中，另一个结点在第 j 个链表

21、中，当需要对边进行操作时，就需找到表示同一条边的两个结点，这给操作带来不便，在这种情况下采用邻接多重表较方便。邻接多重表中结点分为：边结点和顶点结点第41 页，本讲稿共45 页标志域 用于标记该边是否被搜索过边顶点i 该边依附的顶点vi在图中的位置边顶点j 该边依附的顶点vj在图中的位置链域i 指向下一条依附于顶点vi的边链域j 指向下一条依附于顶点vj的边信息域指向和边相关的各种信息的指针域数据域 存储和该顶点相关的信息边链域指示第一条依附于该顶点的边标志域 边顶点i 边顶点j 链域i 链域j 信息域数据域 边链域第42 页，本讲稿共45 页1 3 4 2 例12341 21 32 4第43

22、 页，本讲稿共45 页无向图的邻接多重表存储表示#define MAX_VERTEX_NUM 20typedef emnu unvisited,visited VisitIf;typedef struct Ebox VisitIf mark;/访问标记 int ivex,jvex;/该边依附的两个顶点的位置 struct EBox*ilink,*jlink;/分别指向依附这两个顶点的 下一条边 InfoType*info;/该边信息指针 EBox;typedef struct VexBox VertexType data;EBox*firstedge;/指向第一条依附该顶点的边VexBoxtypedef struct VexBox adjmulistMAX_VERTEX_NUM;int vexnum,edgenum;/无向图的当前顶点数和边数 AMLGraph;第44 页，本讲稿共45 页1.理解图的定义，掌握图的常用术语；2.掌握常见的图的存储结构，以及各种存储结构的特点，在应用时可以根据对图的操作需要加以选取。作业P47：7.1、7.15小结第45 页，本讲稿共45 页