离散数学实验报告二

学生实验报告学院：软件与通信工程学院课程名称：离散数学（软件）专业班级：12软件3班姓名：简建敏学号：0123897学生实验报告（2）学生姓名简建敏学号0123897同组人无实验项目图的矩阵表示和基本运算□必修□选修□演示性实验□验证性实验□操作性实验□综合性实验实验地点W101实验仪器台号12指导教师赵晓平实验日期及节次2013.12.12(四)89A节一、实验综述1、实验目的及要求（1）熟悉图在计算机中的矩阵表示；（2）编写程序，根据输入的整数对，输出一个图形的邻接矩阵，并求出各结点的出度和入度；（3）加强对图知识的理解、应用和运用能力。实验要求：给出如下有向图D，利用邻接矩阵，编写程序计算：（1）各结点的度数；（2）D中2v到4v长度为3的通路的条数；（3）D中3v到3v长度为3的回路的条数。4v3v2v1vwe.认真完成实验题，能正确运行，提交实验报告并上传程序，实验报告要求写出操作步骤、结果、问题、解决方法、体会等。2、实验仪器、设备或软件计算机、VC++6.0、office、相关的操作系统等。二、实验过程（实验步A骤、记录、数据、分析）实验原理：设D＝V,E是一个线图，1211{,,,},{,,,}nnVvvvEeee，则n阶方阵()ijnnAa称为D的邻接矩阵。其中：1,,(,)0,,(,)ijijijijijvvEvvEavvEvvE或或邻接矩阵具有如下特点:（1）邻接矩阵是一个布尔矩阵；（2）无向线图的邻接矩阵是对称的；√√（3）而有向线图的邻接矩阵不一定对称；利用邻接矩阵可以很容易的完成结点的度数计算实验过程代码如下：#includeiostreamusingnamespacestd;#defineMAX_SIZE20#defineOK1typedefintStatus;typedefstructArcCell{intadj;}ArcCell,AdjMatrix[MAX_SIZE][MAX_SIZE];typedefstruct{charvex[MAX_SIZE];AdjMatrixarcs;intvexnum,arcnum;}MGraph;intLocateVex(MGraphG,charv1);intLocateVex(MGraphG,charv1){inti;for(i=0;iG.vexnum;i++){if(G.vex[i]==v1)returni;}return-1;}StatusCreatDG(MGraph&G){cout用abcd代替v1、v2、v3、v4;endl;cout请输入顶点的个数和弧数:;cinG.vexnumG.arcnum;inti,j,k;charv1,v2;cout请按顺序输入所有的顶点:endl;for(i=0;iG.vexnum;i++){111deg()deg(),deg()niikknniikikikkvavavacinG.vex[i];}for(i=0;iG.vexnum;i++){for(j=0;jG.vexnum;j++)G.arcs[i][j].adj=0;}for(k=0;kG.arcnum;k++){cout请输入第k+1边的两个端点:endl;cinv1v2;i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j].adj=1+G.arcs[i][j].adj;}cout邻接矩阵:endl;for(i=0;iG.vexnum;i++){for(j=0;jG.vexnum;j++)coutG.arcs[i][j].adj;coutendl;}returnOK;}voiddu(MGraphG){inti,j,s=0,k=0;for(i=0;iG.vexnum;i++){for(j=0;jG.vexnum;j++){s=s+G.arcs[i][j].adj;k=k+G.arcs[j][i].adj;}cout第i+1个顶点的出度是s,入度是k.endl;s=0;k=0;}}MGraphchangdu(MGraphT){MGraphS;S.arcnum=T.arcnum;S.vexnum=T.vexnum;inti,j;for(i=0;iT.vexnum;i++){S.vex[i]=T.vex[i];for(j=0;jT.vexnum;j++)S.arcs[i][j].adj=T.arcs[i][0].adj*T.arcs[0][j].adj+T.arcs[i][1].adj*T.arcs[1][j].adj+T.arcs[i][2].adj*T.arcs[2][j].adj+T.arcs[i][3].adj*T.arcs[3][j].adj;}returnS;}MGraphchangdu2(MGraphQ,MGraphT){MGraphS;S.arcnum=T.arcnum;S.vexnum=T.vexnum;inti,j;for(i=0;iT.vexnum;i++){S.vex[i]=T.vex[i];for(j=0;jT.vexnum;j++)S.arcs[i][j].adj=Q.arcs[i][0].adj*T.arcs[0][j].adj+Q.arcs[i][1].adj*T.arcs[1][j].adj+Q.arcs[i][2].adj*T.arcs[2][j].adj+Q.arcs[i][3].adj*T.arcs[3][j].adj;}returnS;}inttonglu(MGraphG,intlength,charv1,charv2){MGraphS;S=changdu(G);inti,j;for(i=0;ilength-2;i++)S=changdu2(S,G);cout长度为length的关系矩阵:endl;for(i=0;iG.vexnum;i++){for(j=0;jG.vexnum;j++)coutS.arcs[i][j].adj;coutendl;}i=LocateVex(S,v1);j=LocateVex(S,v2);returnS.arcs[i][j].adj;}voidmain(){MGraphG;CreatDG(G);du(G);inti;charv2,v4,v3;cout请输入长度以及端点v2，v4:;ciniv2v4;coutv2与v4长度为i的通路有tonglu(G,i,v2,v4)条!endl;cout请输入长度以及端点v3:;ciniv3;cout长度为i的v3回路有tonglu(G,i,v3,v3)条!endl;}三、结论1、实验结果2、分析讨论通过本次实验练习，我近一步深入了解了熟悉图在计算机中的矩阵表示，而且根据输入的整数对，输出一个图形的邻接矩阵，并求出各结点的出度和入度，同时加强对图知识的理解、应用和运用能力。这是值得学习的过程；四、指导教师评语及成绩：成绩：指导教师签名：批阅日期：