数据结构普里姆算法 求最小生成树算法数据结构问题

数据结构问题.怎么用普里姆算法求最小生成树算法数据结构?能详细讲解下并举下例子吗?
该算法以贪心为基础,每次保证了添加生成的树一定是最小生成树算法数据结构

参考书籍:数据结构(C语言版)嚴蔚敏吴伟民编著清华大学出版社

本文中的代码可从这里下载:

    对于带权的连通图(连通网)G其生成树也是带权的,将权值之和最小的生成樹称为最小生成树算法数据结构

    假设 N =(V,{E})是一个连通网,U是顶点集 V 的一个非空子集若(u,v)是一条具有最小权值(代价)的边,其中 u ∈Uv∈V-U,则必存在一棵包含边(u,v)的最小生成树算法数据结构

    (2)从 V 中任取一个顶点(假定为 V1),将此顶点并入 U中此时最小生成树算法数据結构顶点集 U={V1};
    (3)从那些其中一个端点已在 U 中,另一端点仍在 U 外的所有边中找一条最短(即权值最小)的边,设该边为(Vi,Vj)其中 Vi∈U,Vj∈V-U并把該边和顶点 Vj分别并入 T 的边集 TE 和顶点集 U;
    (4)如此进行下去,每次往生成树里并入一个顶点和一条边直到 n-1 次后,把所有 n 个顶点都并入生成树 T 的頂点集 U 中此时 U=V,TE中包含有(n-1)条边;这样T 就是最后得到的最小生成树算法数据结构。

    算法时间复杂度O(n^2)与边无关,适合求解边稠密的網的最小生成树算法数据结构

DG(有向图)或者DN(有向网):邻接矩阵、邻接表(逆邻接表--为求入度)、十字链表
UDG(无向图)或者UDN(无向網):邻接矩阵、邻接表、邻接多重表
//1.数组表示法(邻接矩阵):将以有向网为例
typedef int VRType;//顶点关系类型,对于无权图或网用0或1表示相邻否;对於带权图或网,则为相应权值
 

3.2邻接矩阵构造无向网G

 
//若图G中存在顶点v则返回v在图中的位置信息,否则返回其他信息
//采用邻接矩阵表示法构慥无向网G
 
 VRType w;//对于无权图或网用0或1表示相邻否;对于带权图或网,则为相应权值 
 printf("\n每行输入一条弧依附的顶点(先弧尾后弧头)和权值(如:v1 v2 3):\n");
 //又因为是无向网所以邻接矩阵相对于对角线对称,所以还得对另外半边三角阵赋值!!!!!!!!!!重要
 
 

//用prim算法从第u个顶点出发構造网G的最小生成树算法数据结构T输出T的各个边,O(n^2)
 
 

 printf("请输入构造最小生成树算法数据结构的出发点:");
 


参考资料

 

随机推荐