图的最小生成树算法？

发布网友 发布时间：2022-04-19 09:43

我来回答

共3个回答

热心网友 时间：2023-06-21 22:14

图的生成树和最小生成树生成树(SpanningTree):如果一个图的子图是一个包含图所有节点的树,那这个子图就称为生成树.

热心网友 时间：2023-06-21 22:15

普利姆（prim）算法：
定义
普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图。

普利姆的算法如下：

图的顶点集合为V，设置一个顶点集合new_V，很明显new_V是V的一部分，设另一部分为other_V。

在new_V顶点与other_V顶点形成的所有边中，选择权值最小的一条，将该边的在other_V中的顶点移至new_V中，重复操作，直到new_V集合等于V集合，此时other_V为空，操作结束。
import java.util.*;
class t{
public static void main(String[] args){
char[] vertex=new char[]{'A','B','C','D','E','F','G'}; //顶点数组
int[][] ad_matrix=new int[7][];//邻接矩阵
final int N=65535;
ad_matrix[0]=new int[]{N,5,7,N,N,N,2};
ad_matrix[1]=new int[]{5,N,N,9,N,N,3};
ad_matrix[2]=new int[]{7,N,N,N,8,N,N};
ad_matrix[3]=new int[]{N,9,N,N,N,4,N};
ad_matrix[4]=new int[]{N,N,8,N,N,5,4};
ad_matrix[5]=new int[]{N,N,N,4,5,N,6};
ad_matrix[6]=new int[]{2,3,N,N,4,6,N};
Graph G=new Graph(vertex,ad_matrix); //构建图对象
//上述为测试用例
G.minimal();//最小生成树
}
}
class Graph{
private char[] vertex; //顶点数组
private int[][] ad_matrix;//邻接矩阵
private Vi_vertex vi;//已访问顶点集合
public Graph(char[] vertex,int[][] ad_matrix){
this.vertex=vertex;
this.ad_matrix=ad_matrix;
this.vi=new Vi_vertex(vertex.length);
}
public void minimal(){//最小生成树
vi.add(0);//选择下标为0的顶点作为出发顶点
while(!vi.done()){
prim();
}
}
private void prim(){//普利姆算法
int min=65535,index_x=0,index_y=0;
for(int i=0;i<vi.length();i++){
index_x=vi.get(i);
for(int j=0;j<ad_matrix[index_x].length;j++){
if(!vi.in(j)&&ad_matrix[index_x][j]<min){//顶点未被访问且边长较小
min=ad_matrix[index_x][j];//这里没有统计最小生成树的权值
index_y=j;//记录最小边位置
}
}
}
vi.add(index_y);
System.out.println(vertex[index_y]);
}
}
class Vi_vertex{//已访问顶点集合
private int[] visited;//已经存在的顶点集合
private int index=0;//顶点集合容量下标
public Vi_vertex(int length){
visited=new int[length];
}
public int length(){
return index;
}
public boolean in(int f){//判断顶点是否在已存在集合中
int i=0;
while(i<index){
if(visited[i]==f){
return true;
}
i++;
}
return false;
}
public void add(int f){//添加顶点到集合中
visited[index++]=f;
}
public boolean done(){//判断是否操作结束
return index==visited.length;//集合中保存所有顶点
}
public int get(int i){
return visited[i];
}

————————————————
克鲁斯卡尔（kruskal）算法：
基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。
具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。

#include "stdio.h"
#include "stdlib.h"
#define MAX_VERtEX_NUM 20
#define VertexType int
typedef struct edge{
VertexType initial;
VertexType end;
VertexType weight;
}edge[MAX_VERtEX_NUM];
//定义辅助数组
typedef struct {
VertexType value;//顶点数据
int sign;//每个顶点所属的集合
}assist[MAX_VERtEX_NUM];

assist assists;

//qsort排序函数中使用，使edges结构体中的边按照权值大小升序排序
int cmp(const void *a,const void*b){
return ((struct edge*)a)->weight-((struct edge*)b)->weight;
}
//初始化连通网
void CreateUDN(edge *edges,int *vexnum,int *arcnum){
printf("输入连通网的边数：\n");
scanf("%d %d",&(*vexnum),&(*arcnum));
printf("输入连通网的顶点：\n");
for (int i=0; i<(*vexnum); i++) {
scanf("%d",&(assists[i].value));
assists[i].sign=i;
}
printf("输入各边的起始点和终点及权重：\n");
for (int i=0 ; i<(*arcnum); i++) {
scanf("%d,%d,%d",&(*edges)[i].initial,&(*edges)[i].end,&(*edges)[i].weight);
}
}
//在assists数组中找到顶点point对应的位置下标
int Locatevex(int vexnum,int point){
for (int i=0; i<vexnum; i++) {
if (assists[i].value==point) {
return i;
}
}
return -1;
}
int main(){

int arcnum,vexnum;
edge edges;
CreateUDN(&edges,&vexnum,&arcnum);
//对连通网中的所有边进行升序排序，结果仍保存在edges数组中
qsort(edges, arcnum, sizeof(edges[0]), cmp);
//创建一个空的结构体数组，用于存放最小生成树
edge minTree;
//设置一个用于记录最小生成树中边的数量的常量
int num=0;
//遍历所有的边
for (int i=0; i<arcnum; i++) {
//找到边的起始顶点和结束顶点在数组assists中的位置
int initial=Locatevex(vexnum, edges[i].initial);
int end=Locatevex(vexnum, edges[i].end);
//如果顶点位置存在且顶点的标记不同，说明不在一个集合中，不会产生回路
if (initial!=-1&& end!=-1&&assists[initial].sign!=assists[end].sign) {
//记录该边，作为最小生成树的组成部分
minTree[num]=edges[i];
//计数+1
num++;
//将新加入生成树的顶点标记全不更改为一样的
for (int k=0; k<vexnum; k++) {
if (assists[k].sign==assists[end].sign) {
assists[k].sign=assists[initial].sign;
}
}
//如果选择的边的数量和顶点数相差1，证明最小生成树已经形成，退出循环
if (num==vexnum-1) {
break;
}
}
}
//输出语句
for (int i=0; i<vexnum-1; i++) {
printf("%d,%d\n",minTree[i].initial,minTree[i].end);
}
return 0;
}

热心网友 时间：2023-06-21 22:15

求图的最小生成树的算法有两种：
1.Kruskal算法（相对最好）
此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。
1. 把图中的所有边按代价从小到大排序；
2. 把图中的n个顶点看成独立的n棵树组成的森林；
3. 按权值从小到大选择边，所选的边连接的两个顶点ui,vi,应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。

2.Prim算法（基于贪心）
此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。
图的所有顶点集合为V；初始令集合u={s},v=V−u;在两个集合u,v能够组成的边中，选择一条代价最小的边(u0,v0)，加入到最小生成树中，并把v0并入到集合u中。
重复上述步骤，直到最小生成树有n-1条边或者n个顶点为止。
由于不断向集合u中加点，所以最小代价边必须同步更新；需要建立一个辅助数组closedge,用来维护集合v中每个顶点与集合u中最小代价边信息。