离散数学实验报告二

1、学 生 实 验 报 告 学 院： 软件与通信工程学院 课程名称： 离散数学（软件） 专业班级： 12软件 3 班 姓 名： 简建敏 学 号： 学生实验报告（2）学生姓名简建敏学号同组人 无实验项目图的矩阵表示和基本运算必修 选修演示性实验 验证性实验 操作性实验 综合性实验实验地点W101实验仪器台号12指导教师赵晓平实验日期及节次2013.12.12(四) 89A节一、实验综述1、实验目的及要求 （1）熟悉图在计算机中的矩阵表示； （2）编写程序，根据输入的整数对，输出一个图形的邻接矩阵，并求出各结点的出度和入度；（3）加强对图知识的理解、应用和运用能力。实验要求：给出如下有向图D，利用邻接

2、矩阵，编写程序计算：（1）各结点的度数；（2）D中到长度为3的通路的条数；（3）D中到长度为3的回路的条数。we.认真完成实验题，能正确运行，提交实验报告并上传程序，实验报告要求写出操作步骤、结果、问题、解决方法、体会等。2、实验仪器、设备或软件 计算机、VC+6.0、office、相关的操作系统等。二、实验过程（实验步A骤、记录、数据、分析）实验原理： 设D是一个线图，则n阶方阵称为D的邻接矩阵。其中： 邻接矩阵具有如下特点:（1）邻接矩阵是一个布尔矩阵；（2）无向线图的邻接矩阵是对称的；（3）而有向线图的邻接矩阵不一定对称； 利用邻接矩阵可以很容易的完成结点的度数计算实验过程代码如下：#i

3、nclude using namespace std;#define MAX_SIZE 20#define OK 1typedef int Status;typedef struct ArcCellint adj;ArcCell,AdjMatrixMAX_SIZEMAX_SIZE;typedef structchar vexMAX_SIZE;AdjMatrix arcs;int vexnum,arcnum;MGraph;int LocateVex(MGraph G,char v1);int LocateVex(MGraph G,char v1)int i;for(i=0;iG.vexnum;i

4、+)if(G.vexi=v1)return i;return -1;Status CreatDG(MGraph &G) cout用abcd代替v1、v2、v3、v4;endl;coutG.vexnumG.arcnum;int i,j,k;char v1,v2;cout请按顺序输入所有的顶点:endl;for(i=0;iG.vexi;for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)G.arcsij.adj=0;for(k=0;kG.arcnum;k+)cout请输入第k+1边的两个端点:v1v2;i=LocateVex(G,v1);j=LocateVex(G,

5、v2);G.arcsij.adj=1+G.arcsij.adj;cout邻接矩阵:endl;for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)coutG.arcsij.adj ;coutendl;return OK;void du(MGraph G)int i,j,s=0,k=0;for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)s=s+G.arcsij.adj;k=k+G.arcsji.adj;cout第i+1个顶点的出度是s,入度是k.endl; s=0; k=0;MGraph changdu(MGraph T)MGrap

6、h S;S.arcnum=T.arcnum;S.vexnum=T.vexnum;int i,j;for(i=0;iT.vexnum;i+)S.vexi=T.vexi;for(j=0;jT.vexnum;j+)S.arcsij.adj=T.arcsi0.adj*T.arcs0j.adj+T.arcsi1.adj*T.arcs1j.adj+T.arcsi2.adj*T.arcs2j.adj+T.arcsi3.adj*T.arcs3j.adj;return S;MGraph changdu2(MGraph Q,MGraph T)MGraph S;S.arcnum=T.arcnum;S.vexnum=

7、T.vexnum;int i,j;for(i=0;iT.vexnum;i+)S.vexi=T.vexi;for(j=0;jT.vexnum;j+)S.arcsij.adj=Q.arcsi0.adj*T.arcs0j.adj+Q.arcsi1.adj*T.arcs1j.adj+Q.arcsi2.adj*T.arcs2j.adj+Q.arcsi3.adj*T.arcs3j.adj;return S;int tonglu(MGraph G,int length,char v1,char v2)MGraph S;S=changdu(G);int i,j;for(i=0;ilength-2;i+)S=c

8、hangdu2(S,G);cout长度为length的关系矩阵:endl;for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)coutS.arcsij.adj ;coutendl;i=LocateVex(S,v1);j=LocateVex(S,v2);return S.arcsij.adj;void main()MGraph G;CreatDG(G);du(G);int i;char v2,v4,v3;coutiv2v4;coutv2与v4长度为i的通路有tonglu(G,i,v2,v4)条!endl;coutiv3;cout长度为i的v3回路有tonglu(G,i,v3,v3)条!endl;三、结论1、实验结果2、分析讨论