图的最小生成树_范文大全网

范文一：图的最小生成树

#ifndef _ _MY_KRUSKAL_H_ _

#define _ _MY_KRUSKAL_H_ _

#include

template

struct KruskalEdge

{

int vertex1,vertex2;

WeightType weight;

KruskalEdge(int v1=-1,int v2=-1,int w=0):vertex1(v1),vertex2(v2),weight(w){};

};

template

bool operator <=(const> &first,const KruskalEdge &second) {

return first.weight<>

}

template

void MiniSpanTreeKruskal(const AdjListUndirNetwork &net)

{

int vexNum=net.GetVexNum();

Equivalence equival(vexNum);

MinPriorityLinkQueue<> >prioQ;

for (int v=0;v<>

{

for (int u=net.FirstAdjVex(v);u>=0;u=net.NextAdjVex(v,u))

{

if (v<>

{

KruskalEdgekEdge(v,u,net.GetWeight(v,u));

prioQ.InQueue(kEdge);

}

for (int count=0;count<>

{

KruskalEdgekEdge;

prioQ.OutQueue(kEdge);

if (equival.Differ(v1,v2))

{

cout

equival.Union(v1,v2);

}

#endif

#include

int _tmain(int argc, _TCHAR* argv[])

{

try

{

int infity=DEFAULT_INFINITY;

char vexs[]={'A','B','C','D'};

int m[4][4]={

{infity,2,3,4},

{2,infity,5,6},

{3,5,infity,7},

{4,6,7,infity}

};

int n=4;

AdjListUndirNetwork net(vexs,n);

for (int u=0;u<>

{

for (int v=0;v<>

{if (m[u][v]!=infity) net.InsertEdge(u,v,m[u][v]); }

}

cout

Display(net);

system(

cout

cout<>

}

catch (Error err)

{ err.Show();

}

system(

return 0;

}

范文二：图的最小生成树

图的最小生成树

如果用一个连通网表示n个居民点和各个居民点之间可能架设的通讯线路，则网中每一条边上的权值表示架设这条线路所需经费。由于在n个居民点间构建通讯网只需架设n-1条线路，则工程队面临的问题是架设哪几条线路能使总的工程费用最低?类似此类的问题很多，如第1章中的铺设煤气管道问题等。这些问题均等价于，在含有n个顶点的连通网中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称这棵连通子图为连通网的最小生成树。

一、克鲁斯卡尔(Kruskal)算法思想

克鲁斯卡尔算法的基本思想为:为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出n-1条互不构成回路的权值最小边为止。具体作法如下:首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。

由于生成树上不允许有回路，因此并非每一条居当前权值最小的边都可选，那么在算法中如何判别当前权值最小边的两个顶点之间是否已经连通?从生成树的构造过程可见，初始态为n个顶点分属n棵树，互不连通，每加入一条边，就将两棵树合并为一棵树，在同一棵树上的两个顶点之间自然相连通。由此判别当前权值最小边是否可取只要判别它的两个顶点是否在同一棵树上即可。

具体实现方法是以"双亲表示法"来表示树，并以各棵树的根结点作"树"的代号。

克鲁斯卡尔(Kruskal)算法

typedef struct{

VertexType vex1;

VertexType vex2;

VRType weight;

}EdgeType;

typedef ElemType EdgeType;

typedef struct{//有向网的定义

VertexType vexs[MAX_VERTEX_NUM];//顶点信息 EdgeType edge[MAX_EDGE_NUM];//边的信息

int vexnum,arcnum;//图中顶点的数目和边的数目 }ELGraph;

void MiniSpanTree_Kruskal(ELGraph G,SqList&MSTree)

{

//G.edge中依权值从小到大存放有向网中各边，按克鲁斯卡尔算法求得生

成树的边存放在顺序表MSTree中

MFSet F;

InitSet(F,G.vexnum);//将森林F初始化为n棵树的集合 InitList(MSTree,G.vexnum);//初始化生成树为空树 i=0;k=1;

while(k G.vexnum){

e=G.edge[i];//取第i条权值最小的边

r1=fix_mfset(F,LocateVex(e.vex1));

r2=fix_mfset(F,LocateVex(e.vex2));//返回两个顶点所在树的树根

if(r1～=r2){//选定生成树上第k条边

if(ListInsert(MSTree,k,e))k++;//插入生成树

mix_mfset(F,r1,r2);//将两棵树归并为一棵树

//继续考察下一条权值最小边 }//if i++;

}//while DestroySet(F);

}//MiniSpanTree_Kruskal

克鲁斯卡尔(Kruskal)算法分析

该算法的时间复杂度为O(elge);Kruskal算法的时间主要取决于边数,它较适合于稀疏图。

二、普里姆(Prim)算法思想

普里姆算法则从另一个角度构造连通网的最小生成树。它的基本思想是:首先选取图中任意一个顶点v作为生成树的根，之后继续往生成树中添加顶点w，则在顶点w和顶点v之间必须有边，且该边上的权值应在所有和v相邻接的边中属最小。在一般情况下，假设图G=(V,E)中已落在生成树上的顶点集为U，则尚未落在生成树上的顶点集为V-U，则从(V-U)顶点集中选取加入生成树的顶点w应满足下列条件:它和生成树上的顶点之间的边上的权值是在联接这两类顶点的所有边中权值属最小。

从上述生成树的构造过程中回还可以发现一点，即每个顶点都是通过"一条边"加入到生成树上的，因此对集合V-U中的每个顶点，当它和集合U中的顶点有一条以上的边相连时，只需要保留一条权值最小的边即可。由此，在普里姆算法中需要附设一个辅助数组closedge，以记录从集合U到集合V-U中每个顶点当前的权值最小边。

普里姆(Prim)算法代码:

typedef struct{

VertexType adjvex;

VRType lowcost;

}closedge[MAX_VERTEX_NUM];

上的权值，则对于集合V-U中每个顶点w，假设cost(u,w)表示边(u,w)

closedge[LocateVex(G,w)].lowcost=Min{cost(u,w)|u?U} void MiniSpanTree_PRIM(MGraph G,VertexType u,SqList&MSTree)

{

//G为数组存储表示的连通网，按普里姆算法从顶点u出发构造G的最小

生成树，顺序表MSTree中记录生成树的各条边

k=LocateVex(G,u);

InitList(MSTree,G.vexnum);//初始化生成树为空树

for(j=0;j G.vexnum;++j)//辅助数组初始化

if(j～=k)closedge[j]={u,G.arcs[k][j].adj};//{adjvex,lowcost}

closedge[k].lowcost=0;//初始状态，U={u}

for(i=1;i G.vexnum;++i){//选择其余G.vexnum-1个顶点 k=minimum(closedge);//求出T的下一个结点图中第k顶点 //此时

closedge[k].lowcost=Min{closedge[vi].lowcost|closedge[vi].lowcost

0,vi?V-U}

e.vex1=closedge[k].adjvex;

e.vex2=G.vexs[k];

e.weight=closedge[k].lowcost;

b=ListInsert(MSTree,i,e);//e为生成树的一条边 closedge[k].lowcost=0;//第k顶点并入U集

;j G.vexnum;++j) for(j=0

if(G.arcs[k][j].adj closedge[j].lowcost)

//新顶点并入U后重新选择最小边

closedge[j]={G.vexs[k],G.arcs[k][j].adj};

}//for

}//MiniSpanTree

普里姆(Prim)算法分析

该算法的时间复杂度为O(n2)。与图中边数无关，该算法适合于稠密图。

范文三：图的最小生成树

#include

#define INFINITY 100000 //最大值无穷大

#define MAX_VEX_NUM 20 //最大顶点数

typedef struct

{

char vexs[MAX_VEX_NUM]; //顶点向量

int arcs[MAX_VEX_NUM][MAX_VEX_NUM]; //邻接矩阵

int vexnum, arcnum; //图的当前顶点和弧数

}MGraph;

typedef struct

{

int adjvex;

int endvex;

int lowcost;

}closedge[MAX_VEX_NUM];

void CreateUDN (MGraph &G); //创建无向网络

int LocateVex (MGraph G, char v); //结点在顶点向量的下标

void PrintUDN (MGraph G); //输出存储结构示意图

void MiniSpanTree_PRIM (MGraph G, closedge &minedge); //求最小生成树的算法

void PrintMinEdge (MGraph G, closedge minedge); //输出最小生成树的边

int main()

{

MGraph G;

closedge minedge;

CreateUDN (G);

printf ("该图的邻接矩阵存储示意图如下：\n");

PrintUDN (G);

printf ("\n");

MiniSpanTree_PRIM (G, minedge);

printf ("该图生成树的边如下：\n");

PrintMinEdge (G, minedge);

printf ("\n");

return (0);

}

int LocateVex (MGraph G, char v)

{

int i;

for (i = 0; i < g.vexnum;="">

if (G.vexs[i] == v)

return (i);

return (-1);

}

void CreateUDN (MGraph &G)

{//无向网

int i, j, k, w; //w为权值

char va, vb;

printf ("请输入顶点的顶点数，边数：");

scanf ("%d%d", &G.vexnum, &G.arcnum);

printf ("请输入顶点的值：\n");

// for (i = 0; i < g.vexnum;="">

// {

// scanf ("%*c%c", &G.vexs[i]);

// }

scanf ("%s", G.vexs);

// printf ("%c", G.vexs[2]);

for (i = 0; i < g.vexnum;="">

for (j = 0; j < g.vexnum;="">

G.arcs[i][j] = INFINITY;

printf ("请输入各条边，以及权值:\n");

for (k = 0; k < g.arcnum;="">

{

scanf ("%*c%c%*c%c%*c%d", &va, &vb, &w);

i = LocateVex (G, va);

j = LocateVex (G, vb);

G.arcs[i][j] = G.arcs[j][i] = w;

}

void PrintUDN (MGraph G)

{

int i;

printf (" ");

for (i = 0; i < g.vexnum;="">

printf ("%c ", G.vexs[i]);

printf ("\n");

for (i = 0; i < g.vexnum;="">

{

printf ("%c ", G.vexs[i]);

for (int j = 0; j < g.vexnum;="">

{

if (i != j)

{

if (G.arcs[i][j] != INFINITY)

printf ("%d ", G.arcs[i][j]);

else

printf ("∞ ");

}

else

printf ("%d ", 0);

}

printf ("\n");

}

void MiniSpanTree_PRIM (MGraph G, closedge &minedge)

{

int i, j, k, z;

int temp;

int currentmin;

k = 0;

for (j = 1; j < g.vexnum;="" j++)="">

{

minedge[j-1].adjvex = k;

minedge[j-1].endvex = j;

minedge[j-1].lowcost = G.arcs[k][j];

}

for (i = 0; i < g.vexnum-1;="">

{

currentmin = minedge[i].lowcost;

k = i;

for (j = i+1; j < g.vexnum-1;="" j++)="">

{

if (minedge[j].lowcost <>

{

currentmin = minedge[j].lowcost;

k = j;

}

//第k个元素与第i个元素进行交换

temp = minedge[i].adjvex;

minedge[i].adjv

ex = minedge[k].adjvex;

minedge[k].adjvex = temp;

temp = minedge[i].endvex;

minedge[i].endvex = minedge[k].endvex;

minedge[k].endvex = temp;

temp = minedge[i].lowcost;

minedge[i].lowcost = minedge[k].lowcost;

minedge[k].lowcost = temp;

for (j = i+1; j < g.vexnum-1;="">

{

z = minedge[i].endvex; //z为找到的新顶点

k = minedge[j].endvex;

if (k != z)

{

if (G.arcs[z][k] <>

{

minedge[j].adjvex = z;

minedge[j].lowcost = G.arcs[z][k];

}

void PrintMinEdge (MGraph G, closedge minedge)

{

int i, j;

for (i = 0; i < g.vexnum-1;="">

if (minedge[i].lowcost != INFINITY)

printf ("%c->%c: %d\n", G.vexs[minedge[i].adjvex], G.vexs[minedge[i].endvex], minedge[i].lowcost);

}

范文四：树、图及其应用最小生成树

实验4 树、图及其应用

-----------最小生成树

一. 需求分析

1、利用克鲁斯卡尔算法求网的最小生成树；

2、以用户指定的结点为起点, 分别输出每种遍历下的结点访问序列； 3、输入为存在边的顶点对，以及它们之间的权值；输出为所得到的邻接矩阵以及按权排序后的边和最后得到的最小生成树；二. 概要设计设计思想：

图的存储使用数组表示法，即邻接矩阵存储，结构体包含图的邻接矩阵，当前顶点数和弧数。图的初始化使用二重循环得到顶点和表的权值，邻接矩阵的打印使用二重for 循环。然后把图各边的权值按从小到大排序；然后依次把最小边加入进来，即生成最小生成树。克鲁斯卡尔算法：假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，按照构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至只有一棵树，也即子图中含有 n-1条边为止。

1、设定图的抽象数据类型: ADT Graph{

数据对象V :V是具有相同特性的数据元素的集合, 称为点集. 数据关系R :

R={VR}

VR={(v,w)|v,w属于V,(v,w)表示v 和w 之间存在的路

径}

基本操作P:

CreatGraph(&G,V,VR)

初始条件:V是图的顶点集,VR 是图中弧的集合. 操作结果:按V 和VR 是定义构造图G. Sort(edge* ,MGraph *)

初始条件: 图G 存在，各边权值已知；操作结果:对权值进行排序； Find(int *, int )

初始条件:前者为已存在的集合，后者为集合中的元素；操作结果:查找函数，确定后者所属子集； MiniSpanTree(MGraph *)

初始条件: 图G 存在，各边权值已知；操作结果:生成最小树；

Swapn(edge *, int, int)

初始条件: 图G 存在，各边权值已知；

操作结果:交换某两个边的权值； 2 图的存储结构

typedef struct { int adj; int weight;

}AdjMatrix[MAX][MAX];

typedef struct {

AdjMatrix arc; int vexnum, arcnum; }MGraph;

typedef struct {

int begin; int end; int weight; }edge;

3 本程序包含的模块 }

1）初始化操作，结构体定义； 2）函数声明模块；

3）函数定义模块； 4）主程序模块 Main() {

调用函数生成图；

判断图是否为空；（空则从新输入）调用函数生成最小生成树；退出；三详细设计

#include #include #define M 20 #define MAX 20

typedef struct {

int begin; int end; int weight; }edge;

typedef struct {

int adj; int weight;

}AdjMatrix[MAX][MAX];

typedef struct {

AdjMatrix arc;

int vexnum, arcnum; }MGraph;

void CreatGraph(MGraph *); void sort(edge* ,MGraph *); void MiniSpanTree(MGraph *);

int Find(int *, int );

void Swapn(edge *, int, int); void CreatGraph(MGraph *G) {

int i, j,n, m;

printf("请输入边数和顶点数:");

scanf("%d %d",&G->arcnum,&G->vexnum);

for (i = 1; i <= g-="">vexnum; i++) {

for ( j = 1; j <= g-="">vexnum; j++) {

G->arc[i][j].adj = G->arc[j][i].adj = 0; } }

for ( i = 1; i <= g-="">arcnum; i++) {

printf("\n请输入有边的2个顶点"); scanf("%d %d",&n,&m);

while(n < 0="" ||="" n=""> G->vexnum || m < 0="" ||="" n=""> G->vexnum) {

printf("输入的数字不符合要求请重新输入:"); scanf("%d%d",&n,&m); }

G->arc[n][m].adj = G->arc[m][n].adj = 1; getchar();

printf("\n请输入%d与%d之间的权值:", n, m); scanf("%d",&G->arc[n][m].weight); }

printf("邻接矩阵为:\n");

for ( i = 1; i <= g-="">vexnum; i++) {

for ( j = 1; j <= g-="">vexnum; j++) {

printf("%d ",G->arc[i][j].adj); }

printf("\n"); } }

void sort(edge edges[],MGraph *G) {

int i, j;

for ( i = 1; i < g-="">arcnum; i++) {

for ( j = i + 1; j <= g-="">arcnum; j++) {

if (edges[i].weight > edges[j].weight) {

Swapn(edges, i, j); } } }

printf("权排序之后的为:\n"); for (i = 1; i < g-="">arcnum; i++) {

printf("< %d,="" %d="">> %d\n", edges[i].begin, edges[i].end, edges[i].weight); } }

void Swapn(edge *edges,int i, int j) {

int temp;

temp = edges[i].begin;

edges[i].begin = edges[j].begin; edges[j].begin = temp; temp = edges[i].end; edges[i].end = edges[j].end; edges[j].end = temp;

temp = edges[i].weight;

edges[i].weight = edges[j].weight; edges[j].weight = temp; }

void MiniSpanTree(MGraph *G) {

int i, j, n, m; int k = 1;

int parent[M];

edge edges[M];

for ( i = 1; i < g-="">vexnum; i++) {

for (j = i + 1; j <= g-="">vexnum; j++) {

if (G->arc[i][j].adj == 1) {

edges[k].begin = i; edges[k].end = j;

edges[k].weight = G->arc[i][j].weight; k++; } } }

sort(edges, G);

for (i = 1; i <= g-="">arcnum; i++) {

parent[i] = 0; }

printf("最小生成树为:\n"); for (i = 1; i <= g-="">arcnum; i++) {

n = Find(parent, edges[i].begin); m = Find(parent, edges[i].end); if (n != m) {

parent[n] = m;

printf("< %d,="" %d="">> %d\n", edges[i].begin, edges[i].end, edges[i].weight); } } }

int Find(int *parent, int f) {

while ( parent[f] > 0) {

f = parent[f]; }

return f; }

int main(void) {

MGraph *G;

G = (MGraph*)malloc(sizeof(MGraph)); if (G == NULL) {

printf("memory allcation failed,goodbye"); exit(1); }

CreatGraph(G);

MiniSpanTree(G);

system("pause"); return 0; }

四设计和调试分析

1 在定义存储图的结构体时，只需要含参数边以及权值；本程序M 预定义为20，所以输入的顶点数不能超过20；由于各边含有权值，实际上已经是网了；

2 由于在图的初始化以及邻接矩阵的打印时均使用了循环的嵌套，故其时间复杂度为O （n 2 ）的；其他操作的时间复杂度均为O （1）。 3 通过输入图的全部边输入一个图，每个边为一个数对。同时生成树的边是有向边，所以端点顺序不能交换；

五、测试用例及结果

范文五：[汇总]无向图的最小生成树

实验四无向图的最小生成树

题目:求一个无向图的最小生成树班级: 姓名: 学号: 完成日期:

一、需求分析

在本实验中，由于本人编程能力问题，没有使用结构体、指针等较为复杂的东西，只

是力图实现prim算法，关系的存储亦是直接使用关系矩阵存储，没有输入操作。

4、测试数据

共七个点，它们之间的权值如下: mx[1][2]=50;

mx[1][3]=60;

mx[2][4]=65;

mx[2][5]=40;

mx[3][4]=52;

mx[3][7]=45;

mx[4][5]=50;

mx[5][6]=70;

mx[4][6]=30;

mx[4][7]=42;

之间没有权值的两个点令其权值为1000。二、概要设计

为实现上述程序功能，用关系矩阵存储节点间权值。 2、本程序包含两个模块:

(1)主程序模块:

int main(){

定义变量;

接受命令;

处理命令;

退出(return 0);

}

(2)prime算法的实现，产生最小生成树。三、详细设计

1，预编译部分

#include

using namespace std;

#define MAXVEX 30 //定义最大点的个数 #define MAXCOST 1000 //定义最大权值，用来描述两点间没有关系

2，主函数

int main()

{

int n=7,i=0,j=0,mx[MAXVEX][MAXVEX];//定义节点数、关系矩阵、循环变量

for (i=0;i<=n;i++)>

{

for (j=0;j<=n;j++)>

{

mx[i][j]=MAXCOST; //初始化关系矩阵，使每个值都为最大权值

}

mx[1][2]=50; //描述节点间关系

mx[1][3]=60;

mx[2][4]=65;

mx[2][5]=40;

mx[3][4]=52;

mx[3][7]=45;

mx[4][5]=50;

mx[5][6]=70;

mx[4][6]=30;

mx[4][7]=42;

cout<>

prim(mx,n);

return 0;

}

3，prime算法

void prim(int c[MAXVEX][MAXVEX], int n) {

int i,j,k,min,lowcost[MAXVEX],closest[MAXVEX];

for (i=2;i<=n;i++)>

{

lowcost[i]=c[1][i]; //把与第一个节点关联的节点之间的权值存到数

组内

closest[i]=1; //标记未处理节点

}

closest[1]=0;

for (i=2;i<=n;i++)>

{

min=MAXCOST;

j=1;

k=i;

while (j<=n) 寻找最小权值节点="">

{

if (lowcost[j]

{

min=lowcost[j];

k=j;

}

j++;

}

cout<><><><><>

closest[k]=0;

for (j=2;j<=n;j++) 节点j通过k连到图中="">

{

if (closest[j]!=0 && c[k][j]

{

lowcost[j]=c[k][j];

closest[j]=k;

}

四、调试分析

本实验语法和初始阶段的构思都比较难，所以我简化了一些非必要的部分，

故而在完成本实验的过程中遇到的调试问题不多。五、运行结果

六、实验环境

(1)Windows XP系统下

(2)编程环境:VC6.0++ ，TC2.0

转载请注明出处范文大全网 » 图的最小生成树

范文一：图的最小生成树

范文二：图的最小生成树

范文三：图的最小生成树

范文四：树、图及其应用 最小生成树

范文五：[汇总]无向图的最小生成树

范文四：树、图及其应用最小生成树