《数据结构 教学课件 ppt 作者 纪颖 中国机械工业教育协会 组编 第6章 图》由会员分享，可在线阅读，更多相关《数据结构 教学课件 ppt 作者 纪颖 中国机械工业教育协会 组编 第6章 图（79页珍藏版）》请在金锄头文库上搜索。
1、主要内容,普通高等教育“十一五”国家级规划教材,第6章 图,6.1 图的基本概念 6.2 图的存储结构 6.3 图的遍历,返回目录,6.4 最小生成树 6.5 最短路径 6.6 有向无环图及其应用,6.1 图的基本概念,6.1.1 图的定义和术语 6.1.2 图的基本操作 作业,6.1.1 图的定义和术语,1. 图的定义,图是由非空的顶点集合和一个描述顶点之间边（或者弧）的关系的集合，其形式化定义为：,G=(V,E） V=v0,v1, v2, vi, ,vn E=(vi,vj)| vi ,vj VP(vi,vj),其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合，集合E中P(vi,
2、vj)表示顶点vi和顶点vj之间有一条直接连线，即偶对(vi,vj)表示一条边。,该图是一个无向图的示例在图中： 集合V=A,B,C,D,E； 集合E=(A,B),(A,D),(B,C),(B,E),(C,D),(C,E)。,该图是一个有向图的示例，在该图中： 集合V=A,B,C,D； 集合E=,。,该图是一个带权无向图的示例在图中： 集合V=A,B,C,D,E； 集合E=(A,B)3,(A,C)4,(B,C)7,(B,D)6,(C,D)5。,2. 图的基本术语,基本术语的讨论是不考虑结点的自反圈，即结点到自身的边，若(vi,vj)或是图的一条边，则vivj，并且也不允许一条边在图中重复出现。
3、, 无向图 在一个图中，如果任意两个顶点构成的偶对（vi，vj）E是无序的，即顶点之间的连线是没有方向的，则称该图为无向图。, 有向图 在一个图中，如果任意两个顶点构成的偶对（vi，vj）E是有序的，即顶点之间的连线是有方向的，则称该图为有向图。, 顶点、边、弧、弧头、弧尾,数据元素A、B、C、D、E。称为顶点。,在无向图中若在顶点vi和顶点vj之间有一条直接连线 ，则称这条连线为边。,把顶点vi和顶点vj称为邻接点，对应的边（vi,vj）称为相关边；,弧用顶点的有序偶对来表示，有序偶对的第1个结点vi被称为始点（弧尾），在图中就是不带箭头的一端,在有向图中若在顶点vi和顶点vj之间有一条直接
4、连线 ，则称这条连线为弧。,有序偶对的第2个结点vj被称为终点（弧头），在图中就是带箭头的一端。, 无向完全图,在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。可以证明，在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。, 有向完全图,在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。在一个含有n个顶点的有向完全图中，有n(n-1)条边。,若一个图接近完全图，称为稠密图；, 稠密图、稀疏图,称边数很少的图为稀疏图；, 顶点的度、入度、出度,顶点的度是指依附于某顶点v的边数，通常记为TD(v)。,在有向图中，要区别顶点的入度
5、与出度的概念。,右图中A、D、E顶点的度值分别为2，顶点B、C的度值分别为3。,顶点v的入度是指以顶点为终点的弧的数目。记为ID(v)。右图顶点A、B、C、D的入度分别为1。,顶点v的出度是指以顶点v为始点的弧的数目，记为OD(v)。右图顶点A的出度为2，C、D的出度为1，B的出度为0 。,有TD(v)=ID(v)OD(v)。对于具有n个顶点、e条边的图，顶点vi的度TD(vi)与顶点的个数以及边的数目满足关系：, 边的权和网,把与边有关的数据信息称为权。边上带权的图称为网或网络。,无向网图,有向网图, 路径、路径长度,路径是指从某顶点vi出发可以到达另一顶点vj，则称顶点vi到顶点vj有路径
6、。,右图所示的无向图中，ADCE与ABE是从顶点A 到顶点E 的两条不同路径。,路径长度是指从某顶点vi到达另一顶点vj若有路径，则路径上边的数目总和称为路径长度。,上面无向图中顶点A到顶点E的两条路径，ADCE与ABE的路径长度分别为3和2。, 回路、简单路径、简单回路,回路:从起点vi出发经过一些顶点和边又回到起点vi，则所经过的路径称为回路或者环。,简单路径:序列中顶点不重复出现的路径称为简单路径。前面提到的A到E的两条路径都为简单路径。,右图的无向图中，ADCE B A与ADCB A是从顶点A 出发 的两个不同回路（环）。,简单回路:除第一个顶点与最后一个顶点之外，其他顶点不重复出现的
7、回路称为简单回路或者简单环。如上图中的ADCB A就是简单回路。, 子图,子图就是一个图中的一部分。下面的图都是上图的子图。, 连通、连通图、连通分量,连通：在无向图中，若从一个顶点vi到另一个顶点vj(ij)有路径，则称顶点vi和vj是连通的。,连通图：如果图中任意两顶点都是连通的，则称该图是连通图。,连通分量：无向图的极大连通子图称为连通分量。,右图有2个连通分量组成。, 强连通图、强连通分量,强连通图：在有向图中若图中任意一对顶点vi 和vj(ij)均有从一个顶点vi到另一个顶点vj有路径，也有从vj到vi的路径，则称该有向图是强连通图。,右图是1个强连通图。,强连通分量：有向图的极大强
8、连通子图称为强连通分量。, 生成树,连通图的生成树，必须包含其全部n 个顶点，并且包含将n 个顶点连接起来的n-1条边。一个图可以有多棵生成树。,生成树的特点：在生成树中添加任意一条属于原图中的边必定会产生回路；若在生成树中减少任意一条边，则必然成为非连通的。,6.1.2 图的基本操作,1. creatgraph(g) 输入图g的顶点和边，建立图g的存储。 2. destroygraph(g) 释放图g占用的存储空间。 3. getvex(g,v) 在图g中找到顶点v，并返回顶点v的相关信息。 4. putvex(g,v,value) 在图g中找到顶点v，并将value值赋给顶点v。 5. i
9、nsertvex(g,v) 在图g中增添新顶点v。 6. deletevex(g,v) 在图g中，删除顶点v以及所有和顶点v相关联的边或弧。 7. insertarc(g,v,w) 在图g中增添一条从顶点v到顶点w的边或弧。,8. deletearc(g,v,w) 在图g中删除一条从顶点v到顶点w的边或弧。 9. dfstraverse(g,v) 在图g中，从顶点v出发深度优先遍历图G。 10.bfsttaverse(g,v) 在图g中，从顶点v出发广度优先遍历图。 11.locatevex(g,u) 在图g中找到顶点u，返回该顶点在图中位置。 12.firstadjvex(g,v) 在图g中
10、，返回v的第一个邻接点。若顶点在g中没有邻接顶点，则返回“空”。 13.nextadjvex(g,v,w) 在图g中，返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”。,作业,1.图有几种形式? 2.做教材习题中的以下题目。 单项选择题：(1),(2),(4) ,(6) 填空题：(8),6.2 图的存储结构,6.2.1 邻接矩阵(数组)表示法 6.2.2 邻接表 6.2.3 十字链表,6.2.4 邻接多重表 6.2.5 边集数组 作业,6.2.1 邻接矩阵(数组)表示法,邻接矩阵的存储结构，就是用一维数组存储图中 顶点的信息，用矩阵表示图中各顶点之间的邻接系。 假设
11、图G=(V,E)有n个确定的顶点即：V=v0,v1,vn-1, 则表示G中各顶点相邻关系为一个nn的矩阵，矩阵 中的元素为：,若是网图，带有权值wij，则可以表示为,用邻接矩阵存储图的示例:,A B C D E,A B C D E,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,A B C D,A B C D,0 1 1 0,0 0 0 0,0 0 0 1,1 0 0 0,A B C D,A B C D, 3 4 ,3 7 6,4 7 5, 6 5 ,特点：, 无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上（或下）三
12、角矩阵的元素即可。, 对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非元素）的个数正好是第i个顶点的度值。, 对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非元素）的个数正好是第i个顶点的出度值（或入度值）。, 用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。,类型定义： #define MAX 100 /*最大顶点数设为100*/ typedef char vertextype; /*顶点类型设为字符型*/ typedef int edgetype
13、; /*边的权值设为整型*/ typedef struct vertextype vexsMAX; /*顶点表*/ edetype edgesMAXMAX; /*邻接矩阵，即边表*/ int n,e; /*顶点数和边数*/ mgragh; /*maragh是以邻接矩阵存储的图类型*/,void createmgraph(mgraph *g) /*建立有向图g的邻接矩阵存储*/ int i,j,k,w; char ch; printf(“请输入顶点数和边数(输入格式为:顶点数,边数):n“); scanf(“%d,%d“, ,建立有向图的邻接矩阵算法:,6.2.2 邻接表,邻接表是图的一种顺序存
14、储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表，再将所有点的邻接表表头放到数组中，就构成了图的邻接表。,邻接表表示中有两种结点结构:,一种是顶点表示的结点结构，它由顶点域（vertex）和指向第一条邻接边的指针域（firstedge）构成。,另一种是邻接表结点，它由邻接点域(adjvex)和指向下一条邻接边的指针域(next)构成。对于网络图边上的权值需要再增设一个存储边上权值的域（info）。,邻接表存储图的示例：,特点：,在无向图的邻接表中，顶点vi的度值=第i个链表
15、中的结点数；,在有向图中，顶点vi的出度值=第i个链表中的结点数； 顶点vi的入度值=链表中所有结点vi的个数总和。,有时，为了便于确定顶点的入度值或以顶点vi为头的弧，可以建立一个有向图的逆邻接表即:,在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点，但要判定任意两个顶点（vi 和vj）之间是否有边或弧相连，则需搜索第i个或第j个链表，因此，不及邻接矩阵方便。,邻接表表示的形式描述如下：,define MAX 最大顶点数 typedef struct node /*边表结点*/ int adjvex; /*邻接点域*/ struct node *next; /*指向下一个邻接点的指针域*/ /*若要表示边上信息，则应增加一个数据域info*/ edgenode;,t
