|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
#include <iostream>
using namespace std;
#define MAXSIZE 100
#define INFINITY 65535
typedef int ElemType;
typedef char VertexType;
typedef struct MGraph{
VertexType vertex[MAXSIZE];///顶点表
ElemType arc[MAXSIZE][MAXSIZE];///邻接矩阵,可看作边表
ElemType vertexNum, arcNum;///vertexNum是顶点数,arcNum是边数
};
typedef struct EdgeNode{
int begin;
int end;
int weight;
};
void CreateMGraph(MGraph *G) {
int i, j, k ,n;
cout << "输入边数和顶点数:";
cin >> G->arcNum >> G->vertexNum;
///输入顶点
cout << "输入顶点" << endl;
for (i = 0; i < G->vertexNum; i++) {
cin >> G->vertex[i];
}
///初始化矩阵
for (i = 0; i < G->vertexNum; i++) {
for (j = 0; j < G->vertexNum; j++) {
G->arc[i][j] = G->arc[j][i] = INFINITY;
G->arc[i][i] = 0;
}
}
///输入由顶点构成的边
for (k = 0; k < G->arcNum; k++) {
cout << "请输入与边关联的两个顶点的序号和权值,例如( 1 2 34):" << endl;
cin >> i>>j>>n;
G->arc[i][j] = n;
G->arc[j][i] = G->arc[i][j];
}
}
///交换边集数组中的元素
void swap(EdgeNode edges[], int i ,int j){
int temp ;
temp = edges[i].begin;
edges[i].begin = edges[j].begin;
edges[j].begin = temp;
temp=edges[i].end;
edges[i].end = edges[j].end;
edges[j].end = temp;
temp = edges[i].weight;
edges[i].weight = edges[j].weight;
edges[j].weight = temp;
}
///排序
void Bubblesort(MGraph G,EdgeNode edges[]){
int i , j ;
for( i = 0 ; i < G.vertexNum; i++)
{
for(j = 0 ; j < G.vertexNum; j++)
{
if( edges[j].weight > edges[j+1].weight)
{
swap(edges,j,j+1);
}
}
}
}
int Find(int partent[],int f){
while( partent[f] > 0)
{
f =partent[f];
}
return f;
}
void MiniSpanTree_Kruskal(MGraph G){
int i, j, n, m;
int k = 0;
int parent[MAXSIZE];
EdgeNode edges[MAXSIZE];
cout<<"起点"<<"\t"<<"终点"<<"\t"<<"权值"<<endl;
///将这个邻接矩阵变为边集数组
for( i = 0 ;i < G.vertexNum - 1;i++)
{
for(j = i + 1; j <G.vertexNum; j++)
{
if(G.arc[i][j] < INFINITY)
{
edges[k].begin = i;
edges[k].end = j;
edges[k].weight=G.arc[i][j];
k++;
}
}
}
Bubblesort(G,edges);
/****************************/
///初始化数组
for(i = 0; i < G.vertexNum; i++)
{
parent[i] = 0;
}
///打印最小生成树
for(i = 0;i < G.arcNum; i++)
{
n=Find(parent,edges[i].begin);
m=Find(parent,edges[i].end);
if( n != m) ///如果相等则说明形成了环状
{
parent[n] = m; ///partent第n(是起点)个位置存放终点坐标
cout<<edges[i].begin<<"\t"<<edges[i].end<<"\t"<<edges[i].weight<<endl;
}
}
}
int main() {
MGraph G;
CreateMGraph(&G);
MiniSpanTree_Kruskal(G);
return 0;
}
鉴于其他几个都要收费,我就免费给大家提供一段自己的代码,方便大家自己理解 |
|