实验四 图的基本操作及应用
一、 实验目的
1、使学生可以巩固所学的有关图的基本知识。
2、熟练掌握图的存储结构。
3、熟练掌握图的两种遍历算法。
4、掌握如何应用图解决各种实际问题
二、 实验内容和要求
[问题描述]
给定一个无向网，可以求得任意一对顶点之间的最短路径。
[基本要求]
以邻接矩阵为存储结构，实现弗洛伊德算法求解每一对顶点之间的最短路径及最短路径长度。
[测试数据]
由学生依据软件工程的测试技术自己确定。
三、 算法设计
1.主要思想
题目要求用弗洛伊德算法求没对顶点之间的最短路径，则需要用矩阵来存储点与点之间的路径大小和点与点之间最短路径所经过的几个点。下面用一个简单地例子来讲述这个算法的实现：
A 7 B
1
2
C 3 2 D
我们这里使用的是有向图，无向图和此类似。（用-1表示不能到达）
有向图的关系矩阵：
D(-1) P(-1)
A B C D A B C D
A 0 7 2 -1 A AB AC
B -1 0 -1 1 B BD
C -1 3 0 -1 C CB
D 2 -1 -1 0 D DA
添加顶点A：
D(0) P(0)
A B C D A B C D
A 0 7 2 -1 A AB AC
B -1 0 -1 1 B BD
C -1 3 0 -1 C CB
D 2 9 4 0 D DA DAB DAC
添加顶点B：
D(1) P(1)
A B C D A B C D
A 0 7 2 8 A AB AC ABD
B -1 0 -1 1 B BD
C -1 3 0 4 C CB CBD
D 2 9 4 0 D DA DAB DAC
添加顶点C：
D(2) P(2)
A B C D A B C D
A 0 5 2 6 A ACB AC ABCD
B -1 0 -1 1 B BD
C -1 3 0 4 C CB CBD
D 2 7 4 0 D DA DACB DAC
添加顶点D：
D(3) P(3)
A B C D A B C D
A 0 5 2 6 A ACB AC ABCD
B 3 0 5 1 B BDA BDC BD
C 6 3 0 4 C CDA CB CBD
D 2 7 4 0 D DA DACB DAC
以上就是算法实现的过程，D矩阵保存最小路径的值，P矩阵保存最短路径。
2、程序包含两个模块
主函数部分，首先输入顶点个数然后连着输入三个整数A,B,C分别表示顶点A到顶点B的权值C。然后输入连着输入三个0，表示输入结束！
类里面包含关于弗洛伊德算法和所需的存储结构，详情见代码！
四、 调试分析
在处理数字型变量，转换成string类型出现了很多错误。而且用二维数组存储数据时出现了错误，不过这些问题都解决了。具体见代码。
五、 实验结果
六、 总结
理想和现实总是有差距的，不要眼高手低。
七、 源程序（带注释）
#include<iostream>
#include<string>
using namespace std;
class shortpath //最短路径类
{
public:
shortpath(int a) // 构造函数
{
n=a;
p=new int* [n+1]; //动态分配内存生成二维动态数组可以用
q=new string* [n+1]; //下标直接访问
for(int i=1;i<=n;i++)
{
p[i]=new int[n+1];
q[i]=new string[n+1];
}
for(int k=1;k<=n;k++) // 给内存初始化
{
for(int j=1;j<=n;j++)
{
if(k==j)
p[k][j]=0;
else
p[k][j]=9999;
}
}
}
~shortpath() //析构函数 要分两步析构
{
for(int i=1;i<=n;i++)
{
delete []p[i];
delete []q[i];
}
delete []p;
delete []q;
}
void add(int a,int b,int c) //插入函数，用于添加边和权值信息
{
p[a][b]=c;
q[a][b]="";
char s1=(char)a+'0';
char s2=(char)b+'0';
q[a][b]+=s1;
q[a][b]+=s2;
}
void lala() //弗洛伊得所发实现
{ //算法复杂度O（n^3）,不适合较大数据量的计算
for(int i=1;i<=n;i++)
for(int k=1;k<=n;k++)
{
if(k==i)
;
else
{
for(int j=1;j<=n;j++)
{
if(j==i||j==k)
;
else
{
if(p[k][j]>p[k][i]+p[i][j])
{
int tem=0;
if(p[k][j]==9999)
tem=1;
p[k][j]=p[k][i]+p[i][j];
char s2=(char)i+'0';
if(tem==1)
{
q[k][j]="";
chars1=(char)k+'0';
// char s2=(char)i+'0';
chars3=(char)j+'0';
q[k][j]+=s1;
q[k][j]+=s2;
q[k][j]+=s3;
}
else
q[k][j].insert(q[k][j].end()-1,s2);
}
}
}
}
}
}
void mprint() //对关系矩阵信息的打印
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cout<<i<<"->"<<j<<"最短路径长度为："<<p[i][j]<<endl;
if(p[i][j]==9999||p[i][j]==0)
cout<<" 无法到达或是自己到自己！"<<endl;
else
cout<<q[i][j]<<endl;
}
}
private:
int **p;
int n;
string **q;
};
int main()
{
int a,b,c;
int n;
cin>>n;
shortpath path(n);
/*cin>>a>>b>>c;
path.add(a,b,c);
path.lala();
path.mprint();*/
while(cin>>a>>b>>c)
{
if(a==0)
break;
path.add(a,b,c);
}
path.lala();
path.mprint();
return 0;
}