数据结构 C语言版 第2版 教学课件 ppt 李云清 杨庆红 揭安全 第8章_图.ppt

数据结构,李云清 杨庆红 揭安全,高等学校精品课程,人民邮电出版社,（第2版）,数据结构,揭安全,江西省高等学校精品课程,E_mail: jieanquan@,江西师范大学计算机信息工程学院,第８章 图,图的基本概念,图的基本运算,生成树与最小生成树,拓扑排序,图的基本存储结构,最短路径,关键路径,图的遍历,8.1 图的基本概念,一、图的定义,图是由一个非空的顶点集合和一个描述顶点之间多对多关系的边（或弧）集合组成的一种数据结构，它可以形式化地表示为： 图＝（V，E） 其中V={x|x某个数据对象集}，它是顶点的有穷非空集合；E={（x，y）|x，yV}或E={|x，yV且P（x，y）}，它是顶点之间关系的有穷集合，也叫做边集合，P（x，y）表示从x到y的一条单向通路图的应用举例 例1 交通图（公路、铁路） 顶点：地点 边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示；,例2 电路图 顶点：元件 边：连接元件之间的线路,例3 通讯线路图 顶点：地点 边：地点间的连线,通常，也将图G的顶点集和边集分别记为V（G）和E（G）E（G）可以是空集，若E（G）为空，则图G只有顶点而没有边。

若图G中的每条边都是有方向的，则称G为有向图在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示例如，有序对表示一条由vi到vj的有向边有向边又称为弧，弧的始点称为弧尾，弧的终点称为弧头若图G中的每条边都是没有方向的，则称G为无向图无向图中的边均是顶点的无序对，无序对通常用圆括号表示图8-1,图8.1（a）表示的是有向图G1，该图的顶点集和边集分别为： V（G1）={v1，v2，v3，v4} E（G1）={，，，},例,有序对 ： 用以为vi起点、以vj为终点 的有向线段表示，称为有向 边或弧；,例：图8-1,图8.1（b）表示的是无向图G2，该图的顶点集和边集分别为： V（G2）={v1，v2，v3，v4，v5} E（G2）={（vl，v2），（v1，v3），（v1，v4），（v2，v3），（v2，v5），（v4，v5）},无序对(vi,vj)： 用连接顶点vi、vj的线段 表示，称为无向边；,在以后的讨论中，我们约定： （1）一条边中涉及的两个顶点必须不相同，即：若（vi，vj）或是E（G）中的一条边，则要求vi≠vj； （2）一对顶点间不能有相同方向的两条有向边； （3）一对顶点间不能有两条无向边，即只讨论简单的图。

若用n表示图中顶点的数目，用e表示图中边的数目，按照上述规定，容易得到下述结论：对于一个具有n个顶点的无向图，其边数e小于等于n（n-1）/2，边数恰好等于n（n-1）/2的无向图称为无向完全图；对于一个具有n个顶点的有向图，其边数e小于等于n（n-1），边数恰好等于n（n-1）的有向图称为有向完全图也就是说完全图具有最多的边数，任意一对顶点间均有边相连二、完全图,例：图8-2,图8.2所示的G3与G4分别是具有4个顶点的无向完全图和有向完全图图G3共有4个顶点6条边；图G4共有4个顶点12条边若（vi，vj）是一条无向边，则称顶点vi和vj互为邻接点 若是一条有向边，则称vi邻接到vj，vj邻接于vi，并称有向边关联于vi与vj，或称有向边与顶点vi和vj相关联三、度、入度、出度,在图中，一个顶点的度就是与该顶点相关联的边的数目，顶点v的度记为D（v）例如在图8.2（a）所示的无向图G3中，各顶点的度均为3 若G为有向图，则把以顶点v为终点的边的数目称为顶点v的入度，记为ID（v）；把以顶点v为始点的边的数目称为v的出度，记为OD（v），有向图中顶点的度数等于顶点的入度与出度之和，即D（v）=ID（v）+OD（v）。

