最小生成树_Prim算法实现C++.doc

最小生成树Prim算法实现的c +语言，使用邻接矩阵存储边信息。共三个文件。第一个#ifndef _PRIM_H_#define _PRIM_H_template int MinVertex(const AdjMatrixUndirNetwork &net, int *adjVex)/ 操作结果：返回w，使得边为连接V-U到U的具有最小权值的边int w = -1;/ 初始化最小顶点int v;/ 临时顶点for (v = 0; v 0)/ 存在从v到U的边(v, adjVexv) w = v;break; for (v+; v net.GetVexNum(); v+)/ 查找连接V-U到U的具有最小权值的边if (net.GetTag(v) = UNVISITED & net.GetWeight(v, adjVexv) 0 &net.GetWeight(v, adjVexv) net.GetWeight(w, adjVexw)w = v;return w;template void MiniSpanTreePrim(const AdjMatrixUndirNetwork &net, int u0)/ 初始条件：存在网net,u0为g的一个顶点/ 操作结果：用Prim算法从u0出发构造网g的最小代价生成树if (u0 = net.GetVexNum()throw Error(u0不合法1!);/ 抛出异常int *adjVex;/ 如果vV-U,net.GetWeight(v, adjVexv)0/ 表示(v, adjVexv)是v到U具有最小权值边的邻接点int u, v, w;/ 表示顶点的临时变量 adjVex = new intnet.GetVexNum();/ 分配存储空间for (v = 0; v net.GetVexNum(); v+)/ 初始化辅助数组adjVex，并对顶点作标志，此时U = v0if (v != u0)/ 对于vV-UadjVexv = u0;net.SetTag(v, UNVISITED);else/ 对于vUnet.SetTag(v, VISITED);adjVexv = u0;for (u = 1; u net.GetVexNum(); u+)/ 选择生成树的其余net.GetVexNum() - 1个顶点w = MinVertex(net, adjVex);/ 选择使得边为连接V-U到U的具有最小权值的边if (w = -1)/ 表示U与V-U已无边相连return;cout edge:( adjVexw , w ) weight: net.GetWeight(w, adjVexw)= 0 ; v = net.NextAdjVex(w, v)/ 新顶点并入U后重新选择最小边if (net.GetTag(v) = UNVISITED &/ v V - U(net.GetWeight(v, w) net.GetWeight(v, adjVexv) | / 边的权值更小net.GetWeight(v, adjVexv) = 0) ) / 不存在边/ 为新的最小边adjVexv = w;delete adjVex;/ 释放存储空间#endif第二个#ifndef _ADJ_MATRIX_UNDIR_GRAPH_H_#define _ADJ_MATRIX_UNDIR_GRAPH_H_#include utility.h/ 实用程序软件包/ 无向网的邻接矩阵类模板template class AdjMatrixUndirNetworkprotected:/ 邻接矩阵的数据成员:int vexNum, edgeNum;/ 顶点个数和边数WeightType *Matrix;/ 邻接矩阵ElemType *elems;/ 顶点数据mutable StatusCode *tag;/ 指向标志数组的指针WeightType infinity;/ 无穷大/ 辅助函数模板:void DestroyHelp();/ 销毁无向网,释放无向网占用的空间public:/ 抽象数据类型方法声明及重载编译系统默认方法声明:AdjMatrixUndirNetwork(ElemType es, int vertexNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);/ 构造顶点数据为es,顶点个数为vertexNum,infinit表示无穷大,边数为0的无向网AdjMatrixUndirNetwork(int vertexNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);/ 构造顶点个数为vertexNum,infinit表示无穷大,边数为0的无向网AdjMatrixUndirNetwork();/ 析构函数模板StatusCode GetElem(int v, ElemType &e) const;/ 求顶点的元素StatusCode SetElem(int v, const ElemType &e);/ 设置顶点的元素值WeightType GetInfinity() const;/ 返回无穷大 int GetVexNum() const;/ 返回顶点个数 int GetEdgeNum() const;/ 返回边数个数 int FirstAdjVex(int v) const;/ 返回顶点v的第一个邻接点 int NextAdjVex(int v1, int v2) const;/ 返回顶点v1的相对于v2的下一个邻接点 void InsertEdge(int v1, int v2, WeightType w);/ 插入顶点为v1和v2,权为w的边 void DeleteEdge(int v1, int v2);/ 删除顶点为v1和v2的边 WeightType GetWeight(int v1, int v2) const;/ 返回顶点为v1和v2的边的权值void SetWeight(int v1, int v2, WeightType w);/ 设置顶点为v1和v2的边的权值StatusCode GetTag(int v) const;/ 返回顶点v的标志 void SetTag(int v, StatusCode val) const;/ 设置顶点v的标志为val AdjMatrixUndirNetwork(const AdjMatrixUndirNetwork ©);/ 复制构造函数模样AdjMatrixUndirNetwork &operator =(const AdjMatrixUndirNetwork ©); / 重载赋值运算符;template void Display(const AdjMatrixUndirNetwork &g, bool showVexElem);/ 显示邻接矩阵无向网/ 无向网的邻接矩阵类的实现部分template AdjMatrixUndirNetwork:AdjMatrixUndirNetwork(ElemType es, int vertexNum, WeightType infinit)/ 操作结果：构造顶点数据为es,顶点个数为vertexNum,infinit表示无穷大,边数为0的无向网if (vertexNum 0)throw Error(顶点个数不能为负!);/ 抛出异常infinity = infinit;/ 无穷大vexNum = vertexNum;/ 顶点数为vertexNumedgeNum = 0;/ 边数为0elems = new ElemTypevexNum;/ 生成顶点数据标数组int iPos;/ 临时变量 for (iPos = 0; iPos vexNum; iPos+)/ 初始化标志数组elemsiPos = esiPos;tag = new StatusCodevexNum;/ 生成标志数组for (iPos = 0; iPos vexNum; iPos+)/ 初始化标志数组tagiPos = UNVISITED;Matrix = (WeightType *)new WeightType *vexNum;/ 生成邻接矩阵for (iPos = 0; iPos vexNum; iPos+)/ 生成邻接矩阵的行MatrixiPos = new WeightTypevexNum;for (iPos = 0; iPos vexNum; iPos+)for (int jPos = 0; jPos vexNum; jPos+)/ 为邻接矩阵元素赋值MatrixiPosjPos = infinity;template AdjMatrixUndirNetwork:AdjMatrixUndirNetwork(int vertexNum, WeightType infinit)/ 操作结果：构造顶点个数为vertexNum,infinit表示无穷大,边数为0的无向网if (vertexNum 0)throw Error(顶点个数不能为负!);/ 抛出异常infinity = infinit;/ 无穷大vexNum = vertexNum;/ 顶点数为vertexNumedgeNum = 0;/ 边数为0elems = new ElemTypevexNum;/ 生成顶点数据标数组int iPos;/ 临时变量 tag = new StatusCodevexNum;/ 生成标志数组for (iPos = 0; iPos vexNum; iPos+)/ 初始化标志数组tagiPos = UNVISITED;Matrix = (WeightType *)new WeightType *vexNum;/ 生成邻接矩阵for (iPos = 0; iPos vexNum; iPos+)/ 生成邻接矩阵的行MatrixiPos = new WeightTypevexNum;for (iPos = 0; iPos vexNum; iPos+)for (int jPos = 0; jPos vexNum; jPos+)/ 为邻接矩阵元素赋值MatrixiPosjPos = infinity;template void AdjMatrixUndirNetwork:DestroyHelp()/ 操作结果：销毁无向网,释放无向网占用的空间delete elems;/ 释放顶点数据delete tag;/ 释放标志for (int iPos = 0; iPos vexNum; iPos+)/ 释放邻接矩阵的行delete MatrixiPos;delete Matrix;/ 释放邻接矩阵template AdjMatrixUndirNetwork:AdjMatrixUndirNetwork()/ 操作结果：释放对象所占用空间DestroyHelp();template StatusCode AdjMatrixUndirNetwork:GetElem(int v, ElemType &e) const/ 操作结果：求顶点v的元素, v的取值范围为0 v vexNum, v合法时返回/SUCCESS, 否则返回RANGE_ERRORif (v = vexNum)/ v范围错return NOT_PRESENT;/ 元素不存在else/ v合法e = elemsv;/ 将顶点v的元素值赋给ereturn ENTRY_FOUND;/ 元素存在template StatusCode AdjMatrixUndirNetwork:SetElem(int v, const ElemType &e)/ 操作结果：设置顶点的元素值v的取值范围为0 v vexNum, v合法时返回/SUCCESS, 否则返回RANGE_ERRORif (v = vexNum)/ v范围错return RANGE_ERROR;/ 位置错else/ v合法elemsv = e;/ 顶点元素return SUCCESS;/ 成功template WeightType AdjMatrixUndirNetwork:GetInfinity() const/ 操作结果：返回无穷大return infinity;template int AdjMatrixUndirNetwork:GetVexNum() const/ 操作结果：返回顶点个数 return vexNum;template int AdjMatrixUndirNetwork:GetEdgeNum() const/ 操作结果：返回边数个数return edgeNum; template int AdjMatrixUndirNetwork:FirstAdjVex(int v) const/ 操作结果：返回顶点v的第1个邻接点 if (v = vexNum) throw Error(v不合法!);/ 抛出异常for (int cur = 0; cur vexNum; cur+)/ 查找邻接点if (Matrixvcur != infinity) return cur;return -1;/ 返回-1表示无邻接点template int AdjMatrixUndirNetwork:NextAdjVex(int v1, int v2) const/ 操作结果：返回顶点v1的相对于v2的下1个邻接点 if (v1 = vexNum) throw Error(v1不合法!);/ 抛出异常if (v2 = vexNum) throw Error(v2不合法!);/ 抛出异常if (v1 = v2) throw Error(v1不能等于v2!);/ 抛出异常for (int cur = v2 + 1; cur vexNum; cur+)/ 查找邻接点if (Matrixv1cur != infinity) return cur;return -1;/ 返回-1表示无邻接点template void AdjMatrixUndirNetwork:InsertEdge(int v1, int v2, WeightType w)/ 操作结果：插入顶点为v1和v2,权为w的边 if (v1 = vexNum) throw Error(v1不合法!);/ 抛出异常if (v2 = vexNum) throw Error(v2不合法!);/ 抛出异常if (v1 = v2) throw Error(v1不能等于v2!);/ 抛出异常if (w = infinity) throw Error(w不能为无空大!);/ 抛出异常if (Matrixv1v2 = infinity & Matrixv2v1 = infinity)/ 原无向网无边(v1, v2),插入后边数自增1edgeNum+;Matrixv1v2 = w;/ 修改的权值Matrixv2v1 = w;/ 修改的权值template void AdjMatrixUndirNetwork:DeleteEdge(int v1, int v2)/ 操作结果：删除顶点为v1和v2的边 if (v1 = vexNum) throw Error(v1不合法!);/ 抛出异常if (v2 = vexNum) throw Error(v2不合法!);/ 抛出异常if (v1 = v2) throw Error(v1不能等于v2!);/ 抛出异常if (Matrixv1v2 != infinity & Matrixv2v1 != infinity)/ 原无向网存在边(v1, v2),删除后边数自减1edgeNum-;Matrixv1v2 = infinity;/ 修改的权值Matrixv2v1 = infinity;/ 修改的权值template WeightType AdjMatrixUndirNetwork:GetWeight(int v1, int v2) const/ 操作结果：返回顶点为v1和v2的边的权值if (v1 = vexNum) throw Error(v1不合法!);/ 抛出异常if (v2 = vexNum) throw Error(v2不合法!);/ 抛出异常return Matrixv1v2;template void AdjMatrixUndirNetwork:SetWeight(int v1, int v2, WeightType w)/ 操作结果：设置顶点为v1和v2的边的权值if (v1 = vexNum) throw Error(v1不合法!);/ 抛出异常if (v2 = vexNum) throw Error(v2不合法!);/ 抛出异常if (v1 = v2) throw Error(v1不能等于v2!);/ 抛出异常if (w = infinity) throw Error(w不能为无空大!);/ 抛出异常Matrixv1v2 = w;/ 修改的权值Matrixv2v1 = w;/ 修改的权值template StatusCode AdjMatrixUndirNetwork:GetTag(int v) const/ 操作结果：返回顶点v的标志 if (v = vexNum) throw Error(v不合法!);/ 抛出异常return tagv;template void AdjMatrixUndirNetwork:SetTag(int v, StatusCode val) const / 操作结果：设置顶点v的标志为val if (v = vexNum) throw Error(v不合法!);/ 抛出异常tagv = val;template AdjMatrixUndirNetwork:AdjMatrixUndirNetwork(const AdjMatrixUndirNetwork ©)/ 操作结果：由无向网的邻接矩阵copy构造新无向网的邻接矩阵copy复制构造函数模样int iPos, jPos;/ 临时变量infinity =copy.infinity;/ 复制无穷大vexNum = copy.vexNum;/ 复制顶点数edgeNum = copy.edgeNum;/ 复制边数elems = new ElemTypevexNum;/ 生成顶点数据数组for (iPos = 0; iPos vexNum; iPos+)/ 复制顶点数据数组elemsiPos = copy.elemsiPos;tag = new StatusCodevexNum;/ 生成标志数组for (iPos = 0; iPos vexNum; iPos+)/ 复制标志数组tagiPos = copy.tagiPos;Matrix = (WeightType *)new WeightType *vexNum;/ 生成邻接矩阵for (iPos = 0; iPos vexNum; iPos+)/ 生成邻接矩阵的行MatrixiPos = new WeightTypevexNum;for (iPos = 0; iPos vexNum; iPos+)for (jPos = 0; jPos vexNum; jPos+)/ 复制邻接矩阵元素赋值MatrixiPosjPos = copy.MatrixiPosjPos;template AdjMatrixUndirNetwork &AdjMatrixUndirNetwork:operator =(const AdjMatrixUndirNetwork ©)/ 操作结果：将无向网的邻接矩阵copy赋值给当前无向网的邻接矩阵重载赋值运算符if (© != this)DestroyHelp();/ 释放当前无向网占用空间int iPos, jPos;/ 临时变量infinity =copy.infinity;/ 复制无穷大vexNum = copy.vexNum;/ 复制顶点数edgeNum = copy.edgeNum;/ 复制边数elems = new ElemTypevexNum;/ 生成顶点数据数组for (iPos = 0; iPos vexNum; iPos+)/ 复制顶点数据数组elemsiPos = copy.elemsiPos;tag = new StatusCodevexNum;/ 生成标志数组for (iPos = 0; iPos vexNum; iPos+)/ 复制标志数组tagiPos = copy.tagiPos;Matrix = (WeightType *)new WeightType*vexNum;/ 生成邻接矩阵for (iPos = 0; iPos vexNum; iPos+)/ 生成邻接矩阵的行MatrixiPos = new WeightTypevexNum;for (iPos = 0; iPos vexNum; iPos+)for (jPos = 0; jPos vexNum; jPos+)/ 复制邻接矩阵元素赋值MatrixiPosjPos = copy.MatrixiPosjPos;return *this;template void Display(const AdjMatrixUndirNetwork &net, bool showVexElem = true)/ 操作结果: 显示邻接矩阵无向网WeightType infinity = net.GetInfinity();for (int iPos = 0; iPos net.GetVexNum(); iPos+)/ 显示行if (showVexElem)/ 显示顶点元素ElemType e;/ 数据元素net.GetElem(iPos, e);/ 取出元素值cout e;/ 显示元素for (int jPos = 0; jPos net.GetVexNum(); jPos+)/ 显示元素if (net.GetWeight(iPos, jPos) = infinity)/ 显示无穷大cout t ;else/ 显示一般权值cout t net.GetWeight(iPos, jPos);cout endl;/ 换行 #endif第三个#ifndef _UTILITY_H_/ 如果没有定义_UTILITY_H_#define _UTILITY_H_/ 那么定义_UTILITY_H_/ 实用程序软件包#ifdef _MSC_VER/ 表示是VC #if _MSC_VER = 1200/ 表示VC6.0/ 标准库头文件#include / 标准串和操作#include / 标准流操作#include / 极限#include / 数学函数#include / 文件输入输出#include / 字符处理#include / 日期和时间函数#include / 标准库#include / 标准输入输出#include / 输入输出流格式设置#include / 支持变长函数参数#include / 支持断言#else/ 其它版本的VC+/ ANSI C+标准库头文件#include / 标准串和操作#include / 标准流操作#include / 极限#include / 数学函数#include / 文件输入输出#include / 字符处理#include / 日期和时间函数#include / 标准库#include / 标准输入输出#include / 输入输出流格式设置#include / 支持变长函数参数#include / 支持断言using namespace std;/ 标准库包含在命名空间std中#endif/ _MSC_VER = 1200#else/ 非VC / ANSI C+标准库头文件#include / 标准串操作#include / 标准流操作#include / 极限#include / 数据函数#include / 文件输入输出#include / 字符处理#include / 日期和时间函数#include / 标准库#include / 标准输入输出#include / 输入输出流格式设置#include / 支持变长函数参数#include / 支持断言using namespace std;/ 标准库包含在命名空间std中#endif/ _MSC_VER/ 自定义类型enum StatusCode SUCCESS, FAIL, UNDER_FLOW, OVER_FLOW,RANGE_ERROR, DUPLICATE_ERROR,NOT_PRESENT, ENTRY_INSERTED, ENTRY_FOUND, VISITED, UNVISITED;/ 宏定义#define DEFAULT_SIZE 1000/ 缺省元素个数#define DEFAULT_INFINITY 1000000/ 缺省无穷大/ 实用函数(模板)声明static char GetChar(istream &inStream = cin); / 从输入流inStream中跳过空格及制表符获取一字符static bool UserSaysYes();/ 当用户肯定回答(yes)时, 返回true, 用户否定回答(no)时,返回falsestatic void SetRandSeed();/ 设置当前时间为随机数种子static int GetRand(int n);/ 生成0 n-1之间的随机数static int GetRand();/ 生成随机数static int GetPoissionRand(double expectValue);/ 生成期望值为expectValue泊松随机数 template void Swap(ElemType &e1, ElemType &e2);/ 交换e1, e2之值templatevoid Display(ElemType elem, int n);/ 显示数组elem的各数据元素值template void Write(const ElemType &e);/ 显示数据元素/ 实用类class Timer;/ 定时器类Timerclass Error;/ 通用异常类static char GetChar(istream &inStream)/ 操作结果：从输入流inStream中跳过空格及制表符获取一字符char ch;/ 临时变量while (ch = (inStream).peek() != EOF/ 文件结束符(peek()函数从输入流中接受1/ 字符,流的当前位置不变)& (ch = (inStream).get() = / 空格(get()函数从输入流中接受1字符,流/ 的当前位置向后移1个位置)| ch = t);/ 制表符return ch;/ 返回字符static bool UserSaysYes()/ 操作结果: 当用户肯定回答(yes)时, 返回true, 用户否定回答(no)时,返回falsechar ch;/ 用户回答字符bool initialResponse = true;/ 初始回答do/ 循环直到用户输入恰当的回答为止if (initialResponse)/ 初始回答cout (y, n)?; else/ 非初始回答cout 用y或n回答:;while (ch = GetChar() = n);/ 跳过空格,制表符及换行符获取一字符initialResponse = false; while (ch != y & ch != Y & ch != n & ch != N);while (GetChar() != n);/ 跳过当前行后面的字符if (ch = y | ch = Y) return true;else return false;/ 定时器类Timerclass Timerprivate:/ 数据成员clock_t startTime;public:/ 方法声明Timer() startTime = clock();