// Prim算法实现(采用邻接表存储).cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdafx.h"
#include<iostream>
#define MAX 100
#define Infinity 65535
typedef int WeiType;
using namespace std;
struct edgeNode
{
int no; //边端的序号
char info; //边端的名称
WeiType weight; //边的权值
struct edgeNode * next; //下一个
};
struct vexNode
{
char info; //节点名称
struct edgeNode *link; //与之相连的端点
};
//存储节点信息
vexNode adjlist[MAX];
//访问标志
bool visited[MAX];
//lowcost[j]存储从开始节点到节点j的最小花费
WeiType lowcost[MAX];
//parent[j]表示节点j的前驱节点
int parent[MAX];
//建立邻接表存储
void createGraph(vexNode *adjlist,const int n,const int e,const int v0)
{
int i;
for(i=1;i<=n;i++)
{
cout<<"请输入节点"<<i<<"的名称:";
cin>>adjlist[i].info;
adjlist[i].link = NULL;
//初始化
visited[i] = false;
lowcost[i] = Infinity;
parent[i] = v0;
}
edgeNode *p1,*p2;
int v1,v2;
WeiType weight;
for(i=1;i<=e;i++)
{
cout<<"请输入边"<<i<<"的二端的节点序号:";
cin>>v1>>v2;
cout<<"此边的权值:";
cin>>weight;
p1 = (edgeNode*)malloc(sizeof(edgeNode));
p2 = (edgeNode*)malloc(sizeof(edgeNode));
p1->no = v1;
p1->weight = weight;
p1->info = adjlist[v1].info;
p1->next = adjlist[v2].link;
adjlist[v2].link = p1;
p2->no = v2;
p2->weight = weight;
p2->info = adjlist[v2].info;
p2->next = adjlist[v1].link;
adjlist[v1].link = p2;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int cases;
cout<<"请输入案例的个数:";
cin>>cases;
while(cases--)
{
int n,e;
cout<<"请输入节点数:";
cin>>n;
cout<<"请输入边数:";
cin>>e;
cout<<"请输入从哪一个节点开始:";
int v;
cin>>v;
int i,j;
//最小生成树的权值总和
WeiType sum = 0;
createGraph(adjlist,n,e,v);
edgeNode *p,*q;
p = adjlist[v].link;
visited[v] = true;
while(p!=NULL)
{
lowcost[p->no] = p->weight;
p = p->next;
}
WeiType minCost;
for(i=1;i<n;i++)
{
minCost = Infinity;
int k;
for(j=1;j<=n;j++)
{
if(minCost>lowcost[j]&&!visited[j])
{
minCost = lowcost[j];
k = j;
}
}
sum += minCost;
visited[k] = true;
q = adjlist[k].link;
while(q != NULL)
{
if(!visited[q->no]&&q->weight<lowcost[q->no])
{
lowcost[q->no] = q->weight;
parent[q->no] = k;
}
q = q->next;
}
}
cout<<"最小生成树的边集为:"<<endl;
for(i=1;i<=n;i++)
if(i!=v)
cout<<"("<<adjlist[parent[i]].info<<","<<adjlist[i].info<<")"<<" ";
cout<<endl;
cout<<"最小生成树的权值为:"<<sum<<endl;
}
system("pause");
return 0;
}
-----------------------------------------------------程序测试--------------------------------------------------
请输入案例的个数:1
请输入节点数:9
请输入边数:14
请输入从哪一个节点开始:2
请输入节点1的名称:a
请输入节点2的名称:b
请输入节点3的名称:c
请输入节点4的名称:d
请输入节点5的名称:e
请输入节点6的名称:f
请输入节点7的名称:g
请输入节点8的名称:h
请输入节点9的名称:i
请输入边1的二端的节点序号:1 2
此边的权值:4
请输入边2的二端的节点序号:1 8
此边的权值:8
请输入边3的二端的节点序号:2 3
此边的权值:8
请输入边4的二端的节点序号:2 8
此边的权值:11
请输入边5的二端的节点序号:3 4
此边的权值:7
请输入边6的二端的节点序号:3 6
此边的权值:4
请输入边7的二端的节点序号:3 9
此边的权值:2
请输入边8的二端的节点序号:4 5
此边的权值:9
请输入边9的二端的节点序号:4 6
此边的权值:14
请输入边10的二端的节点序号:5 6
此边的权值:10
请输入边11的二端的节点序号:6 7
此边的权值:2
请输入边12的二端的节点序号:7 8
此边的权值:1
请输入边13的二端的节点序号:7 9
此边的权值:6
请输入边14的二端的节点序号:8 9
此边的权值:7
最小生成树的边集为:
(b,a) (b,c) (c,d) (d,e) (c,f) (f,g) (g,h) (c,i)
最小生成树的权值为:37
请按任意键继续. . .
分享到:
相关推荐
代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小...
最小生成树_Prim算法实现C++ 最小生成树_Prim算法实现C++ 最小生成树_Prim算法实现C++
基于MATLAB的最小生成树Prim算法 源代码程序.rar
最小生成树prim最小生成树prim最小生成树prim最小生成树prim
普里姆算法通过寻找无向图中权值最小的边,并且将其组合成最小生成树,也就是图的相对最短路径,同时将最小生成树以点集的形式输出,便于观察
prim算法 Kruskal算法分别实现最小生成树
用邻接表为存储结构的prim算法,程序中包括图的建立,图的深度优先遍历,和最小生成树prim算法
第2关求图(邻接表存储)最小生成树的普里姆(Prim)算法 第3关求图(邻接矩阵存储)最小生成树的克鲁斯卡尔(Kruskal)算法 第4关求图(邻接表存储)最小生成树的克鲁斯卡尔(Kruskal)算法 稳过 生成树是将图中...
图论算法:最小生成树——Prim算法和Kruskal算法C 实现
自己写的Prim算法,求最小生成树,若看不明白,请参看《算法导论》中的详细描述。
最小生成树的prim算法
本文本采用的是java编写的最小生成树Prim算法,参考书:计算机算法设计与分析
最小生成树,Prim算法的使用(邻接矩阵实现)
最小生成树Prim算法朴素版 C语言实现最小生成树Prim算法朴素版 C语言实现
最小生成树prim算法与克鲁斯算法实现,通过图的遍历和生成树求解实现(邻接矩阵、邻接表 —图的深度广度遍历算法的实现和最小生成树PRIM和KRUSCAL算法的实现)
基于matlab的最小生成树的prim算法,有详细的解释,可直接运行
acm 最小生成树 prim算法 用并查集实现 思路简单清晰,适合初学最小生成树的人
PRIM算法,C语言,VC6.0通过,直接复制。数据结构(清华版)实验。输入事例: 5 8//中间要空格 ABCDE AB 8 //中间要空格 AC 4 AE 3 BD 8 BE 6 CD 10 CE 13 DE 12 输出 AE 3 AC 4 BE 6 BD 8
这个程序使用关于prim算法生成最小生成树的问题,是用c++语言实现的。
用字符文件提供数据建立连通带权网络邻接矩阵存储¬¬结构。编写程序,用Prim算法求一棵最小生成树。要求输出最小生成树的各条边(用顶点无序偶表示)、各条边上的权值、最小生成树所有边上的权值之和。