普里姆算法—Prim算法

1. 问题描述

最小生成树在实际运用中又很大的作用，试用prim算法实现最小生成树。

2. 设计要求

利用prim算法

3. 数据结构

本课程设计采用顺序表作为实现该问题的数据结构具体定义如下：

#include

using namespace std;

#define MAX 100

typedef struct

{

int no;//顶点信息

int flag;

}*M, MM;

typedef struct

{

int m[MAX][MAX];//邻接矩阵

int vexnum, arcnum; //顶点数，弧数

MM vexs[MAX];//存放顶点信息

}MG, *MGraph;

void Init(MGraph &mg, int n);

void CreateAdjMatrix(MGraph &mg);

void Prim(MGraph &mg, int n);

4. 分析与实现

（1） 初始化存储模块

void Init(MGraph &mg, int n)//初始化

{

mg = new MG;

mg->vexnum = n;

for (int i = 1; i <= mg->vexnum; i++)

{

for (int j = 1; j <= mg->vexnum; j++)

mg->m[i][j] = 1000;

mg->vexs[i].no = i;

mg->vexs[i].flag = 0;

}

}

void CreateAdjMatrix(MGraph &mg) //带权无向邻接矩阵的建立算法

{

MGraph g = mg;

cout << "请输入弧的数目：";

cin >> g->arcnum;

int i, j, w; cout << "请输入顶点以及之间的边的权值：" << endl;

for (int k = 0; karcnum; k++)

Prim算法

Prim 算法

普⾥姆算法介绍

普⾥姆 (Prim) 算法，是⽤来求加权连通图的最⼩⽣成树的算法。

基本思想对于图 G ⽽⾔，V 是所有顶点的集合；现在，设置两个新的集合 U 和 T，其中 U ⽤于存放 G 的最⼩⽣成树中的顶点，T 存放 G 的最⼩⽣成树中的边。 从所有 uЄU，vЄ(V-U) (V-U 表⽰出去 U 的所有顶点)的边中选取权值最⼩的边 (u, v)，将顶点 v 加⼊集合 U 中，将边(u, v) 加⼊集合 T 中，如此不断重复，直到U=V 为⽌，最⼩⽣成树构造完毕，这时集合 T 中包含了最⼩⽣成树中的所有边。

普⾥姆算法图解

以上图 G4 为例，来对普⾥姆进⾏演⽰ (从第⼀个顶点 A 开始通过普⾥姆算法⽣成最⼩⽣成树)。

初始状态：V 是所有顶点的集合，即 V={A,B,C,D,E,F,G}；U 和 T 都是空！第 1 步：将顶点 A 加⼊到 U 中。此时，U={A}。第 2 步：将顶点 B 加⼊到 U 中。上⼀步操作之后，U={A}, V-U={B,C,D,E,F,G}；因此，边 (A,B) 的权值最⼩。将顶点 B 添加到 U 中；此时，U={A,B}。第 3 步：将顶点 F 加⼊到 U 中。上⼀步操作之后，U={A,B}, V-U={C,D,E,F,G}；因此，边 (B,F) 的权值最⼩。将顶点 F 添加到 U 中；此时，U={A,B,F}。第 4 步：将顶点 E 加⼊到 U 中。上⼀步操作之后，U={A,B,F}, V-U={C,D,E,G}；因此，边 (F,E) 的权值最⼩。将顶点 E 添加到 U 中；此时，U={A,B,F,E}。第 5 步：将顶点 D 加⼊到 U 中。上⼀步操作之后，U={A,B,F,E}, V-U={C,D,G}；因此，边 (E,D) 的权值最⼩。将顶点 D 添加到 U 中；此时，U={A,B,F,E,D}。第 6 步：将顶点 C 加⼊到 U 中。上⼀步操作之后，U={A,B,F,E,D}, V-U={C,G}；因此，边 (D,C) 的权值最⼩。将顶点 C 添加到 U 中；此时，U={A,B,F,E,D,C}。第 7 步：将顶点 G 加⼊到 U 中。上⼀步操作之后，U={A,B,F,E,D,C}, V-U={G}；因此，边 (F,G) 的权值最⼩。将顶点 G 添加到 U 中；此时，U=V。

数据结构普里姆算法

普里姆算法（Prim'salgorithm）是一种贪心算法，用于在加权无向图中找到最小生成树。该算法在每一步选择当前生成树到最远未连接点的最小边，直到所有的点都被连接起来。以下是普里姆算法的基本步骤：1.随机选择图中的一点作为起始点，将其加入生成树集合中。2.在所有连接已选择点和未选择点的边中，选择权重最小

的边。将这条边以及其对应的未选择点加入到生成树集合中。3.重复步骤2，直到所有的点都被加入到生成树集合中。下面是使用Python实现的普里姆算法示例：```python

importheapq

defprim(graph,start):

mst={}#最小生成树的键值对，键为节点，值为

该节点所在的最小权重边visited=set([start])#已访问的节点集合

edges=[#用于存储最小权重边的优先队列，键为

权重，值为边的信息(weight,start,to)

forto,weightingraph[start].items()]

heapq.heapify(edges)

whileedges:

weight,frm,to=heapq.heappop(edges)

iftonotinvisited:visited.add(to)

mst[to]=(frm,weight)#将边加入最小

生成树中forto_next,weight2in

graph[to].items():ifto_nextnotinvisited:heapq.heappush(edges,

(weight2,to,to_next))#将相邻未访问节点加入优先队列中returnmst

```

其中，`graph`是一个字典，表示无向图的邻接表形式。字典的键表示节点，值是另一个字典，表示与该节点相邻的节

点及其对应的权重。`start`是算法的起始点。函数返回一个字典，表示最小生成树，其中键是节点，值是该节点所在的

最小权重边。边的信息由起始节点、权重和目标节点组成。

最⼩⽣成树---普⾥姆算法（Prim算法）和克鲁斯卡尔算法

（Kruskal算法）

最⼩⽣成树的性质：MST性质（假设N=(V,{E})是⼀个连通⽹，U是顶点集V的⼀个⾮空⼦集，如果（u，v）是⼀条具有最⼩权值的边，

其中u属于U，v属于V-U，则必定存在⼀颗包含边（u，v）的最⼩⽣成树）

普⾥姆算法（Prim算法)

思路：以点为⽬标构建最⼩⽣成树

1.将初始点顶点u加⼊U中，初始化集合V-U中各顶点到初始顶点u的权值；

2.根据最⼩⽣成树的定义：从n个顶点中，找出 n - 1条连线，使得各边权值最⼩。循环n-1次如下操作：

（1）从数组lowcost[k]中找到vk到集合U的最⼩权值边，并从数组arjvex[k] = j中找到该边在集合U中的顶点下标

(2)打印此边，并将vk加⼊U中。

（3）通过查找邻接矩阵Vk⾏的各个权值，即vk点到V-U中各顶点的权值，与lowcost的对应值进⾏⽐较，若更⼩则更新

lowcost，并将k存⼊arjvex数组中

以下图为例

#include

using namespace std;

#define MAXVEX 100

#define INF 65535

typedef char VertexType;

typedef int EdgeType;

typedef struct {

VertexType vexs[MAXVEX];

EdgeType arc[MAXVEX][MAXVEX];

int numVertexes, numEdges;

}MGraph;

void CreateMGraph(MGraph *G) {

int m, n, w; //vm-vn的权重w

scanf("%d %d", &G->numVertexes, &G->numEdges);

for(int i = 0; i < G->numVertexes; i++) {

getchar();

scanf("%c", &G->vexs[i]);