图的遍历和联通.doc

成都信息工程学院计算机系 课 程 实 验 报 告 实验课程： 数据结构 实验项目： 图的遍历和连通 指导教师： 李莉丽 学生姓名: 李琼玖 学生学号： 2008053002 班 级： 数字媒体技术08级1班 实验地点： 宿舍和机房 实验时间： 2010 年 5月 ~ 6月 实验成绩： 评阅老师： 一【上机实验目的】 给定一图，在遍历的基础上确定其是否是连通。熟悉图的存储结构，深度和广度遍历以及其连通等。 二【实验环境】 PC机每人1台 三【上机实验内容】 给定一图，在遍历的基础上确定其是否是连通。其中要掌握图的存储结构在此基础上才能知道怎么遍历，然后要把深度遍历和广度遍历分析透，最后才解决连通的问题。 四【上机调试程序流程图】（注：可打印） （用传统流程图的形式表示） 五【上机调试中出现的错误信息、错误原因及解决办法】 上机过程中遇到了很多的问题，小到变量的引用，全局量的运用，地址符，指针等等。其实这些都还好，自己可以一步一步慢慢地解决，最困难的就是一些逻辑错误，严重的时候会出现刷屏或者死机什么什么的。 六【上机调试后的源程序及还存在的问题】（注：源程序可打印） （同时记录下你对你编写此程序的其它具体想法，） #include iostream #include malloc.h using namespace std; #define int_max 10000 #define inf 9999 #define max 20 #define OK 1 //…………………………………………邻接矩阵定义…………………… typedef struct ArcCell { int adj; char *info; }ArcCell,AdjMatrix[max][max]; typedef struct { char vexs[max]; AdjMatrix arcs; int vexnum,arcnum; }MGraph_L; //^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ int localvex(MGraph_L G,char v)//返回V的位置 { int i=0; while(G.vexs[i]!=v) ++i; return i; } int creatMGraph_L(MGraph_L G)//创建图用邻接矩阵表示 { char v1,v2; int i,j,w; cout…………创建图…………endl请输入图G顶点和弧的个数例如:(4 6)不包括“()”endl; cinG.vexnumG.arcnum; for(i=0;i!=G.vexnum;++i) { cout输入顶点iendl; cinG.vexs[i]; } for(i=0;i!=G.vexnum;++i) for(j=0;j!=G.vexnum;++j) { G.arcs[i][j].adj=int_max; G.arcs[i][j].info=NULL; } for(int k=0;k!=G.arcnum;++k) { cout输入一条边依附的顶点和权例如:(a b 3)不包括“()”endl; cinv1v2w;//输入一条边依附的两点及权值 i=localvex(G,v1);//确定顶点V1和V2在图中的位置 j=localvex(G,v2); G.arcs[i][j].adj=w; G.arcs[j][i].adj=w; } cout图G邻接矩阵创建成功！endl; return G.vexnum; } void ljjzprint(MGraph_L G) //邻接矩阵的输出 { int i,j; for(i=0;i!=G.vexnum;++i) { for(j=0;j!=G.vexnum;++j) coutG.arcs[i][j].adj ; coutendl; } } int visited[max];//访问标记 int we; typedef struct arcnode//弧结点 { int adjvex;//该弧指向的顶点的位置 struct arcnode *nextarc;//弧尾相同的下一条弧 char *info;//该弧信息 }arcnode; typedef struct vnode//邻接链表顶点头接点 { char data;//结点信息 arcnode *