Prim算法-最小生成树-创新互联
最小生成树是指一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。
Prim算法：图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点(英语:Vertex (graph theory))，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克(英语:Vojtěch Jarník)发现;并在1957年由美国计算机科学家罗伯特·普里姆(英语:Robert C. Prim)独立发现;1959年，艾兹格·迪科斯彻再次发现了该算法。
思路：将结点分为标记点和未标记点，任取一个初始点作为标记点，依次从未标记点中找到里标记点最短的一条路径，并将该未标记点纳入标记点内，依次重复执行，直至所有点均为标记点。
分析：
1、以0作为初始点，记为第一个标记点。从未标记点中寻找离0最近的一点1，将1纳入标记点。
2、再以0、1位对象，寻找离0或1最近的未标记点2，将2纳入标记点。
3、同理，再以0、1、2为对象，寻找到未标记点4。
4、依次类推，得到5。
5、最后一点3。
代码实现(C语言)：
#include#include#define N 10000
typedef struct Ver {
char id;
struct Ver *father;
int minLength;
int flag;//1 标记，0未标记
} Ver,*Vertex;
//初始化结构体指针数组
void InitialVertex(Vertex vertex[]) {
//让0作为初始点
vertex[0]=(Vertex)malloc(sizeof(Ver));
vertex[0]->id='0';
vertex[0]->father=NULL;
vertex[0]->minLength=0;//无所谓
vertex[0]->flag=1;
for(int i=1; i<6; i++) {
vertex[i]=(Vertex)malloc(sizeof(Ver));
vertex[i]->id=i+'0';
vertex[i]->minLength=N;
vertex[i]->flag=0;
}
return;
}
//寻找李标记点最短的未标记点
int FindVer(Vertex vertex[],int matrix[][6]) {
int M=10000;
int order;//接收未标记点下标
//遍历未标记点
for(int i=0; i<6; i++) {
if(vertex[i]->flag==0) {
//遍历标记点
for(int j=0; j<6; j++) {
if(vertex[j]->flag!=0) {
int all_p=matrix[i][j];
//寻找最短路径
if(all_pfather=vertex[j];
vertex[i]->minLength=all_p;
order=i;
M=all_p;
}
}
}
}
}
return order;
}
//建立最小生成树
void BuildMinTree(Vertex vertex[],int matrix[][6]) {
//一共要寻找5次
for(int i=0; i<5; i++) {
int order=FindVer(vertex,matrix);//接受未标记点
vertex[order]->flag=1;//将未标记点转化为标记点
printf("第%d次，选择的结点为%c,路径长度为%d,连接关系为(%c,%c)\n",i+1,vertex[order]->id,vertex[order]->minLength,vertex[order]->id,vertex[order]->father->id);
}
}
int main() {
int matrix[6][6]= {
{ N, 3, 5, N, N, N },
{ 3, N, 2, 7, 4, N },
{ 5, 2, N, N, 3, N },
{ N, 7, N, N, N, 2 },
{ N, 4, 3, N, N, 1 },
{ N, N, N, 2, 1, N }
};
Vertex vertex[6];
InitialVertex(vertex);
BuildMinTree(vertex,matrix);
return 0;
} 代码实现(Java):
import java.util.ArrayList;
import java.util.List;
public class Prim {
final static int N = 10000;
static int[][] matrix = new int[6][6];
public static void main(String[] args) {
// TODO Auto-generated method stub
matrix[0] = new int[] { N, 3, 5, N, N, N };
matrix[1] = new int[] { 3, N, 2, 7, 4, N };
matrix[2] = new int[] { 5, 2, N, N, 3, N };
matrix[3] = new int[] { N, 7, N, N, N, 2 };
matrix[4] = new int[] { N, 4, 3, N, N, 1 };
matrix[5] = new int[] { N, N, N, 2, 1, N };
// 建立标记点集合
Listmarked = new ArrayList();
// 默认使0作为初始点
marked.add(new Vertexs(0, null, 0));
// 建立未标记点集合
ListunMarked = new ArrayList();
// 将其他结点作为未标记点添加到集合中
for (int i = 1; i<= 5; i++) {
unMarked.add(new Vertexs(i, null, N));
}
int count=1;
//将未标记点集合中的点转移到已标记点集合
while (!unMarked.isEmpty()) {
Vertexs ver = findVer(marked, unMarked);
marked.add(ver);
unMarked.remove(ver);
System.out.println("第"+(count++)+"次，选择的结点为"+ver.id+",路径长度为"+ver.minLength+",连接关系为("+ver.father.id+","+ver.id+")");
}
}
public static Vertexs findVer(Listmarked, ListunMarked) {
int M = 10000;
Vertexs v = null;
for (Vertexs ve : unMarked) {
for (Vertexs vr : marked) {
int all_p = matrix[vr.id][ve.id];
if (all_p< M) {
ve.minLength = all_p;
ve.father = vr;
M=all_p;
v=ve;
}
}
}
return v;
}
}
class Vertexs {
public int id;
public Vertexs father;
public int minLength = 10000;
public Vertexs(int id, Vertexs father, int minLength) {
this.id = id;
this.father = father;
this.minLength = minLength;
}
} 一言：
不是每一场雨都有彩虹，但是晴天总会到来。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
网站标题：Prim算法-最小生成树-创新互联
分享地址：http://6mz.cn/article/ddpsjs.html