数据结构第07章图.ppt
《数据结构第07章图.ppt》由会员分享,可在线阅读,更多相关《数据结构第07章图.ppt(251页珍藏版)》请在三一办公上搜索。
1、第七章 图,本章介绍另一种非线性数据结构 图 图:是一种多对多的结构关系,每个元素可以有零个或多个直接前趋;零个或多个直接后继;,第七章 图 7.1 图的概念 7.2 图的存储结构 7.3 图的遍历 7.4 生成树 7.5 最短路径 7.6 拓扑排序,第七 章 图,学习要点 1熟悉图的各种存储结构及其构造算法,了解实际问题的求解效率与采用何种存储结构和算法有密切联系;2熟练掌握图的两种遍历:深度优先遍历和广度优先遍历的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。树的先根遍历是一种深度优先搜索策略,树的层次遍历是一种广度优先搜索策略 3理解各种图的算法;,第七 章 图,7.1
2、 图的基本概念,一 图的概念 图的定义 图G由两个集合构成,记作G=其中V是顶点的非空有限集合,E是边的有限集合,其中边是顶点的无序对或有序对集合。,G1=V=v0,v1,v2,v3,v4 E=(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4),G1图示,无序对(vi,vj):用连接顶点vi、vj的线段表示,称为无向边;,例,G2 图示,有序对:用以vi起点、以vj为终点的有向线段表示,称为有向边或弧;称vi为弧尾,vj为弧头,无向图:在图G中,若所有边是无向边,则称G为无向图;有向图:在图G中,若所有边是有向边,则称G为有向图;混和图:在图G中,既有
3、无向边也有有向边,则称G为混合图;,7.1 图的基本概念,G2=V=v0 v1,v2,v3E=,图的应用举例例1 交通图(公路、铁路)顶点:地点 边:连接地点的公路 交通图中的有单行道双行道,分别用有向边、无向边表示;例2 电路图 顶点:元件 边:连接元件之间的线路例3 通讯线路图 顶点:地点 边:地点间的连线例4 各种流程图 如产品的生产流程图 顶点:工序 边:各道工序之间的顺序关系,7.1 图的基本概念,1 邻接点及关联边 邻接点:边的两个顶点,v、u互为邻接点 关联边:若边e=(v,u),则称顶点v、u 关联边e2 顶点的度、入度、出度 在无向图中:顶点V的度=与V相关联的边的数目 在有
4、向图中:顶点V的出度=以V为起点有向边数 顶点V的入度=以V为终点有向边数 顶点V的度=V的出度+V的入度 设图G的顶点数为n,边数为e 图的所有顶点的度数和=2*e(每条边对图的所有顶点的度数和“贡献”2度),e,图的基本术语,7.1 图的基本概念,完全图、权、网 有向完全图具有n(n-1)条弧的n个顶点的有向图称为 无向完全图有n(n-1)/2 条边的n个顶点的无向图称为 权与图的边或弧相关的数叫 网带权的图叫,7.1 图的基本概念,4 路径、回路 路径路径是顶点的序列V=Vi0,Vi1,Vin,满足(Vij-1,Vij)E 或 E,(1jn)路径长度沿路径边的数目或沿路径各边权值之和 回
5、路第一个顶点和最后一个顶点相同的路径叫 在图G1中,V0,V1,V2,V3 是V0到V3的路径;V0,V1,V2,V3,V0是回路;在图G2中,V0,V2,V3 是V0到V3的路径;V0,V2,V3,V0是回路;,无向图G1,有向图G2,例,7.1 图的基本概念,5 简单路径和简单回路 在一条路径中,序列中顶点不重复出现的路径称为简单路径;由简单路径组成的回路称为简单回路;在图G1中,V0,V1,V2,V3 是简单路径;在图G2中,V0,V2,V3,V0是简单回路;,无向图G1,有向图G2,例,7.1 图的基本概念,6 连通图(强连通图)在无(有)向图G=中,若对任何两个顶点 v、u 都存在从
6、v 到 u 的路径,则称G是连通图(强连通图),7.1 图的基本概念,非连通图,连通图,强连通图,非强连通图,7 子图 设有两个图G=(V,E)、G1=(V1,E1),若V1 V,E1 E,则称 G1是G的子图;例(b)、(c)是(a)的子图,(a),(b),(c),7.1 图的基本概念,8 连通分量(强连通分量)无向图G 的极大连通子图称为G的连通分量 极大连通子图意思是:该子图是 G 连通子图,将G 的任何不在该子图中的顶点加入,子图不再连通;,连通分量,非连通图,7.1 图的基本概念,有向图D 的极大强连通子图称为D 的强连通分量 极大强连通子图意思是:该子图是D强连通子图,将D的任何不
7、在该子图中的顶点加入,子图不再是强连通的;,9 生成树 包含无向图G 所有顶点的的极小连通子图称为G 的生成树 极小连通子图意思是:该子图是G 的连通子图,在该子图中删除任何一条边,子图不再连通,若T是G 的生成树当且仅当T 满足如下条件 T是G 的连通子图 T包含G 的所有顶点 T中无回路,连通图 G1,G1的生成树,7.1 图的基本概念,T1是G1的生成树,图G1中:V(G1)=1,2,3,4,5,6 E(G1)=,图G2中:V(G2)=1,2,3,4,5,6,7 E(G1)=(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7),3,4,1,3,1,0,路径:
8、1,2,3,5,6,3路径长度:简单路径:1,2,3,5,6,3,1 3,5,6,3,路径:1,2,5,7,6,5,2,3路径长度:7简单路径:回路:简单回路:,5,1,2,3,5,6,回路:,简单回路:,1,2,5,7,6,1,2,3,1,1,2,5,7,6,5,2,1,连通图,强连通图,非连通图连通分量,7.2 图的存储结构多重链表,邻接矩阵表示顶点间相联关系的矩阵定义:设G=(V,E)是有n1个顶点的图,G的邻接矩阵A是具有以下性质的n阶方阵,数组表示法,特点:无向图的邻接矩阵对称,可压缩存储;有n个顶点的无向图需存储空间为n(n+1)/2有向图邻接矩阵不一定对称;有n个顶点的有向图需存
9、储空间为n无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行(或第i列)元素之和有向图中,顶点Vi的出度是A中第i行元素之和顶点Vi的入度是A中第i列元素之和,检测图中的总边数。扫描整个数组A,统计出数组中非0元素的个数。无向图的总边数为非0元素个数的一半,而有向图的总弧数为非0元素个数;,网的邻接矩阵可定义为:,其中 wij表示(vi,vj)边上的权值;表示结点vi和vj之间没有边相连。,若G是一个带权值的图,即为网络,则其邻接矩阵可定义为:,带权有向图的邻接矩阵,带权无向图的邻接矩阵,邻接矩阵表示法中图的存储表示#define n 6/*图的顶点数*/#define e 8/*图的边数*
10、/typedef char vextype;/*顶点的数据类型*/typedef float adjtype;/*权值类型*/typedef struct vextype vexsn;adjtype arcsnn;graph;,2,1,4,3,5,B,A,D,C,E,2,1,5,3,4,0,=,80,70,80,70,50,40,50,30,40,20,30,20,arcs,6,20,30,50,40,70,80,邻接矩阵表示法中无向网络的建立算法CREATEGRAPH(graph*ga)int i,j,k;float w;for(i=0;ivexsigetchar();/*读入顶点信息,建立
11、顶点表*/for(i=0;iarcsij0;/*邻接矩阵初始化*/for(k=0;karcsijw;ga-arcsjiw;,容易实现图的操作,如:求某顶点的度、判断顶点之间是否有边(弧)、找顶点的邻接点等等。n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。对稀疏图而言尤其浪费空间。,邻接矩阵法优点:,邻接矩阵法缺点:,注:用两个数组分别存储顶点表和邻接矩阵#define INFINITY INT_MAX/最大值#define MAX_VERTEX_NUM 20/假设的最大顶点数typedef enum DG,DN,AG,AN GraphKind;/有向/无向图,有向/无向网type
12、def struct ArcCell/弧(边)结点的定义 VRType adj;/顶点间关系,无权图取1或0;有权图取权值类型 InfoType*info;/该弧相关信息的指针ArcCell,AdjMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM;typedef struct/图的定义VertexType vexs MAX_VERTEX_NUM;/顶点表,用一维向量即可AdjMatrix arcs;/邻接矩阵int Vernum,arcnum;/顶点总数,弧(边)总数GraphKind kind;/图的种类标志Mgraph;,图的邻接矩阵存储表示(参见教材P161),对
13、于n个顶点的图或网,空间效率=O(n2),Status CreateUDN(Mgraph/CreateUDN,例:用邻接矩阵生成无向网的算法(参见教材P162),对于n个顶点e条弧的网,建网时间效率=O(n2+n+e*n),邻接表(Adjacency List),在邻接表中,对图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点vi的边。每个结点由三个域组成:,邻接点域,指示与顶点vi邻接的点在图中的位置,链域,指示下一条边或弧的结点,数据域,存储与边或弧相关的信息,如权值,无权图一般不用,每个单链表附设一个头结点。在表头结点中,除了设有链域指向链表中第一个结点之外,还设有存储顶点v
14、i的名或其它有关信息的数据域。,数据域,链域,表头结点可以链相接,通常以顺序结构的形式存储,以便随机访问任一顶点的链表。,存放与该顶点相关的信息,指示第一条依附于该顶点的边的指针,图的邻接表存储表示,#define MAX_VERTEX_NUM 20typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置 struct ArcNode*nextarc;/指向下一条弧的指针 InfoType*info;/该弧相关信息的指针 ArcNode;typedef struct VNode VertexType data;/顶点信息 ArcNode*firstarc;/
15、指向第一条依附该顶点的弧 VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数 int kind;/图的种类标志 ALGraph;,无向图的邻接表,在无向图的邻接表中,顶点vi的度恰为第i个链表中的结点数。,有向图的邻接表(出边表),有向图中对每个结点建立以Vi为尾的弧的单链表顶点:用一维数组存储(按编号顺序)以同一顶点为起点的弧:用线性链表存储,有向图的逆邻接表(入边表),有向图中对每个结点建立以Vi为头的弧的单链表顶点:用一维数组存储(按编号顺序)以同一顶点为终点的
16、弧:用线性链表存储,在有向图中,第i 个链表中的结点个数只是顶点vi的出度,为求入度,必须遍历整个邻接表。在所有链表中其邻接点域的值为i 的结点的个数是顶点vi的入度。在有向图的邻接表中,第 i 个边链表链接的边都是顶点 i 发出的边。也叫做出边表。在有向图的逆邻接表中,第 i 个边链表链接的边都是进入顶点 i 的边。也叫做入边表。,该结点表示边(Vi Vj),其中的2是Vj在一维数组中的位置,邻接表,特点无向图中顶点Vi的度为第i个单链表中的结点数有向图中顶点Vi的出度为第i个单链表中的结点个数顶点Vi的入度为整个单链表中邻接点域值是i的结点个数判定两顶点v,u是否邻接:要看v对应线性链表中
17、有无对应的结点u在G中增减边:要在两个单链表插入、删除结点;若无向图中有n个顶点、e条边,则它的邻接表需n个头结点和2e个表结点。可见,G占用存储空间与G的顶点数、边数均有关;适用于边稀疏的图。,带权图的邻接表,多一个info域,相反,已知某网的邻接(出边)表,可以画出该网络。,80,64,1,2,5,当邻接表的存储结构形成后,图便唯一确定!,邻接表的缺点:,邻接表的优点:,空间效率高;容易寻找顶点的邻接点;,判断两顶点间是否有边或弧,需搜索两结点对应的单链表,没有邻接矩阵方便。,讨论:邻接表与邻接矩阵有什么异同之处?,1.联系:邻接表中每个链表对应于邻接矩阵中的一行,链表中结点个数等于一行中
18、非零元素的个数。2.区别:对于任一确定的无向图,邻接矩阵是唯一的(行列号与顶点编号一致),但邻接表不唯一(链接次序与顶点编号无关)。邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。3.用途:邻接矩阵多用于稠密图的存储(e接近n(n-1)/2);而邻接表多用于稀疏图的存储(en2),三、十字链表(自学)(适用于有向图)四、邻接多重表(自学)(适用于无向图),有向图的十字链表表示法,无向图的邻接多重表表示法,7.3 图的遍历,从图中某个顶点出发游历图,访遍图中其余顶点,并且使图中的每个顶点仅被访问一次。这一过程就称为图的遍历。图的遍历比树的遍历要复杂得多。因为图的任一顶点都可
19、能和其余的顶点相邻接;因此在访问了某个顶点后,可能沿着某条路径搜索后,又回到该顶点上。为了避免同一顶点被访问多次,在遍历图的过程中,必须记下每个已访问过的顶点。,为了避免重复访问,可设置一个标志顶点是否被访问过的辅助数组 visited 0.n-1,它的初始状态为 0,在图的遍历过程中,一旦某一个顶点 i 被访问,就立即让 visited i 为 1,防止它被多次访问。,通常有两条遍历图的路径:深度优先搜索、广度优先搜索,深度优先搜索DFS(Depth_First Search),算法思想:假设初始状态是图中所有顶点未曾被访问,则可从图中某个顶点V0 出发,访问此顶点,然后依次从V0的各个未被
20、访问的邻接点出发深度优先搜索遍历图,直至图中所有和V0有路径相通的顶点都被访问到,若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。,图的深度优先搜索类似于树的前序遍历,深度优先搜索的示例,由上得到顶点访问序列为:v1、v2、v4、v8、v5、v3、v6、v7,显然这是一个递归的过程,为了在遍历过程中便于区分顶点是否已被访问,需附设访问数组visited 0.n-1,数组元素的初始值为false;在遍历过程中,一旦某一个顶点 i 被访问,则置 visited i 为 true。,例2:,v2 v1 v3 v5,DFS 结果,v4
21、v6,起点,深度优先搜索(遍历)步骤:,详细归纳:在访问图中某一起始顶点 v 后,由 v 出发,访问它的任一邻接顶点 w1;再从 w1 出发,访问与 w1邻接但还未被访问过的顶点 w2;然后再从 w2 出发,进行类似的访问,如此进行下去,直至到达所有的邻接顶点都被访问过的顶点 u 为止。,简单归纳:访问起始点 v;若v的第1个邻接点没访问过,深度遍历此邻接点;若当前邻接点已访问过,再找v的第2个邻接点重新遍历。,接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过
22、程,直到连通图中所有顶点都被访问过为止。,Boolean visitedMAX;/访问标志数组 Status(*VisitFunc)(int v);/函数变量/以上两个变量都是全局变量void DFSTraverse(Graph G,Status(*Visit)(int v)/对图G作深度优先遍历。VisitFunc=Visit;for(v=0;vG.vexnum;+v)visitedv=FALSE;/访问标志数组初始化 for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);/对尚未访问的顶点调用DFS,图的深度优先搜索算法,void DFS(Graph G,i
23、nt v)/从第v个顶点出发递归地深度优先遍历图G。visitedv=TRUE;/访问标记置为true VisitFunc(v);/访问第v个顶点 for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/对v的尚未访问的邻接顶点w/递归调用DFS,算法时间复杂度分析,从上述算法可知,在遍历过程中,对图中每个顶点至多调用一次DFS函数;因为一旦某个顶点被标志成已被访问,就不再从它出发进行搜索。因此,对图的遍历实际上是对每个顶点查找其邻接点的过程,耗费的时间取决于所用的存储结构。,如果用邻接表表示图,沿 First
24、out link 链可以找到某个顶点 v 的所有邻接顶点 w。由于总共有 2e 个边结点,所以扫描边的时间为O(e)。而且对所有顶点递归访问1次,所以遍历图的时间复杂性为O(n+e)。如果用邻接矩阵表示图,则查找每一个顶点的所有的边,所需时间为O(n),则遍历图中所有的顶点所需的时间为O(n2)。,广度优先搜索BFS(Breadth_First Search),图的广度优先搜索类似于树的按层次遍历过程,算法思想:从图中的某个顶点V0出发,并在访问此顶点之后依次访问V0的所有未被访问过的邻接点,之后按这些顶点被访问的先后次序依次访问它们的邻接点,直至图中所有和V0有路径相通的顶点都被访问到。若此
25、时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。,广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有往回退的情况。因此,广度优先搜索不是一个递归的过程,其算法也不是递归的。,广度优先搜索的示例,由上得到顶点访问序列为:v1、v2、v3、v4、v5、v6、v7、v8,为了实现对图的逐层访问,需要在算法中使用一个队列,以记忆正在访问的这一层和上一层的顶点,以便于向下一层访问。为避免重复访问,还需要一个辅助数组 visited 0.n-1,给被访问过的顶点加标记。,例2:,v3,BFS 结果,v4 v5
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 07 章图

链接地址:https://www.31ppt.com/p-6578907.html