数据结构图基本知识点

《数据结构图基本知识点》由会员分享，可在线阅读，更多相关《数据结构图基本知识点（108页珍藏版）》请在金锄头文库上搜索。

1、第8章 图,2018年12月12日,第8章 图,8.1 图的基本概念 8.2 图的基本存储结构 8.2.1 邻接距阵及其实现 8.2.2 邻接表及其实现 8.3 图的遍历 8.3.1 深度优先搜索遍历 8.3.2 广度优先搜索遍历 8.4 图的应用 8.4.1 连通图的最小生成树 8.4.2 拓扑排序,一、现实中的图,8.1 图的基本概念,图最常见的应用是在交通运输和通信网络中找出造价最低的方案。通信网络示例如下图所示：,图G是由一个顶点集V和一个边集E构成的数据结构。记为二元组形式： G= (V, E) 其中: V是由顶点构成的非空有限集合，记为：VV0, V1, V2, Vn-1 E是由V

2、中顶点的对偶构成的有限集合，记为：E=(V0, V2), (V3, V4), ，若E为空，则图中只有顶点而没有边。 其中对偶可以表示成： (Vi, Vj)无序的对偶称为边，即(Vi, Vj)=(Vj, Vi) ，其图称为无向图 有序的对偶称为弧，即 ，则称Vi为弧尾，称Vj为弧头，该图称为有向图,二、图的定义,有向图和无向图示例：,无向图G1的二元组表示： V(G1)=V1, 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)=，,在

3、无向图中，若存在一条边（Vi, Vj），则称Vi和Vj互为邻接点（Adjacent） 在有向图中，若存在一条弧，则称Vi为此弧的起点，称Vj为此弧的终点，称Vi邻接到Vj，Vj邻接自Vi，Vi和Vj互为邻接点。,1邻接点,2顶点的度、入度和出度,在无向图中，与顶点v相邻接的边数称为该顶点的度，记为D(v)。 在有向图中，顶点v的度又分为入度和出度两种： 以顶点v为终点(弧头)的弧的数目称为顶点v的入度，记为ID(v)； 以顶点v为起点(弧尾)的弧的数目称为顶点v的出度，记为OD(v)； 有向图顶点v的度为该顶点的入度和出度之和，即 D(v)=ID(v)+OD(v),无论是有向图还是无向图，一个

4、图的顶点数n、边(弧)数e和每个顶点的度di之间满足以下的关系式：,即在有向图或无向图中： 所有顶点度数之和 ：边数 = 2 ：1,3完全图、稠密图和稀疏图,在图G中： 若G为无向图，任意两个顶点之间都有一条边，称G为无向完全图。顶点数为n，无向完全图的边数： e=Cn2 =n(n1)/2 若G为有向图，任意两个顶点Vi, Vj之间都有弧 、 ，称G为有向完全图。如顶点数为n，有向完全图的弧数： e=Pn2 =n(n1) 例如，无向图G1就是4个顶点无向完全图。 若一个图接近完全图，则称其为稠密图；反之，若一个图含有很少条边或弧（即en2），则称其为稀疏图。,4子图,若有图G=(V, E)和G

5、=(V, E) 且V 是V的子集，即V V ， E是E的子集，即 E E 则称图G为图G的子图。,5路径、回路和路径长度,在无向图G中，若存在一个顶点序列(Vp , Vi1 , Vi2 , , Vin , Vq)，使(Vp, Vi1)，(Vi1, Vi2)，(Vin, Vq)均为图G的边，则该称顶点的序列为顶点Vp到顶点Vq的路径。若G是有向图，则路径是有向的。 路径长度定义为路径上的边数或者弧的数目。 若一条路径中不出现重复顶点，则称此路径为简单路径。 若一条路径的起点和终点相同（Vp=Vq）称为回路或环。 除了起点和终点相同外，其余顶点不相同的回路，称为简单回路或简单环。,例如，在无向图G

