数据结构小学期-算法演示程序实验报告(3)

石家庄铁道大学实习报告

cout << endl; } }

5．调试分析

1. 书本上的伪代码大多都没有初始化,注意初始化即可。 2. 调试时要多增加几个断点和监视对象。

6．使用说明

程序名为 algorithms.exe，运行环境为 DOS。程序执行后显示

***********************欢迎来到算法演示程序************************************ 1.Prim 算法 2.Kruskal算法 3.Floyd算法 4.Dijkstra算法 5.退出 请选择您的操作：

在” 请选择您的操作：”后输入数字选择执行不同的功能。

选择 1：执行Prim算法,输入结点及边的总数，起点终点和权值 选择 2：执行Kruskal算法，输入结点及边的总数，起点终点和权值 选择 3：执行Floyd算法 输入结点及边的总数，起点终点和权值 选择4：执行Dijkstra算法输入结点及边的总数，起点终点和权值 选择5：退出程序

7．测试结果

图 1

11 / 22

石家庄铁道大学实习报告

图 2

图 3

8.附录

/*4、 Prim 算法 输入：无向图（顶点序列，边序列） 功能要求：输出最小生成树的各组成边及最小生成树的权值 5、 Kruskal 算法 输入：无向图（顶点序列，边序列） 功能要求：输出最小生成树的各组成边及最小生成树的权值

6、 Floyd 算法 输入：有向图（顶点序列，有向边序列） 功能要求：输出各顶点对间最短

12 / 22

石家庄铁道大学实习报告

路径和路径长度 7、 Dijkstra 算法

输入：有向图（顶点序列，有向边序列），起始顶点 功能要求：输出起始顶点到其它各顶点的最短路径和路径长度*/ //于博 20153236 2017/6/30 #include #include

#include //增强程序可移植性，包含最值宏定义 using namespace std; #include \#include \#define Max 100

#define MAX_VALUE 1000 //宏定义 #define MAX_VERTEX_COUNT 20

//------------------------------------------Prim算法--------------------------------------------------// //树结构体 struct Tree{ int **a; int *v; int *e;

int v1; //叶子结点总数 int e1; //边的总数 };

int ok(Tree &t,int k){ int l=0;

while(l

if(t.v[l]==k){ return 0;} l++; }

return 1; }

//判断函数--是否树包含图的所有结点 void judge(Tree &t){ t.v[0]=1;

for(int i=1;i

int biaoji1=10000; //标记无穷大 int biaoji2=0; int biaoji3=0;

for(int j=0;j

for(int k=1;k<=t.v1;k++){ if(t.a[m][k]

13 / 22

石家庄铁道大学实习报告

if(ok(t,k)){

biaoji1=t.a[m][k]; biaoji2=m; biaoji3=k; } } } }

t.v[i]=biaoji3; t.e[2*i-1]=biaoji2; t.e[2*i]=biaoji3; } }

//调用prim算法相关所有代码 void show_prim(){

int x,y; //起点、终点 Tree t; //树 int n,m;

int m1,m2; //起点、终点 int count; ////权值计数 int sum=0; //权值之和 cout<<\请输入图的点数和边数\输入提示 cin>>n>>m;

t.v1=n; //给树的结点总数和边的结点总数赋值 t.e1=m;

t.v=new int[n]; //结点数组 for(int i=0;i

t.e=new int[2*n-1]; //边与结点数的关系 for(int i=0;i<2*n-1;i++) //循环 初始化 t.e[i]=0; t.a=new int *[n+1]; for(int i=0;i<=n;i++) t.a[i]=new int[n+1];

cout<<\请依次输入各边的两端点及权值\ for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

t.a[i][j]=10000; //初始化为无穷大 for(int i=1;i<=m;i++){ //for循环输入 cin>>m1>>m2>>count;

t.a[m1][m2]=count; //无向网赋值 t.a[m2][m1]=count; }

judge(t); //判断是否有全部叶子节点

14 / 22

石家庄铁道大学实习报告

cout<<\最小生成树为：\ for(int i=1;i

cout<

cout<<\最小生成树的权值之和为：\}

//--------------------------------------prim算法结束-----------------------------------------------------// //--------------------------------------kruskal算法

------------------------------------------------------// int Father[Max]; //结点结构体 struct Node { int Next;

int Weight; //权重 int Priority; //优先级 };

int Find(int x){ //查

if(x==Father[x]) return x; else return Find(Father[x]); }

void Union(int x,int y){ //并 Father[x]=y ; }

int Top,Edge;

bool Com(Node x,Node y){

return x.Weight

dequeMap;

//调用克鲁斯卡尔的相关代码 void show_kruskal() {

cout<<\请输入结点个数及边数：\ cin>>Top>>Edge; int i,j; Node y;

cout<<\请依次输入两点及权值：\ for(i=1;i<=Top;i++) for(j=1;j<=Top;j++){ int x; cin>>x;

15 / 22