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

《邻接矩阵表示图_深度_广度优先遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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个元素存储顶点间相邻关系外，往往还需要另设

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

3、是否有边（或弧）相联，并容易求得各个顶点的度。10　　　　对于有向图，顶点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)上

4、的权值。相应地，网的邻接矩阵表示的类型定义应作如下的修改：　　　　adj:weightype;{weightype为权类型}　　2、图的遍历：*深度优先搜索深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。假设初始状态是图中所有的顶点未曾被访问，则深度优先遍历可从图的某个顶点V出发，访问此顶点，然后依次从V的未被访问的邻接点出发深度优先遍历图，直至图中所有和V有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中的一个未被访问的顶点，重复上述过程，直至图中所有顶点都被访问到为止。以图中无向图G4为

5、例，深度优先遍历图的过程如图所示。假设从顶点V1出发进行搜索，在访问了顶点V1后，选择邻接点V2。因为V2未曾访问，则从V2出发进行搜索。依次类推，接着从V4,V8,V5出发进行搜索。在访问了V5之后，由于V5的邻接点已都被访问，则搜索回到V8。由于同样的理由，搜索继续回到V4，V2直至V1，此时由于V1的另一个邻接点为被访问，则搜索又从V1到V3，再继续进行下去。由此得到顶点的访问序列为：V1V2V4V8V5V3V6V710显然，这是一个递归的过程。为了在遍历过程中便于区别顶点是否已被访问，需附设访问标志数组vis

6、ted[0...n-1],其初值为0，一但某个顶点被访问，则其相应的分量置为1。2、图的输出图的邻接矩阵是一个二维数组，运用for语句的嵌套依次输出。开始开始输入vexnum，arcnumIncInfo选择图的类型构造图i＝i+1输入顶点i

7、无向图的邻接矩阵}beginfori:=1tondoread(G.vertex[i])；{读入n个顶点的信息}fori:=1tondoforj:=1toedoG.arcs[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、法的时间复杂度是O(n2)。4、图的广度优先遍历算法分析beginfori:=1tondo(visited[i]){初始化标志数组}while（i