chap7图1.ppt

第七章第七章 图图四类基本结构：四类基本结构：1.1.线性结构线性结构2.2.树形结构树形结构3.3.图状结构图状结构 4.4.集集 合合数据结构数据结构 第七章第七章 图图7.1图的定义与基本术语图的定义与基本术语7.2图的存储结构图的存储结构7.3图的遍历图的遍历7.4图的应用图的应用生成树生成树拓扑排序拓扑排序关键路径关键路径最短路径最短路径本章主要内容本章主要内容数据结构数据结构 第七章第七章 图图7.1 图的定义与基本术语图的定义与基本术语数据结构数据结构 第七章第七章 图图图图是由是由顶点非空集合顶点非空集合V和和两个顶点之间两个顶点之间关系的关系的集合集合R构成的数据结构构成的数据结构Graph=(V,R)1.图的定义图的定义:其中其中:V=|vDataObjectR=VRVR=|P(v,w)且且(v,wV)表示从表示从v到到w的一条弧，的一条弧，并称并称v为弧尾，为弧尾，w为弧头。为弧头。P(v,w)定义了弧定义了弧的意义或信息的意义或信息,表示从表示从v到到w的一条单向通道。的一条单向通道。数据结构数据结构 第七章第七章 图图图的抽象数据类型定义图的抽象数据类型定义ADTGraph数据对象数据对象V：数据关系数据关系R基本操作：基本操作：1.CreatGraph(G);2.DestroyGraph(G);3.LocateVertex(G,v);4.GetVertex(G,i);5.InsertVertex(G,u);ADTGraphR=VRVR=|P(v,w)(v,wV)一一个个集集合合，该该集集合合中中的的所所有有元元素素具具有有相同的特性。相同的特性。了了解解各各种种操操作作的功能即可的功能即可数据结构数据结构 第七章第七章 图图有向图：有向图：由由顶点集顶点集和和弧集弧集构成的图为有向图。构成的图为有向图。例如例如:ABCDE其中其中顶点集顶点集V1=A,B,C,D,E关系集关系集VR1=,在在有有向向图图中中，若若表表示示从从x到到y的的一一条条弧，并称弧，并称x为为弧尾弧尾，y为为弧头弧头。“弧弧”是有方向的是有方向的数据结构数据结构 第七章第七章 图图无向图：无向图：由由顶点集顶点集和和边集边集构成的图为无向图。构成的图为无向图。例如例如:其中其中顶点集顶点集V1=A,B,C,D,E,F关系集关系集VR1=(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)在图中，若在图中，若 VR必有必有 VR,则称则称(x,y)为顶点为顶点x和顶点和顶点y之间存在一条之间存在一条边边。“边边”是无方向的是无方向的=ABCDEF数据结构数据结构 第七章第七章 图图网、子图网、子图完全图、稀疏图、稠密图完全图、稀疏图、稠密图邻接点、度、入度、出度邻接点、度、入度、出度路径、路径长度、简单路径、简单回路路径、路径长度、简单路径、简单回路连通图、连通分量、连通图、连通分量、强连通图、强连通分量强连通图、强连通分量生成树、生成森林生成树、生成森林2.名词和基本术语名词和基本术语:数据结构数据结构 第七章第七章 图图有向网：有向网：有向图有向图中的中的弧弧带权带权后的图称作后的图称作有向网有向网。无向网：无向网：无向图无向图中的中的边边带权带权后的图称作后的图称作无向网无向网。ABCDE1537211192ABCDEF1579193221有向网有向网无向网无向网2.名词和基本术语名词和基本术语:数据结构数据结构 第七章第七章 图图2.名词和基本术语名词和基本术语:例如例如:子图：子图：设图设图G=(V,VR)和图和图G=(V,VR),且且VV,VRVR,则称则称G 为为G的的子图子图ABCDEABCDADE数据结构数据结构 第七章第七章 图图无向完全图：无向完全图：含含e=n(n-1)/2条边的无向图条边的无向图。有向完全图：有向完全图：含含e=n(n-1)条弧的有向图条弧的有向图。2.名词和基本术语名词和基本术语:假设图中有假设图中有n个顶点个顶点,e条边条边,则则若边或弧的个数若边或弧的个数enlogn，则称作，则称作稀疏图稀疏图，否则称作否则称作稠密图稠密图数据结构数据结构 第七章第七章 图图2.名词和基本术语名词和基本术语:对于对于无向图，若无向图，若顶点顶点x和和y之间存在一条边之间存在一条边(x,y),则称顶点则称顶点x和和y互为互为邻接点邻接点,称边称边(x,y)依附于依附于顶顶点点x和和y或边或边(x,y)与顶点与顶点x和和y相关联相关联。与顶点与顶点x关联的边的数目关联的边的数目定义为定义为x的的度（度（TD）。例如例如:TD(B)=？TD(A)=？ABCDEF23数据结构数据结构 第七章第七章 图图2.名词和基本术语名词和基本术语:对于对于有向图，若有向图，若顶点顶点x和和y之间存在一条弧之间存在一条弧,则称顶点则称顶点x和和y互为互为邻接点邻接点,称弧称弧与顶点与顶点x和和y相关联相关联。例如例如:OD(B)=？ID(B)=？21以以x为为尾尾的弧的数目定义为的弧的数目定义为x的的出度出度(OD)以以x为为头头的弧的数目定义为的弧的数目定义为x的的入度入度(ID)。出度出度+入度入度=该顶点的度（该顶点的度（TD）ABCDETD(B)=？3数据结构数据结构 第七章第七章 图图2.名词和基本术语名词和基本术语:设图设图G=(V,VR)中的中的u=vi,0,vi,1,vi,m=w顶点序列中顶点序列中,有有(vi,j-1,vi,j)VR1jm,则称则称从顶点从顶点u到顶点到顶点w之间存在一条之间存在一条路径路径。路径上边的路径上边的数目称作数目称作路径长度路径长度，有向图的有向图的路径也是路径也是有向的。有向的。路径路径:A,E,C,D,B,C,D路径长度为路径长度为:？ABCDE6例如例如:数据结构数据结构 第七章第七章 图图2.名词和基本术语名词和基本术语:回路回路:首尾顶点相同的路径。首尾顶点相同的路径。ABCDEB,C,D,BA,E,C,D,B,C,D,A简单路径简单路径:顶点不重复的路径。顶点不重复的路径。A,E,C,D简单回路简单回路:中间顶点不重中间顶点不重的回路的回路A,E,C,D,A数据结构数据结构 第七章第七章 图图连通图：连通图：若若无向图无向图G中中任意两个顶点之间都任意两个顶点之间都 有路径相通有路径相通。例如例如:ABCDEF连通分量连通分量:若无向图为非连通图，则图中各个若无向图为非连通图，则图中各个 极大连通子图极大连通子图称作此图的称作此图的连通分量。连通分量。ABCDEFABCDEF2.名词和基本术语名词和基本术语:注注:1.任任何何连连通通图图的的连连通通分分量量只只有有一一个个,即即其其自自身身2.非连通图的无向图有多个连通分量非连通图的无向图有多个连通分量数据结构数据结构 第七章第七章 图图强连通图强连通图:若若有向图有向图,若任意两个顶点之间若任意两个顶点之间 都存在一条有向路径。都存在一条有向路径。例如例如:强连通分量强连通分量:若有向图不是强连通图，则若有向图不是强连通图，则图中各个图中各个 极大强连通子图极大强连通子图称作它的称作它的强连通分量强连通分量。BACD2.名词和基本术语名词和基本术语:注注:1.强连通图的强连通分量只有一个强连通图的强连通分量只有一个,即其自身即其自身2.非强连通图的有向图有多个强连通分量非强连通图的有向图有多个强连通分量n个顶点的强连通图至少有个顶点的强连通图至少有？条弧条弧 BACDBACDn数据结构数据结构 第七章第七章 图图生成树：生成树：假设一个假设一个连通图连通图有有n个顶点和个顶点和e条条边边,其中其中n-1条边和条边和n个顶点构成一个个顶点构成一个极小极小连通子图连通子图,称该极小连通子图为此连通图的称该极小连通子图为此连通图的生生成树成树。2.名词和基本术语名词和基本术语:BACDFEBACDFE数据结构数据结构 第七章第七章 图图生成森林：生成森林：对对非连通图非连通图，则称由各个连通分量，则称由各个连通分量的生成树的集合为此非连通图的的生成树的集合为此非连通图的生成森林生成森林。2.名词和基本术语名词和基本术语:ABCDEFABCDEF数据结构数据结构 第七章第七章 图图7.2 图的存储结构图的存储结构数据结构数据结构 第七章第七章 图图图的存储方式图的存储方式一、图的数组一、图的数组(邻接矩阵邻接矩阵)存储表示存储表示二、二、图的邻接表存储表示图的邻接表存储表示三、三、有向图的十字链表存储表示有向图的十字链表存储表示 四、四、无向图的邻接多重表存储表示无向图的邻接多重表存储表示数据结构数据结构 第七章第七章 图图一、图的数组一、图的数组(邻接矩阵邻接矩阵)存储表示存储表示定义定义:矩阵的元素为矩阵的元素为一维数组：一维数组：二维数组：二维数组：用于存储顶点信息。用于存储顶点信息。用于存储图中顶点之间用于存储图中顶点之间关联关系关联关系Aij=1若若或（或（vi,vj)VR0反之反之CBADE无向图无向图TD(Vi):对对称称矩矩阵阵0000000000000000000000000EDCBAEDCBA第第i行行非零元素的个数，或非零元素的个数，或第第i列列非零元素的个数非零元素的个数邻接矩阵邻接矩阵1111111111数据结构数据结构 第七章第七章 图图一、图的数组一、图的数组(邻接矩阵邻接矩阵)存储表示存储表示定义定义:矩阵的元素为矩阵的元素为一维数组：一维数组：二维数组：二维数组：用于存储顶点信息。用于存储顶点信息。用于存储图中顶点之间用于存储图中顶点之间关联关系关联关系Aij=1若若或（或（vi,vj)VR0反之反之OD(Vi):ID(Vi):非非对对称称矩矩阵阵0001100000000110DCBADCBA第第i行行非零元素的个数非零元素的个数第第i列列非零元素的个数非零元素的个数邻接矩阵邻接矩阵BACD有向图有向图数据结构数据结构 第七章第七章 图图一、图的数组一、图的数组(邻接矩阵邻接矩阵)存储表示存储表示定义定义:矩阵的元素为矩阵的元素为一维数组：一维数组：二维数组：二维数组：用于存储顶点信息。用于存储顶点信息。用于存储图中顶点之间用于存储图中顶点之间关联关系关联关系Aij=1若若或（或（vi,vj)VR0反之反之OD(Vi):ID(Vi):非非对对称称矩矩阵阵0001100000000110DCBADCBA第第i行行非零元素的个数非零元素的个数第第i列列非零元素的个数非零元素的个数邻接矩阵邻接矩阵BACD有向图有向图数据结构数据结构 第七章第七章 图图Aij=1若若或（或（vi,vj)VR0反之反之一、图的数组一、图的数组(邻接矩阵邻接矩阵)存储表示存储表示定义定义:矩阵的元素为矩阵的元素为一维数组：一维数组：二维数组：二维数组：用于存储顶点信息。用于存储顶点信息。用于存储图中顶点之间用于存储图中顶点之间关联关系关联关系邻接矩阵邻接矩阵无向网无向网BAEFDC1943321111465616wij33419331411214146665116516192116FEDCBAFEDCBA对对称称矩矩阵阵数据结构数据结构 第七章第七章 图图Aij=Wij若若或（或（vi,vj)VR反之反之一、图的数组一、图的数组(邻接矩阵邻接矩阵)存储表示存储表示定义定义:矩阵的元素为矩阵的元素为一维数组：一维数组：二维数组：二维数组：用于存储顶点信息。用于存储顶点信息。用于存储图中顶点之间用于存储图中顶点之间关联关系关联关系邻接矩阵邻接矩阵2171123915EDCBAEDCBAABCDE1591173221有向网有向网非非对对称称矩矩阵阵数据结构数据结构 第七章第七章 图图.存储空间存储空间.便于运算便于运算无向图无向图:n(n-1)/2有向图有向图(网网):n2无向图无向图:TD(vi)=Aijj=1n有向图有向图(网网):一、图的数组一、图的数组(邻接矩阵邻接矩阵)存储表示存储表示特点：特点：OD(vi)=Aijj=1nID(vi)=Ajij=1n数据结构数据结构 第七章第七章 图图一、图的数组一、图的数组(邻接矩阵邻接矩阵)存储表示存储表示#defineMAX20typedefenumDG,DN,UDG,UDNGraphKind;typedefcharVertexData;typedefArcNodeintadj;OtherInfoinfo;ArcNode;typedefstructArcNodearcsMAXMAX;intvernum,arcnum;GraphKindkind;MGraph;VertexDatavertexMAX;数据结构数据结构 第七章第七章 图图一、图的数组一、图的数组(邻接矩阵邻接矩阵)创建函数创建函数操作步骤：操作步骤：1.输入各顶点输入各顶点2.邻接矩阵的初始化邻接矩阵的初始化(图是图是0，网是，网是INFINITY)3.创建边或弧创建边或弧4.确定顶点确定顶点v1,v2的位置的位置i,jn有向图有向图:n有向网有向网:n无向图无向图:n无向网无向网:G.arcsij.adj=1;G.arcsij.adj=weight;G.arcsij.adj=1;G.arcsji.adj=1;G.arcsij.adj=weight;G.arcsji.adj=weight;数据结构数据结构 第七章第七章 图图一、图的数组一、图的数组(邻接矩阵邻接矩阵)创建函数创建函数voidCreatDG(MGraph&G)inti,j,k;VertexDatav1,v2;scanf(%d%d,&G.vernum,&G.arcnum);flushall();printf(pleaseinputthevertex:);for(i=0;iG.vernum;i+)scanf(%c,&G.vertexi);for(i=0;iG.vernum;i+)for(j=0;jG.vernum;j+)G.arcsij.adj=0;/*创建边创建边*/数据结构数据结构 第七章第七章 图图一、图的数组一、图的数组(邻接矩阵邻接矩阵)创建函数创建函数/*创建边创建边*/for(k=0;kG.arcnum;k+)flushall();printf(pleaseinputv1,v2:);scanf(%c%c,&v1,&v2);i=Locate(G,v1);j=Locate(G,v2);G.arcsij.adj=1;数据结构数据结构 第七章第七章 图图一、图的数组一、图的数组(邻接矩阵邻接矩阵)打印函数打印函数voidOutPut(MGraphG)inti,j;for(i=0;iG.vernum;i+)printf(t%c,G.vertexi);for(i=0;iG.vernum;i+)printf(n%ct,G.vertexi);for(j=0;jG.vernum;j+)printf(%dt,G.arcsij.adj);printf(n);数据结构数据结构 第七章第七章 图图一、图的数组一、图的数组(邻接矩阵邻接矩阵)练习：练习：1.求出图求出图G中每个结点的中每个结点的入度；入度；2.求出图求出图G中每个结点的中每个结点的出度；出度；3.判断图判断图G中中是否存在边是否存在边v1,v2。数据结构数据结构 第七章第七章 图图一、图的数组一、图的数组(邻接矩阵邻接矩阵)1.求结点的求结点的入度、出度入度、出度voidDegreeDG(MGraphG,intod,intid)inti,j;for(i=0;iG.vernum;i+)for(j=0;jG.vernum;j+)if(G.arcsij.adj!=0)odi+;for(j=0;jG.vernum;j+)for(i=0;iG.vernum;i+)if(G.arcsij.adj!=0)idj+;odi=0;idj=0;数据结构数据结构 第七章第七章 图图一、图的数组一、图的数组(邻接矩阵邻接矩阵)3.判断判断是否存在边是否存在边v1,v2intIsExist(MGraphG,VertexDatav1,VertexDatav2)inti,j;i=Locate(G,v1);j=Locate(G,v2);if(G.arcsij.adj!=0)return1;elsereturn0;数据结构数据结构 第七章第七章 图图.表头结点表头结点.表结点表结点表头结点：表头结点：所有表头结点以顺序结构存储。所有表头结点以顺序结构存储。边表：边表：对图中每个顶点建立一个单链表，第对图中每个顶点建立一个单链表，第i i个个单链表中的结点表示依附于顶点单链表中的结点表示依附于顶点vi i的边。的边。图图网网二、二、图的邻接图的邻接表表示法表表示法datafirstarcadjnextarcadjinfonextarc数据结构数据结构 第七章第七章 图图二、二、图的邻接图的邻接表表示法表表示法无向图无向图CBADE54321EDCBA241352451323数据结构数据结构 第七章第七章 图图二、二、图的邻接图的邻接表表示法表表示法4321DCBA23144321DCBA4131可见，在有向图的邻可见，在有向图的邻接表中不易找到接表中不易找到以该以该顶点为弧头顶点为弧头的弧。的弧。邻邻接接表表逆逆邻邻接接表表BACD有向图有向图数据结构数据结构 第七章第七章 图图二、二、图的邻接图的邻接表表示法表表示法54321EDCBA21533421113215927ABCDE1591173221有向网有向网数据结构数据结构 第七章第七章 图图二、二、图的邻接图的邻接表表示法表表示法#defineMAX20#defineenumDG,DN,UDG,UDNGraphKind;typedefstructArcNodeintadj;structArcNode*nextarc;OtherInfoinfo;ArcNode;typedefstructVertexNodeVertexDatadata;structArcNode*firstarc;VertexNode;typedefstructVertexNode vertexMAX;int vernum,arcnum;GraphKindkind;ALGraph;datafirstarcadjinfonextarc数据结构数据结构 第七章第七章 图图一、图的邻接表一、图的邻接表创建函数创建函数操作步骤：操作步骤：1.输入各顶点输入各顶点2.邻接表的初始化邻接表的初始化(表头数组的初始化表头数组的初始化)3.创建边或弧创建边或弧4.确定顶点确定顶点v1,v2的位置的位置i,jn有向图有向图或或有向网有向网:n无向图无向图或或无向网无向网:开辟空间，在开辟空间，在G.vertexi连接结点连接结点;开辟空间，在开辟空间，在G.vertexi连接结点连接结点;开辟空间，在开辟空间，在G.vertexj连接结点连接结点;数据结构数据结构 第七章第七章 图图一、图的邻接表一、图的邻接表创建函数创建函数voidCreatDG(ALGraph&G)inti,j,k;VertexDatav1,v2;ArcNode*s,*p;scanf(%d%d,&G.vernum,&G.arcnum);flushall();printf(pleaseinputthevertex:);for(i=1;i=G.vernum;i+)scanf(%c,&G.vertexi.data);G.vertexi.firstarc=NULL;/*创建边创建边*/数据结构数据结构 第七章第七章 图图一、图的邻接表一、图的邻接表创建函数创建函数for(k=1;kadj=j;s-nextarc=NULL;/*插入结点插入结点s*/数据结构数据结构 第七章第七章 图图一、图的邻接表一、图的邻接表创建函数创建函数for(k=1;kadjj)s-nextarc=p;G.vertexi.firstarc=s;elsewhile(p-nextarc&p-nextarc-adjnextarc;s-nextarc=p-nextarc;p-nextarc=s;数据结构数据结构 第七章第七章 图图一、图的邻接表一、图的邻接表打印函数打印函数voidOutPutDG(ALGraphG)inti;ArcNode*p;for(i=1;iadj);p=p-nextarc;printf(n);数据结构数据结构 第七章第七章 图图一、图的邻接表一、图的邻接表练习：练习：1.求出图求出图G中每个结点的中每个结点的入度；入度；2.求出图求出图G中每个结点的中每个结点的出度；出度；3.判断图判断图G中中是否存在边是否存在边v1,v2。数据结构数据结构 第七章第七章 图图一、图的邻接表一、图的邻接表1.求结点的求结点的入度、出度入度、出度voidDegree(ALGraphG,intod,intid)inti,j;ArcNode*p;for(i=1;i=G.vernum;i+)odi=idi=0;for(i=1;iadj;idj+;p=p-nextarc;p=G.vertexi.firstarc;数据结构数据结构 第七章第七章 图图一、图的邻接表一、图的邻接表3.判断判断是否存在边是否存在边v1,v2int IsExist(ALGraph G,VertexData v1,VertexDatav2)inti,j;ArcNode*p;i=Locate(G,v1);j=Locate(G,v2);p=G.vertexi.firstarc;while(p&p-adj!=j)p=p-nextarc;if(p=NULL)return0;elsereturn1;数据结构数据结构 第七章第七章 图图特点：特点：二、二、图的邻接图的邻接表表示法表表示法无向图无向图:TD(vi)=第第i个单链表上结点的个数个单链表上结点的个数有向图有向图(网网):OD(vi)=第第i个单链表上结点的个数个单链表上结点的个数ID(vi)扫描整个邻接表扫描整个邻接表逆邻接表逆邻接表.存储空间存储空间.便于运算便于运算无向图无向图:n+2e有向图有向图(网网):n+e数据结构数据结构 第七章第七章 图图顶点的度顶点的度有向图有向图顶点的度顶点的度无向图无向图适宜存储适宜存储存储表示存储表示邻接表邻接表邻接矩阵邻接矩阵三三.图的两种存储结构比较图的两种存储结构比较 第第i个单链表上结个单链表上结点的个数点的个数:OD(Vi)采用邻接矩阵比采用邻接矩阵比邻接表更方便邻接表更方便第第i行行:OD(Vi),第第i列列:ID(Vi),TD(Vi)=ID(Vi)+OD(Vi)第第i个单链表上结个单链表上结点的个数点的个数第第i行行:TD(Vi)或或第第i列列:TD(Vi)稀疏图稀疏图稠密图稠密图不唯一不唯一唯一唯一数据结构数据结构 第七章第七章 图图7.3 图的遍历图的遍历数据结构数据结构 第七章第七章 图图遍历：遍历：从图中某个顶点出发遍历图，访遍从图中某个顶点出发遍历图，访遍图中其余顶点，并且使图中的每个顶点仅图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。被访问一次的过程。深度优先搜索深度优先搜索DFS广度优先搜索广度优先搜索BFS1.基本概念基本概念数据结构数据结构 第七章第七章 图图一一.深度优先搜索深度优先搜索DFS基本思想基本思想 从图中某个顶点从图中某个顶点V0 出发，访问此顶点，然出发，访问此顶点，然后后依次从依次从V0的各个未被访问的邻接点出发的各个未被访问的邻接点出发深度深度优先搜索遍历优先搜索遍历图图，直至图中所有和，直至图中所有和V0有路径相有路径相通的顶点都被访问到。通的顶点都被访问到。连通图连通图的深度优先搜索遍历的深度优先搜索遍历数据结构数据结构 第七章第七章 图图深度优先搜索深度优先搜索例：例：ABCDEFGHIABCA B CFEF EGGDDHHII回到回到A结束！结束！深深度度优优先先搜搜索索树树每个顶点设置一个标志用于检查是否被访问过，每个顶点设置一个标志用于检查是否被访问过，即设置数组即设置数组visitedn，visitedi=0未访问未访问1已访问已访问一一.深度优先搜索深度优先搜索DFS基本思想基本思想解决的办法是：解决的办法是：如何判别如何判别V的邻接的邻接点是否被点是否被访问？访问？数据结构数据结构 第七章第七章 图图访问标志访问标志:访问次序访问次序:ACHDEKFACHDEKFFEKDHCAFFFFFFFKHFEDCATTTTTTT一一.深度优先搜索深度优先搜索DFS基本思想基本思想遍历结果还可以为：遍历结果还可以为：从示意图出发，遍历结果不唯一。从示意图出发，遍历结果不唯一。EKFDHCA数据结构数据结构 第七章第七章 图图从从A出发出发,深度优先遍历深度优先遍历顺序为顺序为:BACDFEBACDFEA E B F D C一一.深度优先搜索深度优先搜索DFS基本思想基本思想BACDFEBACDFE遍历结果还可以为：遍历结果还可以为：从示意图出发，遍历结果不唯一。从示意图出发，遍历结果不唯一。DCFEBA数据结构数据结构 第七章第七章 图图543216EDCBAF从从A出发出发,深度优先遍历深度优先遍历顺序为顺序为:A B E F C DBACDFEBACDFE231561463612234525643一一.深度优先搜索深度优先搜索DFS基本思想基本思想1A2B3C4D5E6FvisitedFFFFFFTTTTTT问题：问题：从存储结构出发从存储结构出发,遍历结果唯一吗？遍历结果唯一吗？答案：唯一答案：唯一数据结构数据结构 第七章第七章 图图一一.深度优先搜索深度优先搜索DFS基本思想基本思想首先将图中每个顶点的访问标志设为首先将图中每个顶点的访问标志设为FALSE,之后搜索图中每个顶点，如果未被访之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。遍历，否则继续检查下一顶点。非连通图非连通图的深度优先搜索遍历的深度优先搜索遍历数据结构数据结构 第七章第七章 图图访问标志访问标志:访问次序访问次序:ACHDEIFBGACHDEIFBGGBFEIDHCAABCDEFGHIFFFFFFFFFTTTTTTTTT一一.深度优先搜索深度优先搜索DFS基本思想基本思想数据结构数据结构 第七章第七章 图图#defineTRUE1#defineFALSE0intvisitedMAX_VERTEX_NUM;voidDFS(MGraphG,intvi)intvj;visit(G,vi);visitedvi=TRUE;vj=0;while(vjG.vernum)DFS(G,vj);vj+;一一.深度优先搜索深度优先搜索DFSprintf(%c,G.vertexi);if(!visitedvj&G.arcsvivj.adj=1)邻接矩阵邻接矩阵存储形式存储形式数据结构数据结构 第七章第七章 图图voidTraverseDFS(MGraphG)inti;for(i=0;iG.vernum;i+)visitedi=FALSE;for(i=0;iadj);p=p-nextarc;一一.深度优先搜索深度优先搜索DFSprintf(%c,G.vertexi.data);if(!visitedp-adj)邻接表邻接表存储形式存储形式数据结构数据结构 第七章第七章 图图voidTraverseDFS(ALGraphG)inti;for(i=0;iG.vernum;i+)visitedi=FALSE;for(i=0;iG.vernum;i+)if(!visitedi)DFS(G,i);一一.深度优先搜索深度优先搜索DFS邻接表邻接表存储形式存储形式数据结构数据结构 第七章第七章 图图类似于树的层次遍历类似于树的层次遍历连通图连通图的深度优先搜索遍历的深度优先搜索遍历二二.广度优先搜索广度优先搜索BFS.从图中某个顶点从图中某个顶点v0出发，首先访问出发，首先访问v0;.依次访问依次访问v0各个未被访问的邻接点；各个未被访问的邻接点；.分别从这些邻接点出发，依次访问它们的各个未分别从这些邻接点出发，依次访问它们的各个未被访问的邻接点。访问时应保证：如果被访问的邻接点。访问时应保证：如果vi和和vk为当前为当前端结点，且端结点，且vi在在vk之前被访问，则之前被访问，则vi的所的所有未被访问有未被访问的邻接点应在的邻接点应在vk所有未被访问的邻接点之前访问。所有未被访问的邻接点之前访问。重复重复，直到所有端结点均没有未被访问的邻接点，直到所有端结点均没有未被访问的邻接点为止。为止。数据结构数据结构 第七章第七章 图图例如：例如：A B D E C G F H I广广度度优优先先搜搜索索树树广度优先搜索广度优先搜索需要辅助队需要辅助队列列Q，以便，以便实现实现访问时访问时应保证的一应保证的一点！点！二二.广度优先搜索广度优先搜索BFS每个顶点设置一个标志用于检查是否被访问过，每个顶点设置一个标志用于检查是否被访问过，即设置数组即设置数组visitedn，visitedi=0未访问未访问1已访问已访问解决的办法是：解决的办法是：ABCDEFGHIABEDCFGHI数据结构数据结构 第七章第七章 图图从从A出发出发,广度优先遍广度优先遍历历顺序为顺序为:BACDFEA E C B F D二二.广度优先搜索广度优先搜索BFS基本思想基本思想BACDFE数据结构数据结构 第七章第七章 图图543216EDCBAF从从A出发出发,广度优先遍历广度优先遍历顺序为顺序为:A B C E F DBACDFE231561463612234525643一一.深度优先搜索深度优先搜索BFS基本思想基本思想BACDFE1A 2B 3C 4D5E6FvisitedFFFFFFTTTTTT数据结构数据结构 第七章第七章 图图#defineTRUE1#defineFALSE0int visitedMAX_VERTEX_NUM;voidTraverseBFS(MGraphG)inti;for(i=1;i=G.vernum;i+)visitedi=FALSE;for(i=1;i=G.vernum;i+)if(!visitedi)BFS(G,i);邻接矩阵邻接矩阵存储形式存储形式二二.广度优先搜索广度优先搜索BFS数据结构数据结构 第七章第七章 图图邻接矩阵邻接矩阵存储形式存储形式二二.广度优先搜索广度优先搜索BFSvoidBFS(MGraphG,intvi)intv,i;SqQueueQ;InitQueue(Q);visit(G,vi);visitedvi=TRUE;EnQueue(Q,vi);while(!IsEmpty(Q)i=0;while(iadj);i+;voidvisit(ALGraphG,inti)printf(%c,G.vertexi);DeQueue(Q,v);if(!visitedi&G.arcsvi.adj=1)数据结构数据结构 第七章第七章 图图#defineTRUE1#defineFALSE0int visitedMAX_VERTEX_NUM;voidTraverseBFS(ALGraphG)inti;for(i=1;i=G.vernum;i+)visitedi=FALSE;for(i=1;iadj);visitedp-adj=TURE;EnQueue(Q,p-adj);p=p-nextarc;voidvisit(ALGraphG,inti)printf(%c,G.vertexi.data);DeQueue(Q,v);if(!visitedp-adj)数据结构数据结构 第七章第七章 图图7.4图的应用图的应用图中两个顶点之间图中两个顶点之间是否存在路径是否存在路径无向图的连通分量无向图的连通分量图的生成树与最小生成树图的生成树与最小生成树1.图的连通性问题图的连通性问题2.有向无环图的应用有向无环图的应用3.最短路径问题最短路径问题拓扑排序拓扑排序关键路径关键路径数据结构数据结构 第七章第七章 图图可以利用图的遍历来判断一个图是否连通，如果可以利用图的遍历来判断一个图是否连通，如果在遍历的过程中，在遍历的过程中，不止一次不止一次调用搜索过程，则说调用搜索过程，则说明该图就是一个明该图就是一个非连通图非连通图，并且，并且几次调用几次调用搜索过搜索过程，表明该图就有程，表明该图就有几个几个连通分量。连通分量。1.图的连通性问题图的连通性问题 无向图的连通分量无向图的连通分量AJCFEGBIDHA BDC IE F GH J数据结构数据结构 第七章第七章 图图voidTraverseDFS(ALGraphG)inti;for(i=1;i=G.vernum;i+)visitedi=FALSE;for(i=1;i=G.vernum;i+)if(!visitedi)printf(n);DFS(G,i);1.图的连通性问题图的连通性问题 无向图的连通分量无向图的连通分量voidTraverseBFS(ALGraphG)BFS(G,i)数据结构数据结构 第七章第七章 图图intDFS_IsPath(MGraphG,Vertexv1,Vertexv2)inti,j;for(i=0;iG.vernum;i+)visitedi=FALSE;i=Locate(G,v1);j=Locate(G,v2);DFS_Path(G,i);if(visitedj=FALSE)return0;elsereturn1;1.图的连通性问题图的连通性问题图中两个顶点之间图中两个顶点之间是否存在路径是否存在路径数据结构数据结构 第七章第七章 图图生成树：生成树：若图若图G是是连通图连通图，从图中某一顶点出发，从图中某一顶点出发遍历图时，图中所有的顶点加上遍历时经过的边遍历图时，图中所有的顶点加上遍历时经过的边所构成的子图称为所构成的子图称为生成树生成树。如果在生成树中加一如果在生成树中加一条边，必定构成一个环。条边，必定构成一个环。1.基本概念基本概念:BACDFEBACDFE某某连连通通图图有有n个个顶顶点点,则则其其生生成成树树应应该该有有?条条边边n-1数据结构数据结构 第七章第七章 图图生成森林：生成森林：对对非连通图非连通图，则称由各个连通分量，则称由各个连通分量的生成树的集合为此非连通图的的生成树的集合为此非连通图的生成森林生成森林。ABCDEFABCDEF1.基本概念基本概念:1、深度优先生成树、深度优先生成树(生成森林生成森林)2、广度优先生成树、广度优先生成树(生成森林生成森林)数据结构数据结构 第七章第七章 图图 假设要在假设要在 n 个城市之间建立通讯联络网，个城市之间建立通讯联络网，则连通则连通 n 个城市只需要修建个城市只需要修建 n-1条线路，条线路，如何如何在最节省经费的前提下建立这个通讯网？在最节省经费的前提下建立这个通讯网？最小生成树的问题提出：最小生成树的问题提出：构造网的一棵最小生成树，即：构造网的一棵最小生成树，即：该问题等价于：该问题等价于：在在e条条带带权权的的边边中中选选取取n-1条条边边（不不构构成回路），使成回路），使“权值之和权值之和”为最小。为最小。数据结构数据结构 第七章第七章 图图算法二：（克鲁斯卡尔算法）算法二：（克鲁斯卡尔算法）算法一：（普里姆算法）算法一：（普里姆算法）1.尽可能选取权值小的边，但不能构成回路。尽可能选取权值小的边，但不能构成回路。2.选取选取n-1条恰当的边以连接网的条恰当的边以连接网的n个顶点。个顶点。最小生成树的要解决的两个问题：最小生成树的要解决的两个问题：数据结构数据结构 第七章第七章 图图1.取图中任意一个顶点取图中任意一个顶点v作为生成树的根，之作为生成树的根，之后往生成树上添加新的顶点后往生成树上添加新的顶点w。2.在添加的顶点在添加的顶点w和已经在生成树上的顶点和已经在生成树上的顶点v之间必定存在一条边，并且该边的权值在所之间必定存在一条边，并且该边的权值在所有连通顶点有连通顶点v和和w之间的边中取值最小之间的边中取值最小。3.之后继续往生成树上