《数据结构(第七章 图)》由会员分享，可在线阅读，更多相关《数据结构(第七章 图)（174页珍藏版）》请在金锄头文库上搜索。
1、数 据 结 构,第 7 章 图,主要内容,7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径,7.1 图的定义和术语,图(Graph)图G是由两个集合V(G)和E(G)组成的,记为G=(V,E) 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对。 有向图有向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为，v,w是顶点，v为弧尾，w为弧头 无向图无向图G是由两个集合V(G)和E(G)组成的 其
2、中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对，记为 （v,w）或（w,v)，并且（v,w)=(w,v),(u,v) ,V=Vertex E=Edge,7.1 图的定义和术语,有向图G1=（V，E）中：V(G1)=1,2,3,4,5,6 E(G1)=, , , , , , ,无向图G2=（V，E）中：V(G2)=1,2,3,4,5,6,7 E(G2)=(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7),图的示例,7.1 图的定义和术语,有向完全图有n(n-1)条弧的n个顶点的有向图 无向完全图有n(n-1)/2条边的n个顶点的无向图 稀
3、疏图-若边或弧的个数 enlogn，则称作稀疏图，否则成稠密图。 权把图的边或弧赋予一个有意义的数，此数叫权 带权图-网弧或边带权的图分别称作有向网或无向网。 子图如果图G(V,E)和图G(V,E),满足： VV 且 EE， 则称G为G的子图 邻接点若无向图G中存在（V,W）,则称V,W互为邻接点； 边（V，W）和顶点V,W相关联。 顶点的度 无向图中，顶点的度为与该顶点相连的边数 有向图中，顶点的度分成入度与出度 入度：以该顶点为弧头的弧的数目 出度：以该顶点为弧尾的弧的数目,7.1 图的定义和术语,证明：, 完全有向图有n(n-1)条边。 证明：若是完全有向图，则顶点1必与所有其他顶点各有
4、2条连线，即有2(n-1)条边， 顶点2有2(n-2)条边，顶点n-1有2条边,顶点n有0条边. 总边数2( n-1 n-210)=2(n-1+0)n/2= n(n-1), 完全无向图有n(n-1)/2 条边。 证明：若是完全无向图，则顶点1必与所有其他顶点各有1条连线，即有n-1条边，顶点2有n-2条边，顶点n-1有1条边,顶点n有0条边. 总边数 n-1 n-210=（n-1+0)n/2= n(n-1)/2,7.1 图的定义和术语,有向网（弧带权值）,有向图顶点的度(TD) =出度(OD)+入度(ID),7.1 图的定义和术语,无向图,无向图(树),有向图,有向图,n(n-1)/2 条边,
5、n(n-1) 条边,G1的顶点集合为V(G1)=0,1,2,3 边集合为E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3),完全图,完全图,图的练习 ：判断下列4种图形各属什么类型？,7.1 图的定义和术语,简单路径：,路径上各顶点 v1,v2,.,vm 均不互相重复。,回路：,若路径上第一个顶点 v1 与最后一个顶点vm 重合，则称这样的路径为回路或环。,路径：,在图 G(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, , vpm，到达顶点vj。则称顶点序列 ( vi vp1 vp2 . vpm vj ) 为从顶点vi 到顶
6、点 vj 的路径。它经过的边(vi, vp1)、(vp1, vp2)、.、(vpm, vj)应当是属于E的边。,路径长度：,非带权图的路径长度是指此路径上边的条数； 带权图的路径长度是指路径上各边的权之和。,简单回路：图的顶点序列中，除了第一个顶点和最后一个顶点相同外，其余顶点不重复出现的回路叫简单回路。,7.1 图的定义和术语,路径13：1,2,3 |（ 1，2，3，5，6，3 ） 路径长度：2 (5) 简单路径：1，2，3，5 回路：1，2，3，5，6，3，1 简单回路：3，5，6，3,路径：1，2，5，7，6，5，2，3 路径长度：7 简单路径：1，2，5，7，6 回路：1，2，5，7，
7、6，5，2，1 简单回路：1，2，3，1,7.1 图的定义和术语,连通图,强连通图,在无向图中, 若从顶点vi到顶点vj有路径, 则称顶点vi与vj是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。 非连通图的极大连通子图叫做连通分量。,在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。 非强连通图的极大强连通子图叫做强连通分量。,7,7.1 图的定义和术语,假设一个（无向）连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。,对非连通图，则称由各个连
8、通分量的生成树的集合为此非连通图的生成森林。,生成树,7.1 图的定义和术语,图的基本操作,结构的建立和销毁,插入或删除顶点,对邻接点的操作,对顶点的访问操作,遍历,插入和删除弧,7.1 图的定义和术语,图的基本操作,CreatGraph(&G, V, VR): / 按定义(V, VR) 构造图,DestroyGraph(&G): / 销毁图,结构的建立和销毁,7.1 图的定义和术语,图的基本操作,对顶点的访问操作,LocateVex(G, u); / 若G中存在顶点u，则返回该顶点在 / 图中“位置”;否则返回其它信息。,GetVex(G, v); / 返回 v 的值。,PutVex( /
9、对 v 赋值value。,7.1 图的定义和术语,图的基本操作,对邻接点的操作,FirstAdjVex(G, v); / 返回 v 的“第一个邻接点” 。若该顶点 /在 G 中没有邻接点，则返回“空”。,NextAdjVex(G, v, w); / 返回 v 的（相对于 w 的） “下一个邻接 / 点”。若 w 是 v 的最后一个邻接点，则 / 返回“空”。,7.1 图的定义和术语,图的基本操作,插入或删除顶点,InsertVex( /在图G中增添新顶点v。,DeleteVex( / 删除G中顶点v及其相关的弧。,7.1 图的定义和术语,图的基本操作,插入和删除弧,InsertArc( / 在
10、G中增添弧，若G是无向的， /则还增添对称弧(w,v)。,DeleteArc( /在G中删除弧，若G是无向的， /则还删除对称弧(w,v)。,7.1 图的定义和术语,图的基本操作,遍 历,DFSTraverse(G, v, Visit(); /从顶点v起深度优先遍历图G，并对每 /个顶点调用函数Visit一次且仅一次。,BFSTraverse(G, v, Visit(); /从顶点v起广度优先遍历图G，并对每 /个顶点调用函数Visit一次且仅一次。,7.2 图的存储结构,一、图的数组(邻接矩阵)存储表示,二、图的邻接表存储表示,三、有向图的十字链表存储表示,四、无向图的邻接多重表存储表示,7
11、.2 图的存储结构,图的数组存储表示,用两个数组分别存储顶点信息和顶点之间的关系信息(邻接矩阵表示顶点间相邻关系的矩阵) 定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A（二维数组）是具有以下性质的n阶方阵：,7.2 图的存储结构,图的数组存储表示,邻接矩阵特点： 无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2 有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n 无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和 (第i行非0元素1的个数) 有向图中， 顶点Vi的出度是A中第i行元素之和 顶点Vi的入度是A中第i列元素之和,7.2 图
12、的存储结构,图的数组存储表示,网的邻接矩阵示意图,网的邻接矩阵可定义为：, 反之,容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。 n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。 对稀疏图而言尤其浪费空间。,邻接矩阵法优点：,邻接矩阵法缺点：,typedef struct ArcCell / 弧的定义 VRType adj; / VRType是顶点关系类型, /对无权图， 用1或0表示相邻否；对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell , AdjMatrix MAX_VERTEX_NUMMA
13、X_VERTEX_NUM;,#define INFINITY INT_MAX /定义无穷大 #define MAX_VERTEX_NUM 20 / 定义图的类型 有向图, 有向网,无向图, 无向网 typedef enum DG, DN, UDG, UDN GraphKind;,typedef struct / 图的定义 VertexType vexsMAX_VERTEX_NUM; / 顶点数组 AdjMatrix arcs; /邻接矩阵，可设二维 int vexnum, arcnum; / 顶点数，弧数 GraphKind kind; / 图的种类标志 MGraph;,7.2 图的存储结构,
14、图的数组（邻接矩阵）存储表示实现,7.2 图的存储结构,图的数组（邻接矩阵）存储表示实现,G1.vexs=1，2，3，4；,G1.arcs=,G2.vexs=1，2，3，4，5；,G2.arcs=,7.2 图的存储结构,图的邻接表存储表示,表头结点结构: 数据域（data）用于存储顶点的名或其它有关信息； 链域（firstarc）用于指向链表中第一个顶点（即与顶点 vi邻接的第一个邻接点） 边表结点结构：adjvex 与顶点vi邻接的点在图中的位置 info 存储和边相关的信息(若无，则置空NULL) nextarc 指向下一条边的结点的指针,表头结点 弧结点,实现：为图中每个顶点建立一个单链
15、表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）；同时为每一个单链表附设一个表头结点，并将所有的表头结点顺序存储（数组），以便随机访问任一顶点的链表。,typedef struct ArcNode / 弧结点 int adjvex; /邻接点域，存放与Vi邻接的点在表头数组中的位置 struct node *nextarc; /链域，指示依附于vi的下一条边或弧的结点， /VRType weight; InfoType *info; / 定义与弧相关的权值，无权则为0 ArcNode ; /定义 指向该弧相关信息的指针,typedef struct /图的结构定义 AdjList vertices; /顶点向量 int vexnum, arcnum; GraphKind kind; / 图的种类标志 MGraph;,7.2 图的存储结构,图的邻接表存储表示,7.2 图的存储结构,图的邻接表存储表示,提示：在无向图，每一个边结点在图的单链表中出现两次，故无向图中若有n个顶点和e条边，则需要存储空间为：n+2e,7.2 图的存储结构,图的邻接表存储表
