自主学习四.实验设计
实验题目：图的邻接矩阵计算
设计方案：
设有向图D=<V,E>，V={v1,v2,…vn}。
如：给定有向图D=<V,E>，
V={a,b,c,d},
E={<a,a>,<a,b>,<a,b>,<a,d>,<d,c>,<c,d>,<c,b>}.
一、需求分析
程序应满足如下功能：
1.能由有向图转换为对应的邻接矩阵。
2.能计算邻接矩阵A，A ²，A ³…A ⁿ.
3.图的邻接矩阵可用来求点到点之间的通路条数。所以程序应能求出点到点之间不同长度的通路条数。
4.能求出点到自身的不同长度的回路条数。
5.能求出长度小于等于n的通路数
6.能求出长度小于等于n的回路数
二、概要设计
1.输入有向图D，将其转换为对应的邻接矩阵。
有向图的输入应包括V，E。可用一维数组存储V；E在后面的计算中不用，一个字符串存储足矣；二维数组存储邻接矩阵。由输入的E与V的关系计算点到点之间的通路数（即邻接矩阵中相应位置的元素）
2.计算邻接矩阵A，A ²，A ³…A ⁿ.
用矩阵乘法算法可求出A，A ²，A ³…A ⁿ.
3.根据A，A ²，A ³…A ⁿ输出所求。
根据矩阵中相应元素的求和等计算可得出所求。
三、详细设计
1.制定输入如下：
图1.1
2.制定菜单如下：
图1.2
3.邻接矩阵的转换算法：
for(int i=0;i<iSize;i++){//遍历E中有向边。
if(E[i]=='<'){//“<”后元素为起始点
for(intj=0;j<n;j++){//遍历V，查找起始点
if(V[j]==E[i+1]){//找到起始点，获取到起始点下标j
for(intk=0;k<n;k++){//遍历V，查找终点
if(V[k]==E[i+3]){//找到终点，获取到终点下标k
A1[j][k]++;//邻接矩阵相应位置+1
}
}
}
}
i+=4;
}
}
2. 计算邻接矩阵A，A ²，A ³…A ⁿ.
这里并不把每一个邻接矩阵A ⁿ都存储下来。根据所需长度求出A ⁿ.
2.1.矩阵乘法算法实现：
//矩阵乘法
void MatMul(int **a,int **b,int **c,intn){
for(inti=0;i<n;i++){
for(intj=0;j<n;j++){
*((int*)c+n*i+j)=0;
for(intk=0;k<n;k++){
*((int*)c+n*i+j)+=(*((int *)a+n*i+k))*(*((int *)b+n*k+j));
}
}
}
}
2.2 A ⁿ的计算：
分析如下：
A ²=A*A
A ³= A ²*A
.
.
.
A ⁿ=A（n-1）*A //（n-1）为上标，不能理解学数学的写报告时一堆公式的感受
每次把A（n-1）的计算结果存储为result。
将result复制到临时存储temp
求出A ⁿ
算法实现：
for(int i=2;i<=len;i++){
MatMul((int**)A1,(int **)temp,(int **)result,n);
copy((int**)temp,(int **)result,n);
}
temp=result这里包装成函数，方便调用。算法如下：
//二维数组复制
void copy(int **a,int **b,int n){
for(inti=0;i<n;i++){
for(intj=0;j<n;j++){
*((int*)a+n*i+j)=*((int *)b+n*i+j);
}
}
}
3.通路数的计算
点到点之间长度为n的通路（回路）数为矩阵中相应位置元素。
设B=A+A ²+A ³+…+A ⁿ，长度小于等于n的通路为B中各元素之和。
回路为对角线之和。
定义如下变量：
int sum=0;//总和
int partSum=0;//每个A ⁿ矩阵和
int diagonalSum=0;//对角线总和
int diaPartSum=0;//每个A ⁿ矩阵对角线和
算法实现：
for(A~ A ⁿ)
partSum=sum(A ⁿ);
sum+=partSum;
diagonalSum+=diaPartSum;
求每个矩阵所有元素之和函数sum()如下：
//矩阵所有元素之和及对角线之和
void Sum(int **a,int *partSum,int*diaPartSum,int n){
*partSum=0;
*diaPartSum=0;
for(inti=0;i<n;i++){
(*diaPartSum)+=*((int*)a+n*i+i);
for(intj=0;j<n;j++){
(*partSum)+=*((int*)a+n*i+j);
}
}
}
四、程序源代码
程序源码为C++语言编写，编译环境为dev-cpp.
#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;
/* run this program using the consolepauser or add your own getch, system("pause") or input loop */
void display(int **a,int n){
for(inti=0;i<n;i++){
for(intj=0;j<n;j++){
cout<<*((int*)a+n*i+j)<<" ";
}
cout<<endl;
}
}
//二维数组复制
void copy(int **a,int **b,int n){
for(inti=0;i<n;i++){
for(int j=0;j<n;j++){
*((int*)a+n*i+j)=*((int *)b+n*i+j);
}
}
}
//矩阵所有元素之和及对角线之和
void Sum(int **a,int *partSum,int*diaPartSum,int n){
*partSum=0;
*diaPartSum=0;
for(inti=0;i<n;i++){
(*diaPartSum)+=*((int*)a+n*i+i);
for(intj=0;j<n;j++){
(*partSum)+=*((int*)a+n*i+j);
}
}
}
//矩阵乘法
void MatMul(int **a,int **b,int **c,intn){
for(inti=0;i<n;i++){
for(intj=0;j<n;j++){
*((int*)c+n*i+j)=0;
for(intk=0;k<n;k++){
*((int*)c+n*i+j)+=(*((int *)a+n*i+k))*(*((int *)b+n*k+j));
}
}
}
}
int main(int argc, char** argv) {
int n,m;
cout<<"设有向图D=<V,E>:"<<endl;
cout<<"请输入顶点个数:";
cin>>n;
charV[n];//V
intA1[n][n];//矩阵
//初始化A1
for(inti=0;i<n;i++){
for(intj=0;j<n;j++){
A1[i][j]=0;
}
}
//输入D
stringE;
cout<<"请输入V：";
for(inti=0;i<n;i++){
cin>>V[i];
}
cout<<"请输入E:"<<endl;
cin>>E;
//求D的邻接矩阵
unsignedint iSize=E.length();
for(inti=0;i<iSize;i++){//遍历E中有向边。
if(E[i]=='<'){//"<"后元素为起始点
for(intj=0;j<n;j++){//遍历V，查找起始点
if(V[j]==E[i+1]){//找到起始点，获取到起始点下标j
for(intk=0;k<n;k++){//遍历V，查找终点
if(V[k]==E[i+3]){//找到终点，获取到终点下标k
A1[j][k]++;//邻接矩阵相应位置+1
}
}
}
}
i+=4;
}
}
cout<<"*************************************************"<<endl;
cout<<"1.求长度为n的矩阵"<<endl;
cout<<"2.求长度为n的通路(回路)"<<endl;
cout<<"3.求长度小于等于n的通路(回路)"<<endl;
cout<<"0.退出"<<endl;
cout<<"*************************************************"<<endl;
cout<<"请选择：";
intoption;
cin>>option;
while(option){
intlen;
cout<<"请输入长度n：";
cin>>len;
inttemp[n][n];
copy((int**)temp,(int **)A1,n);
intresult[n][n];
copy((int**)result,(int **)A1,n);
intsum=0;//总和
intpartSum=0;//每个A（n）矩阵和
intdiagonalSum=0;//对角线总和
intdiaPartSum=0;//每个A（n）矩阵对角线和
Sum((int**)A1,&sum,&diagonalSum,n);
for(inti=2;i<=len;i++){
MatMul((int**)A1,(int **)temp,(int **)result,n);
copy((int**)temp,(int **)result,n);
Sum((int**)result,&partSum,&diaPartSum,n);
sum+=partSum;
diagonalSum+=diaPartSum;
}
charstart;
charend;
switch(option){
option=0;
case1:
display((int**)result,n);
break;
case2:
cout<<"请输入起始点：";
cin>>start;
fflush(stdin);
cout<<"请输入终点：";
cin>>end;
for(inti=0;i<n;i++){
if(V[i]==start){//获取到起始点下标
for(intj=0;j<n;j++){
if(V[j]==end){//获取到终点下标
stringtempStr="的通路有";
if(start==end){
tempStr="的回路有";
}
cout<<"D中"<<start<<"到"<<end
<<"长度为"<<len<<tempStr<<result[i][j]<<"条。" <<endl;
}
}
}
}
break;
case3:
cout<<"D中长度小于等于" <<len<<"的通路有"<<sum
<<"条，其中有"<<diagonalSum<<"条回路。"<<endl;
break;
}
cout<<"请选择：";
cin>>option;
}
return0;
}
五、调试运行：
1.求长度为n的矩阵：
图1.3
2.求长度为n的通路：
图1.4
3.求长度为n的回路：
图1.5
4.求长度小于等于n的通路（回路）：
图1.6
5.输入0正常退出程序。
经过多组测试，结果符合实验需求，其余测试结果略。
注意事项：
图1.7
如图，因V的存储采用的字符数组形式，输入V时应输入单个字符，输入E时不应有空格等作为分隔符，有向边用<vi，vj>形式表示。
六、实验总结（略）