无论有向图还是无向图，图中的每条边均关联于两个顶点，因此，顶点数n、边数e和度数之间有如下关系：,e=,……….（式8-1）,四、子图,给定两个图Gi和Gj，其中Gi=（Vi，Ei），Gj=（Vj，Ej），若满足ViVj，EiEj，则称Gi是Gj的子图v1,v1,子图示例,（a）无向图G3的部分子图,,（b）有向图G4的部分子图,五、路径,无向图G中若存在着一个顶点序列v、v1’、v2’、…、vm’、u，且（v，v1’）、（v1’，v2’）、…、（vm’，u）均属于E（G），则称该顶点序列为顶点v到顶点u的一条路径，相应地，顶点序列u、vm’、vm-1’、…、v1’、v是顶点u到顶点v的一条路径 如果G是有向图，路径也是有向的，它由E（G）中的有向边、、…、组成路径长度是该路径上边或弧的数目如果一条路径上除了起点v和终点u相同外，其余顶点均不相同，则称此路径为一条简单路径起点和终点相同（v=u）的简单路径称为简单回路或简单环六、连通图与强连通图,在无向图G中，若从顶点vi到顶点vj有路径，则称vi与vj是连通的若V（G）中任意两个不同的顶点vi和vj都连通（即有路径），则称G为连通图。

例如，图8.1（b）所示的无向图G2、图8.2（a）所示的无向图G3是都是连通图无向图G的极大连通子图称为G的连通分量根据连通分量的定义，可知任何连通图的连通分量是其自身，非连通的无向图有多个连通分量例：非连通图及其连通分量示例,（a）非连通图G5 （b）G5的两个连通分量H1和H2,在有向图G中，若对于V（G）中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图有向图的极大强连通子图称为G的强连通分量根据强连通图的定义，可知强连通图的唯一强连通分量是其自身，而非强连通的有向图有多个强连分量例如，图8.2（b）所示的有向图G4是一个具有4个顶点的强连通图，图8.5（a）所示的有向图G6不是强连通图（v2、v3、v4没有到达v1的路径），它的两个强连通分量H3与H4如图8.5（b）所示七、网络,有时在图的每条边上附上相关的数值，这种与图的边相关的数值叫权权可以表示两个顶点之间的距离、耗费等具有某种意义的数若将图的每条边都赋上一个权，则称这种带权图为网络8.2 图的基本运算,图是一种复杂数据结构，由图的定义及图的一组基本操作构成了图的抽象数据类型。

ADT Graph { 数据对象V： V是具有相同特性的数据元素的集合，称为顶点集 数据关系R： R={|v，wV且P（v，w），P（v，w）定义了边（v，w）的信息},图的基本操作如下： （1）Creat（n） 创建一个具有n个顶点，没有边的图； （2）Exist（i，j） 如果存在边（i，j）则返回1，否则返回0； （3）Edges（） 返回图中边的数目； （4）Vertices（） 返回图中顶点的数目； （5）Add（i，j） 向图中添加边（i，j）； （6）Delete（i，j） 删除边（i，j）； （7）Degree（i） 返回顶点i的度； （8）InDegree（i） 返回顶点i的入度； （9）OutDegree（i） 返回顶点i的出度； } ADT Graph,8.3 图的基本存储结构,图的邻接矩阵存储表示法,图的邻接多重表表示法,图的邻接表表示法,8.3 图的基本存储结构,图的存储结构至少要保存两类信息： 1)顶点的数据 2)顶点间的关系,约定: G=是图, V={v0,v1,v2, … vn-1 },设顶点的 角标为它的编号,8.3.1邻接矩阵及其实现,给定图G=（V，E），其中V（G）={v0，…，vi，…，vn-1}，G的邻接矩阵（Adacency Matrix）是具有如下性质的n阶方阵：,无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。

