《图的存储及遍历.ppt》由会员分享，可在线阅读，更多相关《图的存储及遍历.ppt（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图的存储结构邻接矩阵数组表示法（邻接矩阵）graph=Recordvex:array1.vtxptrofvertex;存储顶点信息arc:arrayvtxptr,vtxptrofvertex;存储边相关信息借助邻接矩阵容易判定任意两个顶点之间是否有边（或弧）相连，并容易求得各个顶点的度。对于无向图，顶点的度vi是邻接矩阵中第i行（或第i列）的元素之和。对于有向图，顶点vi的出度是邻接矩阵中第i行的元素之和，顶点vi的入度是邻接矩阵中第i列的元素之和。网的邻接矩阵表示为：图的存储结构边集数组边集数组是利用一维数组存储图中所有边的一种图的边集数组是利用一维数组存储图中所有边的一种图的表示方法表示方
2、法Typenode=recordfromv,endv:1.n;起点，终点weight:integer;权值end;图的存储结构邻接表邻接表typeedgeptr=edgenode;edgenode=recordadjvex:1.n;邻接点域weight:weightType;权值next:edgeptr；链域end;vexnode=Recorddata:dpeatat；link:edgeptr;end;表头结点包括一个起点信息和一个链接Adjlist=array1.nofvexnode;n个定点的邻接表有向图建立邻接表的过程Procedurecreatelist(varg:adilist)va
3、rs:edgenodebeginread(n,e);fori:=1tondobeginread(gi.data);gi.link:=nil;end;Fork:=1toedobeginread(i,j,w);new(s);s.adj:=j;s.weight:=w;s.next:=gi.link;gi.link:=s;end;End;图的深度优先遍历从某个未被访问的顶点v出发,深度优先遍历图,直到和v有路径的顶点都访问到.Proceduredfs(i:1.n);图用邻接表存储beginwrite(gi.v);visitedi:=true;p:=gi.link;whilepnildobeginj:=
4、p.adj;j为i的一个后继ifnotvisitedjthendfs(j);深度，递归p:=p.next;p为i的下一个后继end;end;procedureshendu(i);图用邻接矩阵存储beginwrite(i);vi:=true;forj:=1tondoif(ai,j=1)andnot(vj)thenshendu(j);end;深深度度优优先先搜搜索索DFS(Depth First Search)n n深度优先搜索的示例深度优先搜索的示例ACDEGBFIHACDEGBFIH123456789123456789前进回退深度优先搜索过程深度优先搜索过程 深度优先生成树深度优先生成树n n
5、DFS 在访问图中某一起始顶点在访问图中某一起始顶点 v 后后,由由 v 出发出发,访问它的任一邻接顶点访问它的任一邻接顶点 w1;再从再从 w1 出发出发,访问与访问与 w1邻邻 接但还没有访问过的接但还没有访问过的顶点顶点 w2;然后再从然后再从 w2 出发出发,进行类似的进行类似的访问访问,如此进行下去如此进行下去,直至到达所有的直至到达所有的邻接顶点都被访问过的顶点邻接顶点都被访问过的顶点 u 为止为止。接着。接着,退回一步退回一步,退到前一次刚访问过的顶点退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。看是否还有其它没有被访问的邻接顶点。如如果有果有,则访问此顶点则访问
6、此顶点,之后再从此顶点出之后再从此顶点出发发,进行与前述类似的访问进行与前述类似的访问;如果没有如果没有,就再退回一步进行搜索。重复上述过程就再退回一步进行搜索。重复上述过程,直直到连通图中所有顶点都被访问过为止。到连通图中所有顶点都被访问过为止。图的广度优先遍历从某个未被访问的顶点v出发,依次访问v的各个未曾访问过的邻接点.然后分别从这些邻接点出发广度优先搜索遍历,直到所有已被访问的邻接点都被访问到.procedureguangdu(i);beginwrite(i);vi:=true;i进队;repeat队首元素出队设为kforj:=1tondoif(ak,j=1)and(notvj)the
7、nbeginwrite(j);vj:=true;j进队;end;until队列q为空;广度优先搜索广度优先搜索广度优先搜索广度优先搜索BFSBFS (Breadth First Search(Breadth First Search )n n广度优先搜索的示例广度优先搜索的示例ACDEGBFIHACDEGBFH123456789123456789广度优先搜索过程广度优先搜索过程 广度优先生成树广度优先生成树InBFS在访问了在访问了起始顶点起始顶点 v 之后之后,由由 v 出发出发,依次访问依次访问 v 的各个的各个未被访问过的邻接顶点未被访问过的邻接顶点 w1,w2,wt,然后再顺序访问然后
8、再顺序访问 w1,w2,wt 的所有还未被访问过的邻接顶的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，们的所有还未被访问过的邻接顶点，如如此做下去，直到图中所有顶点都被访问到为此做下去，直到图中所有顶点都被访问到为止。止。n广度优先搜索是一种分层的搜索过程广度优先搜索是一种分层的搜索过程,每向每向前走一步可能访问一批顶点前走一步可能访问一批顶点,不像深度优先不像深度优先搜索那样有往回退的情况。因此搜索那样有往回退的情况。因此,广度优先广度优先搜索不是一个递归的过程。搜索不是一个递归的过程。n n为了实现逐层访问为了实现逐层访问,算法中使用了一个队算法中使用了一个队列列,以记忆正在访问的这一层和上一层的顶以记忆正在访问的这一层和上一层的顶点点,以便于向下一层访问。以便于向下一层访问。n n为避免重复访问为避免重复访问,需要一个辅助数组需要一个辅助数组 visited ，给被访问过的顶点加标记。给被访问过的顶点加标记。