6、1中： 顶点序列（V1, V2, V3, V4）是一条从顶点V1到顶点V4，长度为3的简单路径； 顶点序列（V1, V2, V4, V1, V3）是一条从顶点V1到顶点V3，长度为4的路径，但不是简单路径； 顶点序列（V1, V2, V3, V1）是一条长度为3的简单回路。 在有向图G3中： 顶点序列（V2, V3, V2）是一个长度为2的有向简单环。,6连通、连通分量和连通图、生成树,在无向图G中： 如果从顶点Vi 到顶点Vj至少有一条路径，则称Vi与Vj是连通的。 如果图中任意两个顶点都连通，则称G为连通图，否则称为非连通图。 在非连通图G中，任何一个极大连通子图称为G的连通分量。 任何连

7、通图的连通分量只有一个，即其自身，而非连通图有多个连通分量。 在一个连通图中，含有全部顶点的极小(边数最少)连通子图，称为该连通图的生成树。(包含图的所有 n 个结点，但只含图的 n-1 条边。在生成树中添加一条边之后，必定会形成回路或环),非连通图G4,图G1和G2为连通图,非连通图G4的三个连通分量,连通图G5,连通图G5的两棵生成树,7强连通、强连通分量和强连通图,在有向图G中： 存在从顶点Vi 到顶点Vj的路径，也存在从顶点Vj 到顶点Vi的路径，则称Vi与Vj是强连通的。 如果图中任意两个顶点都是强连通，则称G为强连通图，否则称为非强连通图。 在非强连通图G中，任何一个极大强连通子图

8、称为G的强连通分量。 任何强连通图的强连通分量只有一个，即其自身，而非强连通图有多个强连通分量。,有向图G和强连通分量示例：,8权、带权图、有向网和无向网,在一个图中，各边(或弧)上可以带一个数值，这个数值称为权。 这种每条边都带权的图称为带权图或网 有向网：带权有向图 无向网：带权无向图,8.2 图的基本存储结构,图需存储的信息： 各顶点的数据 各个边（弧）的信息，包括： 哪两个顶点有边（弧） 若有权要表示出来 顶点数、边（弧）数,8.2.1 邻接矩阵及其实现,顶点数据存储： 一维数组（顺序存储） 边（弧）信息的存储： 邻接矩阵：图中n个顶点之间相邻关系的n阶方阵（即二维数组ann） 邻接矩

9、阵中元素值情况（规定自身无边、无弧）：,无向图,有向图,网,W 表示边上的权值； 0 表示vi与vj是同一个顶点 表示一个计算机允许的、大于所有边上权值的数。,1、举例,无向图,特点： 对称 行或列方向的非零元素（或1）的个数为此顶点的度,无向网,1、举例,有向图,特点： 不一定对称 行方向的非零元素（或1）的个数为此顶点的出度 列方向的非零元素（或1）的个数为此顶点的入度,容易实现图的操作，如：求某顶点的度、判断顶点之间是否 有边（弧）、找顶点的邻接点等等。 n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。 对稀疏图而言尤其浪费空间。,邻接矩阵法优点：,邻接矩阵法缺点：,2、邻接

10、矩阵法特点,3、邻接矩阵存储的图类型定义,# define MAX 100 /* MAX为图中顶点最多个数 */ typedef int vextype; /* vextype为顶点的数据类型 */ typedef struct vextype vexMAX; /* 一维数组存储顶点信息 */ int arcMAXMAX; /*邻接矩阵存储边（弧）信息 */ int vn, en; /* vn顶点数和en边数 */ MGraph; /* 图类型 */,注：MGraph 既可以表示有向图、无向图，也可以表示有整型权的网,分析： 各顶点信息：键盘输入 各边信息：邻接矩阵，顶点间有边值为1，无边值为

