算法分析研究与方案实验报告单源最短路径最小生成树.docx

个人收集整理 仅供参考学习
实验报告
课程 计算机算法设计与分析 实验名称 单源最短路径、最小生成树
学号 姓名 实验日期：
实验三
单源最短路径、最小生成树
一．
for (i=0;i<=n;i++)
{c[i]=new int [n+1];}
2 / 8
个人收集整理 仅供参考学习
getdata(c,n); //获取数据
int begin=1,end;
cout<<" 请输入所求单源路径地 起点 终点： ";
cin>>begin>>end;
v=begin;
Dijkstra(n,v,dist,prev,c); //计算路径
PrintPath(prev,n,begin,end); // 输出路径
}
最小生成树问题地程序代码如下：
#include""
#include""
#include""
#include <>
#include <>
#include <>
#define MAX_VERTEX_NUM 20 // 最大顶点个数
#define MAX_NAME 3 // 顶点字符串地最大长度 +1 #define MAX_INFO 20 // 相关信息字符串地最大长度 +1
#define INFINITY INT_MAX // 用整型最大值代替∞
typedef int VRType;
typedef char InfoType;
typedef char VertexType[MAX_NAME];
// 邻接矩阵地数据结构
typedef struct
{ VRType adj; // 顶点关系类型 .对无权图，用 1(是 )或 0(否 )表示相邻否；
// 对带权图，则为权值类型
InfoType *info; // 该弧相关信息地指针 (可无 )
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; RTCrpUDGiT
// 图地数据结构
typedef struct
{ VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量
AdjMatrix arcs; // 邻接矩阵
int vexnum, // 图地当前顶点数
arcnum; // 图地当前弧数
} MGraph;
记录从顶点集 U 到 V-U 地代价最小地边地辅助数组定义
typedef struct
{VertexType adjvex;
VRType lowcost;
3 / 8
个人收集整理 仅供参考学习
}minside[MAX_VERTEX_NUM];
// 若 G 中存在顶点 u,则返回该顶点在图中位置 ;否则返回 -1. int LocateVex(MG