学生实验报告
学 院： 软件与通信工程学院
课程名称： 离散数学（软件）
专业班级： 13软件 3 班
姓 名： 刘汉存
学 号： 0133652
学生实验报告（2）
一、实验综述
1、实验目的及要求
（1）熟悉图在计算机中的矩阵表示；
（2）编写程序，根据输入的整数对，输出一个图形的邻接矩阵，并求出各结点的出度和入度；
（3）加强对图知识的理解、应用和运用能力。
实验要求：
给出如下有向图D，利用邻接矩阵，编写程序计算：（1）各结点的度数；（2）D中
到
长度为3的通路的条数；（3）D中
到长度为3的回路的条数。
认真完成实验题，能正确运行，提交实验报告并上传程序，实验报告要求写出操作步骤、结果、问题、解决方法、体会等。
2、实验仪器、设备或软件
计算机、VC++6.0、office、相关的操作系统等。
二、实验过程（实验步骤、记录、数据、分析）
实验原理：
设D＝<V,E>是一个线图，
，则n阶方阵
称为D的邻接矩阵。其中：
邻接矩阵具有如下特点:
（1）邻接矩阵是一个布尔矩阵；
（2）无向线图的邻接矩阵是对称的；
（3）而有向线图的邻接矩阵不一定对称；
利用邻接矩阵可以很容易的完成结点的度数计算
写明具体实施的步骤，包括实验过程中的记录、数据和相应的分析
#include <iostream>
using namespace std;
#define MaxInt 0
#define MVNum 100
bool visited [MVNum];
bool visited1 [MVNum];
typedef struct{
char vexs[MVNum];
int arcs[MVNum][MVNum];
int vexnum,arcnum;
}AMGraph;
int Locate(AMGraph G,char v){
for(int i=0;i<G.vexnum;i++)
if(G.vexs[i]==v)return i;
}
void CreateUDN(AMGraph &G){
int i,j;
char v1,v2;
cout<<"输入总顶点数和总边数："<<endl;
cin>>G.vexnum>>G.arcnum;
cout<<"输入点的信息："<<endl;
for(i=0;i<G.vexnum;++i)cin>>G.vexs[i];
for(i=0;i<G.vexnum;++i)
for(j=0;j<G.vexnum;++j)
G.arcs[i][j]=MaxInt;
cout<<"输入各边依附的顶点："<<endl;
for(int k=0;k<G.arcnum;++k){
cin>>v1>>v2;
i=Locate(G,v1);
j=Locate(G,v2);
G.arcs[i][j]++;
}
cout<<"G的邻接矩阵为："<<endl;
for(i=0;i<G.vexnum;i++){
for(j=0;j<G.vexnum;j++)
cout<<G.arcs[i][j]<<" ";
cout<<endl;
}
}
void tonghuilu(AMGraph &G){
int i,j,k;
int a[MVNum][MVNum];
int b[MVNum][MVNum];
int c[MVNum][MVNum];
for(i=0;i<G.vexnum;++i)
for(j=0;j<G.vexnum;++j){
a[i][j]=MaxInt;
c[i][j]=MaxInt;
b[i][j]=G.arcs[i][j];
}
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
for(k=0;k<G.vexnum;k++)
a[i][j]=a[i][j]+b[i][k]*b[k][j];
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
for(k=0;k<G.vexnum;k++)
c[i][j]=c[i][j]+a[i][k]*b[k][j];
int m,n,o,p;
cout<<"输入起点 ";cin>>m;
cout<<"输入终点 ";cin>>n;
cout<<"(2)D中v2到v4长度为3的通路的条数"<<endl;
cout<<"计算得到通路的条数"<<endl;
cout<<c[m-1][n-1]<<endl;
cout<<"(2)D中v3到v3长度为3的通路的条数"<<endl;
cout<<"输入起点 ";cin>>o;
cout<<"输入终点 ";cin>>p;
cout<<"计算得到回路的条数"<<endl;
cout<<c[o-1][p-1]<<endl;
}
void ChuRuDu(AMGraph &G){
int sum[MVNum];
int sum1[MVNum];
int i,j;
for(i=0;i<G.vexnum;++i){
sum[i]=MaxInt;
sum1[i]=MaxInt;
}
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++){
sum[i]+=G.arcs[i][j];
sum1[i]+=G.arcs[j][i];
}
cout<<"(1)各结点的度数:"<<endl;
for(i=0;i<G.vexnum;i++)
cout<<G.vexs[i]<<"的入度为："<<sum1[i]<<" 出度为："<<sum[i]<<endl;
}
void main(){
AMGraph G;
cout<<"假设v1，v2，v3，v4分别为a，b，c，d"<<endl;
CreateUDN(G);
ChuRuDu(G);
tonghuilu(G);
}
三、结论
1、实验结果
根据实验过程中所见到的现象和测得的数据，做出结论
2、分析讨论
对本次实验的心得体会、思考和建议。
四、指导教师评语及成绩：
成绩： 指导教师签名：
批阅日期：
第二篇：离散数学实验报告2_240111338
南京工程学院
实 验 报 告
课程名称 离散数学
实验项目名称集合论
实验学生班级 K多媒体111
实验学生姓名 朱在吉
学 号 240111338
同组学生姓名
实验时间 2012.11.08
实验地点
实验成绩评定
指导教师签字 年 月 日