11、0 顶点数、边数：键盘输入,例：建一个如图所示的无向图,4、建图运算 建图就是完成图类型变量中各个成员值的创建过程。,执行时输入数据： 5 6 0 1 2 3 4 0 1 0 3 1 2 1 4 2 3 2 4,算法实现（无向图）,void CreateGraph(MGraph *g) int i, j, v, e; scanf(“%d %d“, /*建有向图时此句不要*/ ,8.2.2 邻接表及其实现,是顺序与链接相结合的图的存储方式 所有顶点组成一个数组，为每个顶点建立一个单链表 有两部分组成： 表头顶点数组（存放顶点信息） 表体单链表（存放与顶点相关的边或弧的信息）,1、举例,无向图,顶

12、点的度：该顶点所在单链表中表结点个数,无向网,与顶点V1相邻接的顶点在数组中的下标,权值,1、举例,有向图,以顶点V1为始点的弧的终点顶点在数组中的下标,顶点的出度 该顶点所在单链表中表结点个数 顶点的入度 查询整个邻接表中的表结点，与该顶点的序号（数组下标）一致的表结点个数,邻接表的缺点：,邻接表的优点：,空间效率高；容易寻找顶点的邻接点；,判断任意两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。,2、邻接表法特点,3、邻接表存储的图类型定义,（1）表(边)结点表示边(或弧)信息的链表中结点,表结点：,邻接点序号(下标),下一个邻接点地址,权值,typedef struct

13、 arcnode int adjvex; struct arcnode *next; ArcNode, *Arc;,表结点类型,3、邻接表存储的图类型定义,（2）顶点结点类型,顶点结点：,顶点信息,链表头指针(指向第一个表结点),typedef struct vexnode vextype vertex; ArcNode *firstarc; VexNode;,顶点结点类型,（3）图的邻接表类型,typedef struct VexNode adjlistMAX; /*顶点结点所在数组*/ int vn, en; ALGraph;,分析： 各顶点信息：顶点数据键盘输入 各链表：若顶点有出度弧，

14、创建表结点，头插入链表 顶点数、边数：键盘输入,例：建一个如图所示的有向图,4、建图运算 建图就是完成图类型变量中各个成员值的创建过程。,执行时输入数据： 4 4 0 1 2 3 0 2 0 1 2 3 3 0,vertex,firstarc,adjvex,next,算法实现（有向图）,void CreateAGraph(ALGraph *g) int i, j, v, e; ArcNode* p; scanf(“%d %d“, ,思考： 建无向图如何修改？,B,A,C,D,F,E,补例：图的邻接表存储表示,有向图的邻接表,A,B,E,C,D,可见，在有向图的邻接表中不易找到指向该顶点的弧,A

15、,B,E,C,D,有向图的逆邻接表,在有向图的逆邻接表中，对每个顶点，链接的是指向该顶点的弧,8.3 图的遍历,从图中某个顶点出发遍历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。 图的遍历有两种方法： 深度优先搜索遍历（DFS） 广度优先搜索遍历（BFS）。 它们对无向图和有向图都适用。,8.3.1 连通图的深度优先搜索遍历,1深度优先搜索(dfs)的基本思想 首先访问初始出发点V0，并将其标记设置为已访问； 然后任选一个与V0相邻接且没有被访问的邻接点V1作为新的出发点，访问V1之后，将其标记设置为已访问； 再以V1为新的出发点，继续进行深度优先搜索，访问与V1相邻接且没有被访问的任一个顶点V2； 重复上述过程，若遇到一个所有邻接点均被访问过的顶点，则回到已访问顶点序列中最后一个还存在未被访问的邻接点的顶点，再从该顶点出发继续进行深度优先搜索，直到图中所有顶点都被访问过，搜索结束。,例,序列1： V0,V1,V3,V7,V4,V2,V5,V6,从v0出发的DFS序列为：,由于没有规定 访问邻接点的顺序， DFS序列不是唯一的,序列2： V0,V1,V4,V7,V3,V2,V5,V6,算法描述： 访问开始顶点（如 v）； 寻找 v 顶点未被访问的第一个邻接顶点（如 w）； 并把 w 作为开始顶点继续深度优先搜索遍历（递归思想）； 直到所有顶点被访问； 其中处理：