邻接表实现prim算法c语言,最小生成树Prim算法实现（采用邻接表存储）C++实现

你的名字 2022-10-15 05:53 12阅读 0赞

// Prim算法实现(采用邻接表存储).cpp : Defines the entry point for the console application.

\#include "stdafx.h"

\#include

\#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<

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<

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

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->weightno\])

lowcost\[q->no\] = q->weight;

parent\[q->no\] = k;

q = q->next;

cout<

for(i=1;i<=n;i++)

if(i!=v)

cout<

system("pause");

return 0;

\-----------------------------------------------------程序测试--------------------------------------------------

![eab1a1573fc373088622fceef9af79a5.png][]

请输入案例的个数：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

请按任意键继续. . .

[eab1a1573fc373088622fceef9af79a5.png]: /images/20221014/7a3afd72e81449c5b68f2f25c8163ecf.png

邻接表实现prim算法c语言,最小生成树Prim算法实现（采用邻接表存储）C++实现

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 Prim算法的优化：邻接表、优先级队列 (堆) 优化(C语言实现)

相关最小生成树Prim实现(.)

相关鲁大师的最小生成树的Prim算法c++实现

相关邻接表实现prim算法c语言,最小生成树Prim算法实现（采用邻接表存储）C++实现

相关数据结构——邻接矩阵的最小生成树Prim算法

相关 Python 实现Prim最小生成树算法

相关最小生成树Prim算法实现（采用邻接表存储）C++实现

相关数据结构（C实现）------- 最小生成树之Prim算法

相关用于最小生成树的Prim算法实现

相关 prim算法--最小生成树