2022年用邻接矩阵法输出图结构文件 .pdf

《2022年用邻接矩阵法输出图结构文件 .pdf》由会员分享，可在线阅读，更多相关《2022年用邻接矩阵法输出图结构文件 .pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图结构（设计性）4.1 实验目的1熟练掌握图的两种存储结构(邻接矩阵和邻接表 )的表示方法。2掌握图的基本运算及应用。3加深对图的理解，逐步培养解决实际问题的编程能力。4.2 实验要求1对图的各项操作一定要编写成为C（C+）语言函数，组合成模块化的形式，每个算法的实现要从时间复杂度和空间复杂度上进行评价。2将本算法中的各个操作实现。3保存程序的运行结果，并结合程序进行分析。4上机过程中，能够熟练运用高级语言的程序调试器DEBUG 调试程序。5上机后，认真整理源程序及其注释，完成实验报告（包括源程序、实验结果、算法分析、心得体会等） 。4.3 实验内容在 VC+环境下编写调试图深度优先和广度优先

2、遍历的算法和函数，或者把已布置作业中的算法改成程序，进行运行。问题描述：输入每条边的顶点u 和 v 及其权值 w ，然后建立用邻接矩阵表示的图。其相关操作如下：1. 创建一个可以随机确定结点数和弧（有向或无向）数的图。2. 根据图结点的序号，得到该结点的值。3. 根据图结点的位置的第一个邻接顶点的序号，以及下一个邻接顶点的序号。4. 实现从第 v 个顶点出发对图进行深度优先递归遍历。5. 实现对图作深度优先遍历。6. 编写主程序，实现对各不同的算法调用。4.4 实验清单#include #define MAX_VERTEX_NUM 10 /* 最多顶点个数 */ #define INFINIT

3、Y 32768 /* 表示极大值，即 */ #define True 1 #define False 0 #define Error -1 #define Ok 1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - typedef enumDG, DN, UDG, UDN GraphKind; /*图的种类： DG 表示有向图, DN 表示有向网 , UDG 表示无向图 , UDN 表示无向网 */ typedef char Ve

4、rtexData; /*假设顶点数据为字符型 */ typedef struct ArcNode / AdjType adj; /*对于无权图， 用 1 或 0 表示是否相邻； 对带权图， 则为权值类型 */ / OtherInfo info; int adj; ArcNode; typedef struct VertexData vexsMAX_VERTEX_NUM; /*顶点向量 */ ArcNode arcsMAX_VERTEX_NUMMAX_VERTEX_NUM; /* 邻接矩阵*/ int vexnum,arcnum; /* 图的顶点数和弧数 */ GraphKind kind; /

5、*图的种类标志 */ AdjMatrix; /*(Adjacency Matrix Graph)*/ int LocateVertex(AdjMatrix *G ,VertexData v) /*求顶点位置函数 */ int j=Error,k; for(k=0;kvexnum;k+) if(G-vexsk=v) j=k; break; return(j); int CreateDN(AdjMatrix *G) /*创建一个有向网 */ int i,j,k,weight; VertexData v1,v2; printf( 输入图的弧数和顶点数 n); fflush(stdin); scanf

6、(%d,%d,&G-arcnum,&G-vexnum); /* 输入图的顶点数和弧数 */ for(i=0;ivexnum;i+) /*初始化邻接矩阵 */ for(j=0;jvexnum;j+) G-arcsij.adj=INFINITY; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - for(i=0;ivexnum;i+) printf( 输入图的顶点 n); fflush(stdin); scanf(%c,&G-vexs

7、i); /* 输入图的顶点 */ for(k=0;karcnum;k+) printf( 输入一条弧的两个顶点及权值n); fflush(stdin); scanf(%c,%c,%d,&v1,&v2,&weight);/* 输入一条弧的两个顶点及权值*/ i=LocateVertex(G,v1); j=LocateVertex(G ,v2); G-arcsij.adj=weight; /*建立弧 */ return(Ok); void printf_adjmatrix(AdjMatrix *G) int i,j; printf( ); for(i=0;ivexnum;i+) printf(%c

8、,G-vexsi); printf( ); printf(n); for(i=0;ivexnum;i+) printf(%c,G-vexsi); for(j=0;jvexnum;j+) if(G-arcsij.adj = INFINITY) printf( ); else printf(%-4d, G-arcsij.adj); printf(n); void main() AdjMatrix G; CreateDN(&G); printf_adjmatrix(&G); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - 4.5 运行结果4.6 实验心得对图结构和矩阵之间的概念和关系还不是很了解，在写程序是出现了很多错误我自己对输出图结构这方面还不是很了解，通过慢慢摸索， 写出了程序， 有很大的成就感名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -