资源描述：
《图的建立及输出（图的遍历）.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构课程设计题目图的建立及输出学生姓名学号院系专业指导教师二Ｏ一Ｏ年12月16日目录一、设计题目…………………………………………………2二、运行环境（软、硬件环境）………………………………2三、算法设计的思想…………………………………………23.1邻接矩阵表示法…………………………………………23.2图的遍历………………………………………………43.3邻接矩阵的输出…………………………………………5四、算法的流程图……………………………………………6五、算法设计分析……………………………………………75.1
2、无向网邻接矩阵的建立算法………………………………75.2无向图邻接矩阵的建立算法………………………………75.3图的深度优先遍历………………………………………75.4图的广度优先遍历………………………………………8六、源代码……………………………………………………8七、运行结果分析……………………………………………14八、收获及体会………………………………………………15一、设计题目：图的建立及输出*问题描述：建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶
3、点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。二、运行环境（软、硬件环境）*软件环境：Windows7、WindowsVista、WindowsXp等*硬件环境：处理器：Pentium4以上内存容量：256M以上硬盘容量：40GB以上三、算法设计的思想1、邻接矩阵表示法: 设G=(V,E)是一个图，其中V={V1,V2,V3…,Vn}。G的邻接矩阵是一个他有下述性质的n阶方阵： 1，若(Vi,Vj)∈E或∈E；A[i,j]={0，反之图5-2中有向图G1和无向图G2的邻接
4、矩阵分别为M1和M2:M1=┌0101┐│1010││1001│└0000┘M2=┌0111┐│1010││1101│└1010┘ 注意无向图的邻接是一个对称矩阵，例如M2。 用邻接矩阵表示法来表示一个具有n个顶点的图时，除了用邻接矩阵中的n*n个元素存储顶点间相邻关系外，往往还需要另设一个向量存储n个顶点的信息。因此其类型定义如下： VertexTypevertex[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧
5、(边)数GraphKindkind;//图的种类标志 若图中每个顶点只含一个编号i(1≤i≤vnum)，则只需一个二维数组表示图的邻接矩阵。此时存储结构可简单说明如下： typeadjmatrix=array[1..vnum,1..vnum]ofadj; 利用邻接矩阵很容易判定任意两个顶点之间是否有边（或弧）相联，并容易求得各个顶点的度。 对于无向图，顶点Vi的度是邻接矩阵中第i行元素之和，即 n n D(Vi)＝∑A[i,j] （或∑A[i,j]） j=1
6、 i=1 对于有向图，顶点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)上的权值。相应地，网的邻接矩阵
7、表示的类型定义应作如下的修改： adj:weightype;{weightype为权类型} 图5-6列出一个网和它的邻接矩阵。┌∞３１∞∞┐│∞∞５１∞││∞∞∞∞∞││∞∞６∞∞│└∞３２２∞┘(a)网(b)邻接矩阵图5-6网及其邻接矩阵 对无向图或无向网络，由于其邻接矩阵是对称的，故可采用压缩存贮的方法，仅存贮下三角或上三角中的元素(但不含对角线上的元素)即可。显然，邻接矩阵表示法的空间复杂度O()。无向网邻接矩阵的建立方法是：首先将矩阵A的每个元素都初始化成∞。然后，读入边及权值(i,j,wij
8、),将A的相应元素置成Wij。2、图的遍历：*深度优先搜索深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。假设初始状态是图中所有的顶点未曾被访问，则深度优先遍历可从图的某个顶点V出发，访问此顶点，然后依次从V的未被访问的邻接点出发深度优先遍历图，直至图中所有和V有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中的一个未被访问的顶点，重复上述过程，直至图中所有顶
