数据结构.第4章图及其相关算法-10-1

1第4章图及其相关算法Slide.4-1图的搜索算法是有关图问题的重要算法！图的搜索算法是有关图问题的重要算法！第4章图及其相关算法Slide.4-24.14.1图的基本概念图的基本概念4.24.2图的表示图的表示4.34.3图的搜索图的搜索((遍历遍历))4.44.4图与树的联系图与树的联系4.54.5无向图的双连通性无向图的双连通性4.64.6有向图的搜索有向图的搜索4.74.7强连通图强连通图4.84.8拓扑分类拓扑分类4.94.9关键路径关键路径4.104.10最短路径最短路径第4章图及其相关算法Slide.4-3图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)其中V={x|x某个数据对象}是顶点的有穷非空集合；E={(x,y)|x,yV}或E={x,y|x,yV}是顶点之间关系的有穷集合，也叫做边(edge)集合。定义图4.1图的基本概念第4章图及其相关算法Slide.4-4有向图若图G的每条边都有方向，则称G为有向图（Digraph)。在有向图中，有向边（也称弧）都是顶点的有序对x,y。无向图若图G的每条边都是没有方向的，则称G为无向图（UnDigraph)。在无向图中，每条边都是顶点的无序对(x,y)。V0V3V2V1G1V0V3V2V1G2V0V3V2V1G356789第4章图及其相关算法Slide.4-5若（vi，vj）是一条无向边，则称vi和vj互为邻接点（Adjacent)，或称vi与vj相邻接；若vi，vj是一条有向边，则称vi邻接到vj，或称vj邻接于vi；若将图中的每条边都赋予一个权，则称这种带权的图为网络(Network)。通常权是一个具有某种意义的数（如表示两顶点间的距离、耗费等）。第4章图及其相关算法Slide.4-6无向图中顶点v的度（Degree）是关联于该顶点的边的数目，或与该顶点相邻的顶点数目，记为D（v）。若G是有向图，则把邻接到顶点v的顶点数目或边数目称为顶点v的入度（Indegree），记为ID（v）；把邻接于顶点v的顶点数目或边数目称为顶点v的出度（Outdegree），记为OD（v）；顶点v的度则定义为该顶点的入度和出度之和，即D（v）=ID（v）+OD（v）定义结点的度V0V3V2V1G1V0V3V2V1G22第4章图及其相关算法Slide.4-7无论是有向图还是无向图，顶点数n、边数e和度数之间的关系为：e=—∑D(vi)21i=0n定义路（径）、路径长、简单路、简单环路在无向图G中，若存在一个顶点序列vp,vi1,vi2,…vim,vq，使得（vp,vi1）,（vi1,vi2）,…,（vim,vq）∈E(G)，则称顶点vp路到vq有一条路径（Path）。在有向图G中，若存在一个顶点序列vp,vi1,vi2,…vim,vq，使得有向边vp,vi1,vi1,vi2,…,vim,vq∈E(G)，则称顶点vp路到vq有一条有向路径。第4章图及其相关算法Slide.4-8简单路径若路径上各顶点v1,v2,...,vm均不互相同,则称这样的路径为简单路径。简单回路若路径上第一个顶点v1与最后一个顶点vm重合,则称这样的简单路径为回路或环。非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。第4章图及其相关算法Slide.4-9连通图与连通分量在无向图中,若从顶点vi到顶点vj有路径,则称顶点vi与vj是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。强连通图与强连通分量在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。定义图的连通性第4章图及其相关算法Slide.4-104.2.1邻接矩阵(AdjacencyMatrix)否则若i,j∈E或(i,j)∈E01A.edge[i][j]=﹣一、图的邻接矩阵表示4.2图的存储表示在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。设图A=(V,E)是一个有n个顶点的图,图的邻接矩阵是一个二维数组A.edge[n][n]，定义：第4章图及其相关算法Slide.4-110123=0101101001011010A.edge=000101010A.edge012无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。在有向图中,统计第i行1的个数可得顶点i的出度，统计第j列1的个数可得顶点j的入度。在无向图中,统计第i行(列)1的个数可得顶点i的度。第4章图及其相关算法Slide.4-12∞jiji,ji,jiji,ji,jijiji若或且若或且若,)(,)(),,(]][[0EEEEWA.edge≠≠∈∈∈∈863129542031410∞068053290A.edge[i][j]=∞∞∞二、网络的邻接矩阵二、网络的邻接矩阵／／3第4章图及其相关算法Slide.4-13#defineMaxValueInt_Max//在limits.h中#defineNumEdges50;//边条数#defineNumVertices10;//顶点个数typedefcharVertexData;//顶点数据类型typedefintEdgeData;//边上权值类型typedefstruct{VertexDatavexlist[NumVertices];//顶点表EdgeDataedge[NumVertices][NumVertices];//邻接矩阵—边表,可视为边之间的关系intn,e;//图中当前的顶点个数与边数}MTGraph;三、用邻接矩阵表示的图结构的定义第4章图及其相关算法Slide.4-14四、图的邻接矩阵构造算法voidCreateMGragh(MTGragh*G)//建立(无向)图的邻接矩阵{inti,j,k,w;scanf(%d,%d,&G→n,&G→e);//输入顶点数和边数for(i=0;iG→n;i++)//读入顶点信息，建立顶点表G→vexlist[i]=getchar();for(i=0;iG→n;i++)for(j=0;jG→n;j++)G→edge[i][j]=0;//邻接矩阵初始化for(k=0;kG→e;k++){//读入e条边建立邻接矩阵scanf(%d%d%d,&i,&j,&w);//输入边（i,j）上的权wG→edge[i][j]=w(或1);G→edge[j][i]=w（或1）;}//空间复杂性：S=O(n+n2)}//时间复杂性：T=O(n+n2+e)。当en,T=O(n2)第4章图及其相关算法Slide.4-154.2.2邻接表(AdjacencyListList)一、图的邻接表表示对于G中的每个顶点vi，把所有邻接（于）vi的顶点vj链成一个单链表（称为关于vi的邻接表）。邻接表中每个表结点都有两个域：其一是邻接点域adjvex，用以存放与vi相邻顶点的序号；其二是链域next，用来将邻接表的所有表点链在一起；另外若要表示边上的信息如（权值）,则在表结点中还应增加一个数据域cost.再为每个顶点vi的邻接表设置一个表头结点，头结点包含两个域，其一是顶点域vextex，用来存放顶点vi的信息，另一个是指针域firstedge，它是vi的邻接表的头指针。第4章图及其相关算法Slide.4-16V3V1V4V5V2G1v5v1v2v3v4314243202101^^^^^01234vertexfirstedgeadjvexnext顶点表边表无向图G1邻接表第4章图及其相关算法Slide.4-17（为了便于随机访问任意顶点的邻接表，）将所有头结点顺序存储在一个数组中,这样就构成了图的邻接表表示，(但有时为了增加对图中顶点，边数等属性的描述可将邻接表和这些属性放在一起描述图的存储结构)无向图G1邻接表V3V1V4V5V2G1v5v1v2v3v4314243202101^^^^^01234vertexfirstedgeadjvexnext顶点表边表第4章图及其相关算法Slide.4-18G2的逆邻接表V1V3V4V2G2有向图G2邻接表v1v2v3v42130^^^0123^vertexfirstedgeadjvexnext顶点表出边表v1v2v3v43002^^^^0123入边表在无向图的邻接表中，一条边（Vi，Vj）在邻接表中出现两次：一次在关于Vi的邻接表中；一次在关于Vj的邻接表中.关于顶点Vi的邻接表的结点数目为顶点Vi的度4第4章图及其相关算法Slide.4-19在有向图的邻接表中，一条边Vi，Vj在邻接表中出只现一次关于顶点Vi的邻接表中结点数目为顶点Vi的出度；在逆邻接表中关于顶点Vi的邻接表中结点数目为顶点Vi的入度。v1v2v3v42130^^^0123^vertexfirstedgeadjvexnext顶点表出边表V1V3V4V2G2第4章图及其相关算法Slide.4-20二、用邻接表表示的图结构的定义#defineNumVertices10;//顶点个数typedefcharVertexData;//顶点数据类型typedefintEdgeData;//边上权值类型typedefstructnode{//边表结点intadjvex;//邻接点域（下标）EdgeDatacost;//边上的权值structnode*next;//下一边链接指针}EdgeNode;typedefstruct{//顶点表结点VertexDatavertex;//顶点数据域EdgeNode*firstedge;//边链表头指针}VertexNode;typedefstruct{//图的邻接表VertexNodeverlist[NumVertices];intn,e;//图中当前的顶点个数与边数}AdjGraph;adjvexcostnext表结点vertexfirstedge头结点第4章图及其相关算法Slide.4-21三、邻接表的构造算法voidCreateGraph(AdjGraphG){cinG.nG.e;//输入顶点个数和边数for(inti=0;iG.n;i++){cinG.vexlist[i].vertex;//输入顶点信息G.vexlist[i].firstedge=NULL;}//边表置为空表for(i=0;ie;i++){//逐条边输入,建立边表cintailheadweight;//变量说明省了EdgeNode*p=newEdgeNode;p→adjvex=head;p→cost=weight;p→next=G.vexlist[tail].firstedge;//链入第tail号链表的前端G.vexlist[tail].firstedge=p;p=newEdgeNode;p→adjvex=tail;p→cost=weight;p→next=G.vexlist[head].firstedge;//链入第head号链表的前端G.vexlist[head].firstedge=p;}}//时间复杂度：O(2e+n)空间复杂度：有向图：S=O(e+n)无向图：S=O(2e+n)当en2时，S=O(n)第4章图及其相关算法Slide.4-22四、两种存储结构的比较在邻接矩阵中求边的数目e，必须检查整个矩阵，所耗时间是O(n2)，与边的个数e无关；而在邻接表中求边的数目e，只要对每个边表的结点个数进行计数即可求得e，所耗时间是O(e+n)。因此当en2时，采用邻接表更节省空间。在邻接矩阵中，很容易判断(Vi，Vj)和Vi，Vj是否为图的一条边，只要判断矩阵中的第i行第j列是否为非零元素即可;但在邻接表中，须扫描第i个边表，最坏情况下消耗时间O