《数据结构__图的基本知识点讲述》由会员分享，可在线阅读，更多相关《数据结构__图的基本知识点讲述（108页珍藏版）》请在金锄头文库上搜索。
1、第8章 图 * 第8章 图 8.1 8.1 图的基本概念图的基本概念 8.2 8.2 图的基本存储结构图的基本存储结构 8.2.1 8.2.1 邻接距阵及其实现邻接距阵及其实现 8.2.2 8.2.2 邻接表及其实现邻接表及其实现 8.3 8.3 图的遍历图的遍历 8.3.1 8.3.1 深度优先搜索遍历深度优先搜索遍历 8.3.2 8.3.2 广度优先搜索遍历广度优先搜索遍历 8.4 8.4 图的应用图的应用 8.4.1 8.4.1 连通图的最小生成树连通图的最小生成树 8.4.2 8.4.2 拓扑排序拓扑排序 一、现实中的图 8.1 图的基本概念 图最常见的应用是在交通运输和通信网络中找出
2、造价 最低的方案。通信网络示例如下图所示： 图G是由一个顶点集V和一个边集E构成的数据结构 。记为二元组形式： G= (V, E) 其中: V是由顶点构成的非空有限集合，记为：VV0, V1, V2, Vn-1 E是由V中顶点的对偶构成的有限集合，记为：E=(V0, V2), (V3, V4), ，若E为空，则图中只有顶点而没有边。 其中对偶可以表示成： (Vi, Vj)无序的对偶称为边，即(Vi, Vj)=(Vj, Vi) ，其图称为 无向图 有序的对偶称为弧，即 ，则称Vi 为弧尾，称Vj为弧头，该图称为有向图 二、图的定义 有向图和无向图示例： 无向图G1的二元组表示： V(G1)=V1
3、, V2, V3, V4 E(G1)=(V1, V2)，(V1, V3)，(V1, V4)，(V2, V3)，(V2, V4)，(V3, V4) 有向图G3的二元组表示： V(G3)=V1, V2, V3 E(G3)=， l 在无向图中，若存在一条边（Vi, Vj），则称Vi和Vj 互为邻接点邻接点（Adjacent） l 在有向图中，若存在一条弧，则称Vi为此 弧的起点，称Vj为此弧的终点，称Vi邻接到Vj，Vj 邻接自Vi，Vi和Vj互为邻接点。 1 1邻接点邻接点 2顶点的度、入度和出度 l 在无向图中，与顶点v相邻接的边数称为该顶点的 度，记为D(v)。 l 在有向图中，顶点v的度又分
4、为入度和出度两种： 以顶点v为终点(弧头)的弧的数目称为顶点v的入度，记 为ID(v)； 以顶点v为起点(弧尾)的弧的数目称为顶点v的出度，记 为OD(v)； 有向图顶点v的度为该顶点的入度和出度之和，即 D(v)=ID(v)+OD(v) l 无论是有向图还是无向图，一个图的顶点数n、边( 弧)数e和每个顶点的度di之间满足以下的关系式： l 即在有向图或无向图中： 所有顶点度数之和 ：边数 = 2 ：1 3完全图、稠密图和稀疏图 l 在图G中： 若G为无向图，任意两个顶点之间都有一条边，称G为无 向完全图。顶点数为n，无向完全图的边数： e=Cn2 =n(n1)/2 若G为有向图，任意两个顶
5、点Vi, Vj之间都有弧 、 ，称G为有向完全图。如顶点数为n，有向完全图 的弧数： e=Pn2 =n(n1) l 例如，无向图G1就是4个顶点无向完全图。 l 若一个图接近完全图，则称其为稠密图稠密图；反之，若一个图含 有很少条边或弧（即en2），则称其为稀疏图稀疏图。 4 4子图子图 l 若有图G=(V, E)和G=(V, E) l 且V 是V的子集，即V V ， E是E的子集，即 E E l 则称图G为图G的子图。 5路径、回路和路径长度 l 在无向图G中，若存在一个顶点序列(Vp , Vi1 , Vi2 , , Vin , Vq) ，使(Vp, Vi1)，(Vi1, Vi2)，(Vin
6、, Vq)均为图G的边，则该称 顶点的序列为顶点Vp到顶点Vq的路径。若G是有向图，则路 径是有向的。 l 路径长度定义为路径上的边数或者弧的数目。 l 若一条路径中不出现重复顶点，则称此路径为简单路径。 l 若一条路径的起点和终点相同（Vp=Vq）称为回路或环。 l 除了起点和终点相同外，其余顶点不相同的回路，称为简单 回路或简单环。 l 例如，在无向图G1中： 顶点序列（V1, V2, V3, V4）是一条从顶点V1到顶点 V4，长度为3的简单路径； 顶点序列（V1, V2, V4, V1, V3）是一条从顶点V1到 顶点V3，长度为4的路径，但不是简单路径； 顶点序列（V1, V2, V
7、3, V1）是一条长度为3的简单 回路。 l 在有向图G3中： 顶点序列（V2, V3, V2）是一个长度为2的有向简单 环。 6连通、连通分量和连通图、生成树 l 在无向图G中： 如果从顶点Vi 到顶点Vj至少有一条路径，则称Vi与Vj是连通 的。 如果图中任意两个顶点都连通，则称G为连通图，否则称为 非连通图。 在非连通图G中，任何一个极大连通子图称为G的连通分量 。 任何连通图的连通分量只有一个，即其自身，而非连通图有 多个连通分量。 在一个连通图中，含有全部顶点的极小(边数最少)连通子图 ，称为该连通图的生成树。(包含图的所有 n 个结点，但只 含图的 n-1 条边。在生成树中添加一条
8、边之后，必定会形成 回路或环) l 非连通图G4 AB CD E FG IJ K AB CD E IJ K F G l 图G1和G2为连通图 l 非连通图G4的三个连通分量 l 连通图G5 AB CD l 连通图G5的两棵生成树 AB CD AB CD 7强连通、强连通分量和强连通图 l 在有向图G中： 存在从顶点Vi 到顶点Vj的路径，也存在从顶点Vj 到顶点Vi 的路径，则称Vi与Vj是强连通的。 如果图中任意两个顶点都是强连通，则称G为强连通图， 否则称为非强连通图。 在非强连通图G中，任何一个极大强连通子图称为G的强连 通分量。 任何强连通图的强连通分量只有一个，即其自身，而非强 连通
9、图有多个强连通分量。 有向图G和强连通分量示例： 8权、带权图、有向网和无向网 l 在一个图中，各边(或弧)上可以带一个数值，这个数值称为 权。 l 这种每条边都带权的图称为带权图或网带权图或网 有向网：有向网：带权有向图带权有向图 无向网：无向网：带权无向图带权无向图 8.2 图的基本存储结构 l l 图需存储的信息：图需存储的信息： 各顶点的数据各顶点的数据 各个边（弧）的信息，包括：各个边（弧）的信息，包括： l l哪两个顶点有边（弧）哪两个顶点有边（弧） l l若有权要表示出来若有权要表示出来 顶点数、边（弧）数顶点数、边（弧）数 V0 V4 V3 V1 V2 V0 V1 V2 V3
10、a ij= 0 vi与vj无边 1 vi与vj有边 8.2.1 8.2.1 邻接矩阵及其实现邻接矩阵及其实现 l l 顶点数据存储：顶点数据存储： 一维数组（顺序存储）一维数组（顺序存储） l l 边（弧）信息的存储：边（弧）信息的存储： 邻接矩阵邻接矩阵：图中：图中n n个顶点之间相邻关系的个顶点之间相邻关系的n n阶方阵（即二阶方阵（即二 维数组维数组annann） 邻接矩阵中元素值情况（规定自身无边、无弧）：邻接矩阵中元素值情况（规定自身无边、无弧）： l l 无向图无向图 a ij= 0 vi到vj无弧 1 vi到vj有弧 l l 有向图有向图 a ij= 或0 vi与vj无边（或vi
11、到vj无弧） w vi与vj有边（或vi到vj有弧 ） l l 网网 W 表示边上的权值； 0 表示vi与vj是同一个顶点 表示一个计算机允许的、大于所有边上权值的数。 1 1、举例、举例 无向图无向图 邻接矩阵表示 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0 V1V2 V4 V5 V3 l l 特点：特点： 对称对称 行或列方向的非零元素（或行或列方向的非零元素（或1 1）的个数为此顶点的度）的个数为此顶点的度 无向网无向网 V1V2 V4 V5 V3 2 54 3 1 1 邻接矩阵表示 0 2 4 2 0 1 5 1 0 3 1 4
12、3 0 5 1 0 V1 V2 V3 V4 V5 V1V2V3V4V5 V1 V2 V3 V4 V5 V1V2V3V4V5 1 1、举例、举例 有向图有向图 V1V2 V3 V4 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 邻接矩阵表示 l l 特点：特点： 不一定对称不一定对称 行方向的非零元素（或行方向的非零元素（或1 1）的个数为此顶点的出度）的个数为此顶点的出度 列方向的非零元素（或列方向的非零元素（或1 1）的个数为此顶点的入度）的个数为此顶点的入度 V1 V2 V3 V4 V1V2V3V4 容易实现图的操作，如：求某顶点的度、判断顶点之间是否 有边（弧）、找顶点
13、的邻接点等等。 n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。 对稀疏图而言尤其浪费空间。 邻接矩阵法优点： 邻接矩阵法缺点： 2、邻接矩阵法特点 3 3、邻接矩阵存储的图类型定义、邻接矩阵存储的图类型定义 # define MAX 100 /* MAX为图中顶点最多个数 */ typedef int vextype; /* vextype为顶点的数据类型 */ typedef struct vextype vexMAX; /* 一维数组存储顶点信息 */ int arcMAXMAX; /*邻接矩阵存储边（弧）信息 */ int vn, en; /* vn顶点数和en边数 */
14、MGraph; /* 图类型 */ 注：MGraph 既可以表示有向图、无向图，也可以表示有 整型权的网 分析：分析： 各顶点信息各顶点信息：键盘输入：键盘输入 各边信息各边信息：邻接矩阵，顶点间有边值为：邻接矩阵，顶点间有边值为1 1 ，无边值为，无边值为0 0 顶点数、边数：顶点数、边数：键盘输入键盘输入 例：建一个如图所示的无向图 01 34 2 4 4、建图运算、建图运算 建图建图就是完成图类型变量中各个成员值的创建过程。就是完成图类型变量中各个成员值的创建过程。 执行时输入数据执行时输入数据 ： 5 65 6 0 1 2 3 40 1 2 3 4 0 10 1 0 3 0 3 1 2
15、 1 2 1 41 4 2 32 3 2 42 4 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0 算法实现（无向图）算法实现（无向图） void CreateGraph(MGraph *g) int i, j, v, e; scanf(“%d %d“, /*输入顶点数和边数*/ for(v=0;vvn;v+) scanf(“%d“, /*顶点数据输入*/ for(i=0;ivn;i+) for(j=0;jvn;j+) g-arcij=0; /*邻接矩阵的初始值都为0*/ for(e=0;een;e+) /*共有g-en条边*/ scanf(“%d %d“, /*指明有边的两个顶点的序号*/ g-arcij=1; /*有边赋值为1*/ g-arcji=1; /*建有向图时此句不要*/ 8.2.2 8.2.2 邻接表及其实现邻接表及其实现 l l 是顺序与链接相结合的图的存储方式是顺序与链接相结合的图的存储方式 l l 所有顶点组成一个数组，为每个顶点建立