一、非网络的邻接矩阵,图的邻接矩阵示例,用邻接矩阵表示图，很容易判定任意两个顶点之间是否有边相连，并求得各个顶点的度数对于无向图，顶点vi的度数是邻接矩阵中第i行或第i列值为1的元素个数，即：,D（vi）= = …（8-2）,对于有向图，邻接矩阵中第i行值为1的元素个数为顶点vi的出度，第i列值为1的元素的个数为顶点vi的入度，即：,OD（vi）= ; ID（vi） = … （8-3）,二、网络的邻接矩阵,当G=（V，E）是一个网络时，G的邻接矩阵是具有如下性质的n阶方阵：,其中Wij表示边上的权值；∞表示一个计算机允许的、大于所有边上权值的数网络的邻接矩阵示例,邻接矩阵存储结构,/**************************************/ /* 邻接矩阵类型定义 文件名：ljjz.h */ /**************************************/ #include #define FINITY 5000 /*此处用5000代表无穷大*/ #define M 20 /*最大顶点数*/ typedef char vertextype; /*顶点值类型*/ typedef int edgetype; /*权值类型*/ typedef struct{ vertextype vexs[M]; /*顶点信息域*/ edgetype edges[M][M]; /*邻接矩阵*/ int n,e; /*图中顶点总数与边数*/ } Mgraph;,/* 函数功能：建立图的邻接矩阵存储结构 函数参数：邻接矩阵的指针变量g；存放图信息的文件名s；图的类型参数c，c=0表示建立无向图，否则表示建立有向图 函数返回值：无 */ void creat(Mgraph *g,char *s ,int c) {int i,j,k,w; /*建立网络的邻接矩阵存储结构*/ FILE *rf ; rf = fopen(s, “r“) ;/*从文件中读取图的边信息*/ if (rf) { fscanf(rf,“%d%d“, /*读入图的顶点数与边数*/,for(i=0;in;i++) /*读入图中的顶点值*/ fscanf(rf,“%1s“,,} else g-n=0; },图的文件信息以文本文件的形式提供，里面存放了图的顶点数、边数、顶点信息和所有的边信息。

当建立网络存储结构时，边信息以三元组（i，j，w）的形式输入，i、j分别表示两顶点的序号，w表示边上的权4 4 0123 0 1 56 0 2 34 0 3 78 2 3 25,输入文件g7.txt内容,建图调用方式: creat(&g,”g7.txt”，0),例:对图8.6所示的无向网络G7,当参数c=1时，将建立有向图的存储结构 当建立非网络的存储结构时，所有的边信息只需按二元组（i，j）的形式输入，边的权值取值为0或18.3.2邻接表及其实现,用邻接矩阵表示法存储图，占用的存储单元个数只与图中顶点的个数有关，而与边的数目无关一个含有n个顶点的图，如果其边数比n2少得多，那么它的邻接矩阵就会有很多空元素，浪费了存储空间无向图的邻接表 对于图G中的每个顶点vi，该方法把所有邻接于vi的顶点vj链成一个带头结点的单链表，这个单链表就称为顶点vi的邻接表单链表中的每个结点至少包含两个域，一个为邻接点域（adjvex），它指示与顶点vi邻接的顶点在图中的位序，另一个为链域（next），它指示与顶点vi邻接的下一个结点为了便于随机访问任一顶点的邻接表，可将所有头结点顺序存储在一个向量中就构成了图的邻接表存储。

最后将图的顶点数及边数等信息与邻接表放在一起来描述图的存储结构表头结点结构,边结点结构,对于无向图，vi的邻接表中每个表结点都对应于与vi相关联的一条边；对于有向图来说，如果每一顶点vi的邻接表中每个表结点都存储以vi的为始点射出的一条边，则称这种表为有向图的出边表（有向图的邻接表），反之，若每一顶点vi的邻接表中每个表结点都对应于以vi为终点的边（即射入vi的边），则称这种表为有向图的入边表（又称逆邻接表）。