邻接矩阵表示图深度广度优先遍历

邻接矩阵表示图深度广度优先遍历

ID:8868421

大小:90.94 KB

页数:11页

时间:2018-04-09

邻接矩阵表示图深度广度优先遍历_第1页
邻接矩阵表示图深度广度优先遍历_第2页
邻接矩阵表示图深度广度优先遍历_第3页
邻接矩阵表示图深度广度优先遍历_第4页
邻接矩阵表示图深度广度优先遍历_第5页
资源描述:

《邻接矩阵表示图深度广度优先遍历》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

1、*问题描述:建立图的存储结构,能够输入图的顶点和边的信息,并存储到相应存储结构中,而后输出图的邻接矩阵。1、邻接矩阵表示法:  设G=(V,E)是一个图,其中V={V1,V2,V3…,Vn}。G的邻接矩阵是一个他有下述性质的n阶方阵:      1,若(Vi,Vj)∈E或∈E;A[i,j]={0,反之图5-2中有向图G1的邻接矩阵为M1M1=┌0101┐│1010││1001│└0000┘  用邻接矩阵表示法来表示一个具有n个顶点的图时,除了用邻接矩阵中的n*n个元素存储顶点间相邻关系外,往往还需要另设一个向量存储n个顶点的信息。

2、因此其类型定义如下: VertexTypevertex[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧(边)数GraphKindkind;//图的种类标志  若图中每个顶点只含一个编号i(1≤i≤vnum),则只需一个二维数组表示图的邻接矩阵。此时存储结构可简单说明如下: typeadjmatrix=array[1..vnum,1..vnum]ofadj;  利用邻接矩阵很容易判定任意两个顶点之间是否有边(或弧)相联,并容易求得各个顶点的度。10   

3、 对于有向图,顶点Vi的出度OD(Vi)为邻接矩阵第i行元素之和,顶点Vi的入度ID(Vi)为第i列元素之和。即        n         n    OD(Vi)=∑A[i,j],OD(Vi)=∑A[j,i])       j=1         j=1      用邻接矩阵也可以表示带权图,只要令         Wij,若或(Vi,Vj)    A[i,j]={         ∞,否则。  其中Wij为或(Vi,Vj)上的权值。相应地,网的邻接矩阵表示的类型定义应作如下的修改:    adj:weigh

4、type;{weightype为权类型}  2、图的遍历:*深度优先搜索深度优先搜索遍历类似于树的先根遍历,是树的先根遍历的推广。假设初始状态是图中所有的顶点未曾被访问,则深度优先遍历可从图的某个顶点V出发,访问此顶点,然后依次从V的未被访问的邻接点出发深度优先遍历图,直至图中所有和V有路径相通的顶点都被访问到;若此时图中尚有顶点未被访问,则另选图中的一个未被访问的顶点,重复上述过程,直至图中所有顶点都被访问到为止。以图中无向图G4为例,深度优先遍历图的过程如图所示。假设从顶点V1出发进行搜索,在访问了顶点V1后,选择邻接点V2。因为V2未曾访

5、问,则从V2出发进行搜索。依次类推,接着从V4,V8,V5出发进行搜索。在访问了V5之后,由于V5的邻接点已都被访问,则搜索回到V8。由于同样的理由,搜索继续回到V4,V2直至V1,此时由于V1的另一个邻接点为被访问,则搜索又从V1到V3,再继续进行下去。由此得到顶点的访问序列为:V1V2V4V8V5V3V6V710显然,这是一个递归的过程。为了在遍历过程中便于区别顶点是否已被访问,需附设访问标志数组visted[0...n-1],其初值为0,一但某个顶点被访问,则其相应的分量置为1。2、图的输出图的邻接矩阵是一个二维数组,运用for语句的嵌套

6、依次输出。开始开始输入vexnum,arcnumIncInfo选择图的类型构造图i=i+1输入顶点i

7、s[i][j]=0;{将邻接矩阵的每个元素初始化成0}fork:=1toedo{e为边的数目}[read(i,j,w){读入边和权}G.arcs[i][j]:=w]G.arcs[i][j]=G.arcs[i][i]{置对称弧}end;该算法的执行时间是O(n+n2+e),其中消耗在邻接矩阵初始化操作上的时间是O(n2),而e

8、..}}end10二维数组表示邻接矩阵作图的存储结构,其中n为图中顶点数,查找每个顶点的邻接点所需时间为O(n2)。/*Graph.h*/#inclu

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。