《数据结构 C语言版 教学课件 ppt 作者 李云清 第08章_图》由会员分享，可在线阅读，更多相关《数据结构 C语言版 教学课件 ppt 作者 李云清 第08章_图（135页珍藏版）》请在金锄头文库上搜索。
1、第章 图,图的基本概念,图的基本运算,生成树与最小生成树,拓扑排序,图的基本存储结构,最短路径,关键路径,图的遍历,8.1 图的基本概念,一、图的定义,图是由一个非空的顶点集合和一个描述顶点之间多对多关系的边（或弧）集合组成的一种数据结构，它可以形式化地表示为： 图（V，E） 其中V=x|x某个数据对象集，它是顶点的有穷非空集合；E=（x，y）|x，yV或E=|x，yV且P（x，y），它是顶点之间关系的有穷集合，也叫做边集合，P（x，y）表示从x到y的一条单向通路。,图的应用举例 例1 交通图（公路、铁路） 顶点：地点 边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示；,
2、例2 电路图 顶点：元件 边：连接元件之间的线路,例3 通讯线路图 顶点：地点 边：地点间的连线,例4 各种流程图 如产品的生产流程图 顶点：工序 边：各道工序之间的顺序关系,通常，也将图G的顶点集和边集分别记为V（G）和E（G）。E（G）可以是空集，若E（G）为空，则图G只有顶点而没有边。,若图G中的每条边都是有方向的，则称G为有向图。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。例如，有序对表示一条由vi到vj的有向边。有向边又称为弧，弧的始点称为弧尾，弧的终点称为弧头。若图G中的每条边都是没有方向的，则称G为无向图。无向图中的边均是顶点的无序对，无序对通常用圆括
3、号表示。,图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
4、）或是E（G）中的一条边，则要求vivj； （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个顶点的无向完全图和有向完全图。
5、图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）
6、。,无论有向图还是无向图，图中的每条边均关联于两个顶点，因此，顶点数n、边数e和度数之间有如下关系：,e=,.（式8-1）,四、子图,给定两个图Gi和Gj，其中Gi=（Vi，Ei），Gj=（Vj，Ej），若满足ViVj，EiEj，则称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是有向图，路径也是有
7、向的，它由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的连通分量。根据连通分量的定义，可知任何连通图的连通分量是其自身，非连通的无向图有多个连通分量。,例：非连通图
8、及其连通分量示例,（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）所示。,七、网络,有时在图的每条边上附上相关的数值，这种与图的边相关的数值叫权
9、。,权可以表示两个顶点之间的距离、耗费等具有某种意义的数。若将图的每条边都赋上一个权，则称这种带权图为网络。,作业：,8.1 对于无向图8.29，试给出 （1）图中每个顶点的度； （2）该图的邻接矩阵； （4）该图的连通分量。,v0,v3,v4,v2,v1,v5,v6,图8.29 无向图,8.2 给定有向图8.30，试给出 （1）顶点D的入度与出度； （2）该图的出边表与入边表； （3）该图的强连通分量。,A,B,C,D,E,图8.30 有向图,8.2 图的基本运算,图是一种复杂数据结构，由图的定义及图的一组基本操作构成了图的抽象数据类型。 ADT Graph 数据对象V：V是具有相同特性的数
10、据元素的集合，称为顶点集。 数据关系R： R=|v，wV且P（v，w），P（v，w）定义了边（或弧）（v，w）的信息,图的基本操作如下： （1）creatgraph（&g） 创建一个图的存储结构。 （2）insertvertex（&g，v） 在图g中增加一个顶点v。 （3）deletevertex（&g，v） 在图g中删除顶点v及所有和顶点v相关联的边或弧。 （4）insertedge（&g，v，u） 在图g中增加一条从顶点v到顶点u的边或弧。 （5）deleteedge（&g，v，u） 在图g中删除一条从顶点v到顶点u的边或弧。,（6）trave（g） 遍历图g。 （7）locatevert
11、ex（g，v） 求顶点v在图g中的位序。 （8）fiirstvertex（g，v） 求图g中顶点v的第一个邻接点。 （9）degree（g，v） 求图g中顶点v的度数。 （10）nextvertex（g，v，w） 求图g中与顶点v相邻接的顶点w的下一个邻接点。即求图g中顶点v的某个邻接点，它的存储顺序排在邻接点w的存储位置之后。 ADT Graph,8.3图的基本存储结构,图的存储结构至少要保存两类信息： 1)顶点的数据 2)顶点间的关系,约定: G=是图, V=v0,v1,v2, vn-1 ,设顶点的 角标为它的编号,8.3.1邻接矩阵及其实现,给定图G=（V，E），其中V（G）=v0，vi
12、，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的邻接矩阵是具有
13、如下性质的n阶方阵：,其中Wij表示边上的权值；表示一个计算机允许的、大于所有边上权值的数。,网络的邻接矩阵示例,邻接矩阵存储结构,#define FINITY 5000 /*此处用5000代表无穷大*/ #define m 20 /*最大顶点数*/ typedef char vertextype; /*顶点值类型*/ typedef int edgetype; /*权值类型*/ typedef struct vertextype vexsm; /*顶点信息域*/ edgetype edgesmm; /*邻接矩阵*/ int n,e; /*图中顶点总数与边数*/ mgraph; /*邻接矩阵表
14、示的图类型*/,文件名:mgraph.h,/*/ /* 图的邻接矩阵创建算法 */ /* 文件名：c_ljjz.c 函数名：creatmgraph1() */ /*/ #include #include “mgraph.h“ void creatmgraph1(mgraph *g) int i,j,k,w; /*建立有向网络的邻接矩阵存储结构*/ printf(“please input n and e:n“); scanf(“%d%d“,for(i=0;in;i+) /*输入图中的顶点值*/ g-vexsi=getchar(); for(i=0;in;i+) /*初始化邻接矩阵*/ for(
15、j=0;jn;j+) if (i=j) g-edgesij=0; else g-edgesij=FINITY; printf(“please input edges:n“); for (k=0;ke;k+) /*输入网络中的边*/ scanf(“%d%d%d“, 即可*/ ,说明: 当建立有向网时，边信息以三元组（i，j，w）的形式输入，i、j分别表示两顶点的序号，w表示边上的权。对于每一条输入的边信息（i，j，w），只需将g-edgesij赋值为w。 算法8.5中用到的creatmgraph2()是用于建立无向网络的函数，它与creatmgraph1()的区别在于对每一条输入的边信息（i，j，w），需同时将g-edgesij 和g-edgesji赋值为w。 当建立非网络的存储结构时，所有的边信息只需按二元组（i，j）的形式输入。,8.3.2邻接表及其实现,用邻接矩阵表示法存储图，占用的存储单元个数只与图中顶点的个数有关，而与边的数目无关。一个含有n个顶点
