# 图的最小生成树之Prim算法

Prim算法基于贪心算法设计，其从一个顶点出发，选择这个顶点发出的边中权重最小的一条加入最小生成树中，然后又从当前的树中的所有顶点发出的边中选出权重最小的一条加入树中，以此类推，直到所有顶点都在树中，算法结束。

① 顶点a发出的边包括<a,b>和<a,d>和<a,f>，其中权重最小的边为<a,f>，于是我们将边<a,f>加入到最小生成树中，此时最小生成树包括下图中的阴影边和灰色顶点。

② 接下来我们继续从当前最小生成树中的顶点发出的所有边中寻找权重最小的一条，即边<a,b>、<a,d>、<f,c>中的边<a,d>，于是我们将边<a,d>加入到树中，如下图所示。

③ 继续上述步骤，从顶点a、f、d发出的边中选出权重最小的一条，即边<a,b>，并将它加入树中，如下图所示。

typedef struct GNode
{
int number;	// 顶点编号
struct GNode *next;
} GNode;

typedef struct Vertex
{
int number;
int weight;		// 边(p, v)的权重，用于最小生成树中记录该顶点到已有树的最小距离
int f;			// 在prim算法中表示该结点是否已被加入最小生成树中
struct Vertex *p;
} Vertex;

typedef struct Graph
{
Vertex *vertex;
int VertexNum;
} Graph;

// prim算法，输入图g的结点编号从1开始
void prim(Graph *g, int **w, int root)
{
Vertex *vs = g->vertex;
int vertexNum = g->VertexNum;

for (int i = 0; i < vertexNum; i++)
{
(vs + i)->weight = INF;
(vs + i)->p = NULL;
(vs + i)->f = 0;
}
(vs + root - 1)->weight = 0;

while (1)
{
int no = min(vs, vertexNum);
if (no == 0)
{
break;
}
Vertex *u = vs + no - 1;
u->f = 1;
GNode *link = links + no - 1;
while (link != NULL)
{
int weight = *((int *)w + (no - 1)*vertexNum + link->number - 1);
Vertex *v = vs + link->number - 1;
if (v->f == 0 && weight < v->weight)
{
v->weight = weight;
v->p = u;
}
}
}
}

int min(Vertex *vs, int num)
{
int min = INT_MAX;
int m = -1;
for (int i = 0; i < num; i++)
{
if ((vs + i)->f == 0 && (vs + i)->weight < min)
{
min = (vs + i)->weight;
m = i;
}
}
return m + 1;
}

	Graph graph;
graph.VertexNum = 5;
Vertex v[5];
Vertex v1; v1.number = 1; v1.p = NULL; v[0] = v1;
Vertex v2; v2.number = 2; v2.p = NULL; v[1] = v2;
Vertex v3; v3.number = 3; v3.p = NULL; v[2] = v3;
Vertex v4; v4.number = 4; v4.p = NULL; v[3] = v4;
Vertex v5; v5.number = 5; v5.p = NULL; v[4] = v5;
graph.vertex = v;

GNode nodes[5];
GNode n1; n1.number = 1;
GNode n2; n2.number = 2;
GNode n3; n3.number = 3;
GNode n4; n4.number = 4;
GNode n5; n5.number = 5;
GNode a; a.number = 3; GNode b; b.number = 4; GNode y; y.number = 5; n1.next = &a; a.next = &b; b.next = &y; y.next = NULL;
GNode c; c.number = 3; GNode x; x.number = 4; n2.next = &c; c.next = &x; x.next = NULL;
GNode d; d.number = 1; GNode e; e.number = 2; n3.next = &d; d.next = &e; e.next = NULL;
GNode f; f.number = 5; GNode g; g.number = 2; GNode j; j.number = 1; n4.next = &f; f.next = &g; g.next = &j; j.next = NULL;
GNode h; h.number = 4; GNode i; i.number = 1; n5.next = &h; h.next = &i; i.next = NULL;
nodes[0] = n1;
nodes[1] = n2;
nodes[2] = n3;
nodes[3] = n4;
nodes[4] = n5;

int w[5][5] = {	0,			INF,		4,			2,			5,
INF,		0,			2,			3,			INF,
4,			2,			0,			INF,		INF,
2,			3,			INF,		0,			1,
5,			INF,		INF,		1,			0 };
int root = 1;
prim(&graph, (int **)w, root);

for (int i = 0; i < graph.VertexNum; i++)
{
if (i != root - 1)
{
Vertex *v = graph.vertex + i;
printf("(%d, %d) ", v->p->number, v->number);
}
}

• 本文已收录于以下专栏：

## 图之prim算法

• TODD911
• 2013年07月03日 22:19
• 8571

## 最小生成树Prim算法理解

MST（Minimum Spanning Tree，最小生成树）
• yeruby
• 2014年08月16日 18:49
• 74712

## 贪心算法——Prim最小生成树

1、首先介绍一下什么是贪心算法： 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。ps：不懂得话可...

## 最小生成树-Prim算法和Kruskal算法

Prim算法 1.概览 普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (...

## prim最小生成树算法原理

prim 最小生成树算法原理 主要需要了解算法的原理、算法复杂度、优缺点 、刻画和度量指标 评价等 可以查阅相关的文献，这部分内容主要整合了两篇博客的内容 分别是：http://blog.csdn....

## 无向带权图的最小生成树算法——Prim及Kruskal算法思路

• lingzhm
• 2015年03月30日 16:09
• 4097

## Prim算法——求无向图的最小生成树

1212 无向图最小生成树 基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题  收藏  关注 N个点M条边的无向连通图，...

举报原因： 您举报文章：图的最小生成树之Prim算法 色情 政治 抄袭 广告 招聘 骂人 其他 (最多只允许输入30个字)
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "http://blog.csdn.net/Ivan_zgj/article/details/51547938", "fetch_time": 1513595265000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2017-51/segments/1512948615810.90/warc/CC-MAIN-20171218102808-20171218124808-00436.warc.gz", "warc_record_offset": 35943836, "warc_record_length": 13302, "token_count": 1877, "char_count": 3579, "score": 4.0, "int_score": 4, "crawl": "CC-MAIN-2017-51", "snapshot_type": "latest", "language": "en", "language_score": 0.2144809067249298, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00003-of-00064.parquet"}