最小生成树Kruskal算法

资 源 简 介

图论中最小生成树Kruskal算法 及画图程序 M-函数格式 [Wt，Pp]=mintreek(n，W)：n为图顶点数，W为图的带权邻接矩阵，不构成边的两顶点之间的权用inf表示。显示最小生成树的边及顶点， Wt为最小生成树的权，Pp(:，1:2)为最小生成树边的两顶点，Pp(:，3)为最小生成树的边权，Pp(:，4)为最小生成树边的序号 附图，红色连线为最小生成树的图 例如 n=6 w=inf*ones(6) w(1，[2，3，4])=[6，1，5] w(2，[3，5])=[5，3] w(3，[4，

详 情 说 明

在图论中，最小生成树Kruskal算法是一种有效的算法。这种算法利用了图的特性，并通过M-函数格式的画图程序进行实现。M-函数的格式为[Wt，Pp]=mintreek(n，W)，其中n表示图的顶点数，W表示图的带权邻接矩阵。如果两个顶点之间没有边相连，则它们之间的权重用inf表示。利用这个函数，图的最小生成树的边和顶点可以被显示出来。Wt表示最小生成树的权重，而Pp(:，1:2)表示最小生成树的边的两个顶点，Pp(:，3)表示最小生成树的边权，而Pp(:，4)则表示最小生成树边的序号。在附图中，红色的连线代表了最小生成树的图。例如，当n为6，w为inf*ones(6)时，w(1，[2，3，4])=[6，1，5]，w(2，[3，5])=[5，3]，w(3，[4，5，6])=[5，6，4]，w(4，6)=2，w(5，6)=6。此时，可以使用[a，b]=mintreek(n，w)来得到最小生成树。