最小生成树问题.doc
// 自定义头文件
#define Max_Num_Arcnum 100
typedef char VertexType;
typedef struct TreeNode {
VertexType ch;
int num;
}TreeNode; // 合并集合做标记
typedef struct Edge {
VertexType fromVertex;
VertexType toVertex;
int weight;
}Edge; // 存储边以及权值
typedef struct Graph {
int arcnum;
int vexnum;
Edge vertices[Max_Num_Arcnum]; // 数组存储边 }Graph; // 图
class KryskaNode
{
public:
// 输入数据初始化
void Scanf_Tree(VertexType node[],int vexnum,Edge edge[],int num);
// 显示最初输入数据
void Display();
// 生成最小生成树
void MinSpanTree();
private:
Graph graph;
int m_Sum; // 计算最低成本
TreeNode Node[Max_Num_Arcnum];
void Initial(VertexType node[]);
int Find(VertexType x);
void Merge(VertexType x,VertexType y);
void Sort();
};
// 自定义头文件 实现
#include
#include
#include
#include
using namespace std;
#include"minspantree.h"
// 输入数据初始化
void KryskaNode::Scanf_Tree(VertexType node[],int vexnum,Edge edge[], int arcnum)
{
int i;
m_Sum = 0;
graph.vexnum = vexnum;
graph.arcnum = arcnum;
Initial(node);
for(i=0;i graph.vertices[j].weight)
{
temp = graph.vertices[i];
graph.vertices[i] = graph.vertices[j];
graph.vertices[j] = temp;
}
}
}
// 主函数
#include
using namespace std;
#include"minspantree.h"
int main()
{
int num , i;
KryskaNode s;
while(true)
{
cout<<" *************************************"<>ch;
if(ch == '1') // 输入数据初始化
{
VertexType node[100];
int vexnum,arcnum;
cout<<"请输入顶点数目"<>vexnum;
cout<<"请分别输入这些顶点"<>node[i];
}
cout<<"输入边的个数"<>arcnum;
Edge edge[30];
char str;
while(true)
{
cout<<"*********************************"<>str;
if(str != 'Y' && str != 'y' && str !='N' && str != 'n')
cout<<"选择错误，重新选择!"<>edge[i].fromVertex>>edge[i].toVertex;
if(str == 'Y' ||str == 'y')
edge[i].weight = rand()% 100;
else
cin>>edge[i].weight;
}
s.Scanf_Tree(node,vexnum,edge,arcnum);
}
else if(ch == '2') // 计算最小生成树
{
s.Display();
}
else if(ch == '3')
{
s.MinSpanTree();
}
else if(ch == '0')
{
break;
}
else
{
cout<<"输入操作错误，请重新输入!"<
本文档为【最小生成树问题.doc】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483