软件技术基础课件-第3章 算法与数据结构(四)

软件技术基础电子教案第3章算法与数据结构2/64第3章内容摘要3.1数据结构概述3.2算法的描述和分析3.3线性表3.4树和二叉树3.5图3.6查找与排序《软件技术基础》电子教案3/643.5图的主要内容•图的定义•图的存储结构•图的遍历操作•图的几个典型问题•小结《软件技术基础》电子教案4/64一、图的定义和相关概念1.定义:是由非空的顶点集合和一个描述顶点之间关系(边或者弧)的集合组成，其二元组定义为：G＝(V，E)V＝{vi|vi∈dataobject}E＝{(vi，vj)|vi，vj∈V∧P(vi，vj)}其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合，P(vi，vj)表示顶点vi和顶点vj之间有一条直接连线。集合E可以是空集，若E为空，则该图只有顶点而没有边，偶对(vi，vj)表示一条边。图的形态举例《软件技术基础》电子教案5/64AADCB图1图2更多图的相关概念B《软件技术基础》电子教案6/642.图的相关概念1)无向图:如果任意两个顶点构成的偶对(vi，vj)∈E是无序的，即顶点之间的连线是没有方向的，则称该图为无向图(Undigrpah)2)有向图:如果任意两个顶点构成的偶对vi，vj∈E是有序的，即顶点之间的连线是有方向的，则称该图为有向图(Digrpah)注意：为了区别起见，无向图的边用圆括号表示，有向图的边(或称为弧)用尖括号表示。显然在无向图中(vi，vj)=(vj，vi)，但在有向图中vi，vj≠vj，vi《软件技术基础》电子教案7/643)图中的数据元素vi称为顶点(Vertex)4)P(vi，vj)表示在顶点vi和顶点vj之间有一条直接连线。5)无向图:则称P(vi，vj)为边；边用顶点的无序偶对(v，w)来表示，称顶点v和顶点w互为邻接点，6)有向图:一般称这条连线为弧(Arc)；弧用顶点的有序偶对vi，vj来表示，有序偶对的第一个结点vi被称为始点(或弧尾Tail)，有序偶对的第二个结点vj被称为终点(或弧头Head)，若v，w是一条弧，则称顶点v邻接到w，顶点w邻接自v《软件技术基础》电子教案8/647)无向完全图:在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图(UnderetedCompleteGraph)。有n个顶点的无向完全图中，有n(n-1)/2条边。8)有向完全图:在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图(DirectedCompleteGraph)。有n个顶点的有向完全图中，有n(n-1)条边《软件技术基础》电子教案9/649)度、入度、出度:顶点的度(degree)是指依附于某顶点v的边数，通常记D(v)。在有向图中，有顶点的入度与出度的概念。顶点v的入度(Indegree)是指以顶点v为终点的弧的数目，记为ID(v)；顶点v出度(Outdegree)是指以顶点v为始点的弧的数目，记为OD(v)有D(v)=ID(v)＋OD(v)可以证明：对于具有n个顶点、e条边的图，顶点vi的度D(vi)与顶点的个数以及边的数目满足关系：niViDe1)(21《软件技术基础》电子教案10/6410)边的权、网图：如图的边或弧附带有数值信息，这种数值称为权(Weight)；每条边或弧都带权的图称为带权图或网络在应用中，权值可以有某种含义。如，在一个反映城市交通线路的图中，边上的权值可以表示该条线路的长度或者等级；对于一个电子线路图，边上的权值可以表示两个端点之间的电阻、电流或电压值；对于反映工程进度的图而言，边上的权值可以表示从前一个工程到后一个工程所需要的时间等等下图所示的G5就是一个无向网图。如果边是有方向的带权图，则就是一个有向网图。《软件技术基础》电子教案11/6411)路径:在无向图G=(V，E)中，从顶点vp到顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,vi2,…,vim=vq)，其中，(vij-1,vij)∈E(1≤j≤m)。若G是有向图，则路径也是有方向的，顶点序列满足vij-1,vij∈E(1≤j≤m)。12)路径长度：路径上边的数目。13)回路(环)：第一个顶点和最后一个顶点相同的路径。14)简单路径：序列中顶点不重复出现的路径。15)简单回路(简单环)：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。《软件技术基础》电子教案12/6416)子图：若图G=(V，E)，G'=(V'，E')，如果V'V且E'E，则称图G'是G的子图。v1v3v4v5v2V1V3V4V5V2v1v4v5v2《软件技术基础》电子教案13/6417)连通、连通图、连通分量：在无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连通的。连通图：如果图中任意两个顶点都是连通的连通分量：非连通图的极大连通子图。如何判断一个子图是极大连通子图?首先是子图；然后子图是连通的，并且连通子图含有极大顶点数；最后依附于这些顶点的边都加上。《软件技术基础》电子教案14/64BEADCF无向图BAFE连通分量1DC连通分量2《软件技术基础》电子教案15/6418)强连通图、强连通分量：强连通图：在有向图中，对图中任意一对顶点vi和vj(i≠j)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径。强连通分量：非强连通图的极大强连通子图称为。V4V3V2V1V4V3V2V1强连通分量《软件技术基础》电子教案16/6419)图的生成树(SpanningTree)：是一个极小的连通子图，包含图中全部顶点，和最少的边。n个顶点的连通图，它的生成树是由n个顶点和n-1条边组成的连通子图。如果G的一个子图G’的边数大于n-1，则G’中必定会产生回路。相反，如果G’的边数小于n-1，则G’一定不连通。20)生成森林：在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成树。这些连通分量的生成树就组成了一个非连通图的生成森林(SpanningForest)。生成树《软件技术基础》电子教案17/643.图的基本操作图的基本操作有以下几种：得到某个顶点Getvertex(G，V)找出某个顶点的第一邻接点Firstadj(G，V，W)增加一顶点UAddvertex(G，U)删除一顶点VDelvertex(G，V)，与其所有连接的边全删除增加一条边(V，U)Addedge(G，V，U)删除一条边(V，U)Deledge(G，V，U)遍历路径Travpath(G，V，U)找出所有路径Findpaths(G，V，U)最短/长路径Shortpath(G，V，U)遍历所有顶点Travvertex(G)在为这些运算写算法时，要先解决G如何在机器中存放《软件技术基础》电子教案18/64二、图的存储结构图是一种结构复杂的数据结构，图的信息包括两部分，即图中顶点的信息以及描述顶点之间的关系(边或者弧)的信息。图的存储需要实现顶点和边的信息的存储1.邻接矩阵2.邻接表3.十字链表(请自行阅读教材)4.邻接多重表(请自行阅读教材)《软件技术基础》电子教案19/641.邻接矩阵(AdjacencyMatrix)用一维数组存储图中顶点的信息，用一个二维数组表示图中各顶点之间的邻接关系信息，这个二维数组称为邻接矩阵。设图G=(V，E)有n个确定的顶点，即V={v0，v1，…，vn-1}，则表示G中各顶点相邻关系为一个n×n的矩阵，矩阵的元素为：A[i][j]=1当顶点i与j之间有边或弧时0当顶点i与j之间无边或弧时对于带权图，则邻接矩阵定义为：A[i][j]=wij当顶点i与j之间有边或弧，且权值为wij0所在的对角线元素(i=j)∞当顶点i与j之间无边或弧时下页实例《软件技术基础》电子教案20/64矩阵存储特点《软件技术基础》电子教案21/64邻接矩阵的特点：(1)无向图的邻接矩阵一定是一个对称矩阵；有向图的邻接矩阵不一定是对称矩阵(2)对于无向图，邻接矩阵的第i行(或第i列)非零元素(或非∞元素)的个数正好是第i个顶点的度TD(vi)(3)对于有向图，邻接矩阵的第i行(或第i列)非零元素(或非∞元素)的个数正好是第i个顶点的出度OD(vi)(或入度ID(vi))《软件技术基础》电子教案22/64邻接矩阵的特点：(4)易确定图中任意两个顶点之间是否有边相连；但确定图中有多少条边，须按行、列对每个元素进行检测，花费的时间代价大(5)在邻接矩阵表示法中，如果是顶点很多而边很少的图，将会表示成一个稀疏矩阵，浪费空间C实现《软件技术基础》电子教案23/64算法实现邻接矩阵#defineMaxVerNum30/*最大顶点个数*/typedefstruct{Vextypevexs[MaxVerNum]；/*顶点表*/Edgetypeedges[MaxVerNum][MaxVerNum]/*邻接矩阵，即边表*/intn，e；/*顶点数和边数*/}MGragh；/*MGragh是以邻接矩阵存储的图类型*/《软件技术基础》电子教案24/64建立有向图G的邻接矩阵存储voidCreatGraph(MGraph*G)/*建立有向图G的邻接矩阵存储*/{inti，j，k，w；charch；scanf(“%d，%d”，&(G-n)，&(G-e))；/*输入顶点数和边数*/for(i=0；iG-n；i++)scanf(“%c”，&(G-vexs[i]))；/*输入顶点信息，建立顶点表*/for(i=0；iG-n；i++)for(j=0；jG-n；j++)G-edges[i][j]=0；/*初始化邻接矩阵*/for(k=0；kG-e；k++){scanf(“%d，%d”，&i，&j)；/*输入e条边，建立邻接矩阵*/G-edges[i][j]=1；/*若加入G-edges[j][i]=1，则为无向图的邻接矩阵*/}}《软件技术基础》电子教案25/642.邻接表对图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表再将所有点的邻接表表头放到数组中，就构成了图的邻接表。其中，单链表中的结点称为表结点，每个单链表设的一个头结点称为顶点结点邻接表表示中有两种结点结构:带权图的边表结构《软件技术基础》电子教案26/64邻接表示例（无向图）注：对于无向图，第i个顶点的度为第i个链表的结点数无向图中有n个顶点、e条边，则它的邻接表需n个头结点和2e个表结点。在边稀疏(en(n-1)/2)的情况下，用邻接表表示图比邻接矩阵节省存储空间v3v2v4v1《软件技术基础》电子教案27/64v3v2v10v11v22v3∧102∧∧邻接表示例（有向图）对于有向图，第i个顶点的出度是第i个链表的结点数求第i个顶点的入度要遍历整个邻接表《软件技术基础》电子教案28/64邻接表示例：逆邻接表•若问题总对入度更关心，则可以把线性链表的表结点的数据域更改即可：由表尾改为表头：所有以头结点为表头的弧组成的线性链表。此时该邻接表称为逆邻接表。v3v2v10v11v22v3∧011∧∧邻接表的C实现《软件技术基础》电子教案29/64定义邻接表数据类型＃defineMaxVerNum30/*最大顶点数为30*/typedefstructnode{/*表结点*/intadjvex；/*邻接点域，一般是放顶点对应的序号或在表头向量中的下标*/InfoTypeInfo；/*与边(或弧)相关的信息structnode*next；/*指向下一个邻接点的指针域*/}EdgeNode；typedefstructvnode{/*顶点结点*/VertexTypevertex；/*顶点域*/EdgeNode*firstedge；/*边表头指针*/}VertexNode；typedefstruct{VertexNodeadjlist[MaxVerNum]；/*邻接表*/intn，e；/*顶点数和边数*/}ALGraph；/*ALGraph是以邻接表方式存储的图类