matlab最小树算法

最小生成树简介最小生成树（Minimum Spanning Tree）是图论中的一个重要概念。

它是一种用于连接所有节点的树，同时使得树中边的权值之和最小。

最小生成树在许多领域中都有广泛的应用，例如网络设计、电力传输、交通规划等。

算法Kruskal算法Kruskal算法是一种常用的解决最小生成树问题的算法。

它的基本思想是通过不断选择图中权值最小的边，并且保证这些边不会形成环，直到选择了足够多的边为止。

具体步骤如下：1.初始化一个空的最小生成树集合。

2.将图中所有边按照权值从小到大排序。

3.遍历排序后的边，如果当前边不会导致最小生成树形成环，则将该边添加到最小生成树集合中。

4.最终得到的最小生成树集合即为所求。

Prim算法Prim算法是另一种解决最小生成树问题的经典算法。

它的基本思想是从一个起始节点开始，逐步扩展最小生成树，直到覆盖所有节点。

具体步骤如下：1.初始化一个空的最小生成树集合。

2.随机选择一个起始节点，并将其加入到最小生成树集合中。

3.在最小生成树集合和图的剩余节点之间找到连接两部分的最小权值边，将该边和连接的节点加入到最小生成树集合中。

4.重复步骤3，直到最小生成树覆盖了所有节点。

应用场景网络设计最小生成树在网络设计中有着广泛应用。

例如，在计算机网络中，我们希望通过最小的成本将所有节点连接起来。

最小生成树提供了一种方法来实现这一目标，通过构建一个权值最小的树形网络，可以节省物理资源，提高网络传输效率。

电力传输在电力传输领域，最小生成树被用于设计最优的电力传输网络。

通过选择最小的成本边连接所有电力站点，可以减少电力传输的总成本，并优化电力的分布。

交通规划最小生成树在交通规划中也有着广泛的应用。

例如，在城市道路规划中，我们希望通过最小的道路建设成本将所有地区连接起来。

最小生成树算法可以帮助我们找到连接所有区域的最短路径，从而实现高效的交通规划。

MATLAB代码实现function [T] = minSpanningTree(G)% 输入参数:% G: 输入图的邻接矩阵表示% 输出参数:% T: 最小生成树的邻接矩阵表示n = size(G, 1); % 节点个数visited = zeros(1, n); % 记录节点是否被访问过T = zeros(n); % 初始化最小生成树的邻接矩阵visited(1) = 1; % 从第一个节点开始构建最小生成树while sum(visited) < n % 当所有节点都被访问过时停止minEdge = inf; % 最小权值边的权值minIndex = 0; % 最小权值边的终点for i = 1:nif visited(i) == 1for j = 1:nif visited(j) == 0 && G(i, j) < minEdgeminEdge = G(i, j);minIndex = j;endendendendvisited(minIndex) = 1; % 将新节点标记为已访问T(minIndex, :) = G(minIndex, :); % 将该边添加到最小生成树中T(:, minIndex) = G(:, minIndex);endend总结最小生成树是一种重要的图论概念，常用于解决连接所有节点的问题。

kruskal算法及代码---含伪代码、c代码、matlab、pascal等代码K r u s k a l算法每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。

注意到所选取的边若产生环路则不可能形成一棵生成树。

K r u s k a l算法分e 步，其中e 是网络中边的数目。

按耗费递增的顺序来考虑这e 条边，每次考虑一条边。

当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。

目录Kruskal算法1.算法定义举例描述Kruskal算法的代码实现1.伪代码C代码实现matlab代码实现pascal代码实现Kruskal算法1.算法定义举例描述Kruskal算法的代码实现1.伪代码C代码实现matlab代码实现pascal代码实现算法定义克鲁斯卡尔算法假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。

之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。

依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。

举例描述克鲁斯卡尔算法(Kruskal's algorithm)是两个经典的最小生成树算法的较为简单理解的一个。

这里面充分体现了贪心算法的精髓。

大致的流程可以用一个图来表示。

这里的图的选择借用了Wikipedia上的那个。

非常清晰且直观。

首先第一步，我们有一张图，有若干点和边如下图所示：第一步我们要做的事情就是将所有的边的长度排序，用排序的结果作为我们选择边的依据。

matlabKruskal最小生成树算法clear all;clc;a = rand(100,100);%随机生成100*100的方阵graph_adjacent = (a+a')/2;len = length(graph_adjacent);%计算图中的顶点数temp = graph_adjacent;%将原图内容拷贝到temp中，以防对原图做改动superedge = zeros(len-1,2);%用于保存生成最小生成树的边i = 1;%指向superedge的下标for j = 1:lentag(j) = j;%关联标志初始化，将每个顶点的关联标志设为其本身end;%以下的循环完成kruskal算法ticwhile(superedge(len-1,1)==0)[Y,I] = sort(temp);%将temp的每列按从小到大排序，数组Y保存temp 排序后的结果，I中保存相应结果对应的在temp中的下标cost_min = min(Y(1,:));%找出权值最小的边index = find(Y(1,:)==cost_min);%找出权值最小的边对应的顶点index = index(1);%一条边对应两个节点，且不同的边的权值可能一样，这里为了方便处理人为规定了顺序，取标号最小的顶点进行处理anotherpoint = I(1,index);%找到该边对应的另一个顶点%将该边对应的权值修改为最大，防止该边在下次循环中再次被选为最优边temp(index,anotherpoint)=100;temp(anotherpoint,index)=100;if(tag(anotherpoint)~=tag(index))%当两个点不属于一个连通集时，这两个点之间的边为最小生成树的边superedge(i,:)=[index,anotherpoint];%将其加入最小生成树的边集中i=i+1;%下标加1%下面的语句的作用是将两个连通分支变成一个连通分支，即tag 值一样for j=1:len %以index的tag值为标准if((tag(j)==tag(anotherpoint))&&(j~=anotherpoint))%遍搜tag数组，先将和anotherpoint tag值一样的点的tag值变为index 的tag值tag(j)=tag(index);endendtag(anotherpoint)=tag(index);%将anotherpoint的tag值变为index的tag值endendtoc%s=0;for ii=1:len-1k=sprintf('最小生成树第%d条边：（%d,%d），权值为%d',ii,superedge(ii,1),superedge(ii,2),graph_adjacent(superedg e(ii,1),superedge(ii,2)));%格式化字符串disp(k);%显示disp(' ');%空一行%s=s+graph_adjacent(superedge(ii,1),superedge(ii,2)); %求最小生成树的代价end%显示最小生成树的代价%disp('最小生成树的总代价为：') %disp(s);。

Kruskal算法寻找最小树的matlab程序function tree=kruskal(d) %矩阵d为无向图的权矩阵，且是对称矩阵N=size(d,1);k=0; %记录图中边的条数I=max(max(d)); %I作为无穷大edge=zeros(N*(N-1)/2,3);%用于存储图中所有的边，边的条数最多为n*(n-1)/2for i=1:N-1 %因为权矩阵是对称阵，所以只用上三角矩阵。

for j=i+1:Nif d(i,j)<Ik=k+1;edge(k,1)=i;edge(k,2)=j;edge(k,3)=d(i,j);endendendedge=edge(1:k,:); %删除多余的行。

o_edge=edge; %用于存储排序后的边及边的端点。

for i=1:k-1 %用选择排序法进行升序排序for j=i+1:kif o_edge(i,3)>o_edge(j,3)temp=o_edge(i,:);o_edge(i,:)=o_edge(j,:);o_edge(j,:)=temp;endendendtree=zeros(N-1,3); %用于存放最小树中的边及边的端点，最小树中的边数为节点数减1 tree(1:2,:)=o_edge(1:2,:); %两条边一定不能构成圈，所以前面最小的两条边一定在最小树中。

line=3;for i=3:kif line==N %如果line=N说明tree矩阵已填满，最小树已经找到，跳出循环break;elseif line<Nif isempty(find(tree(:,1:2)==o_edge(i,1), 1))||isempty(find(tree(:,1:2)==o_edge(i,2), 1))%判断tree中已经确定的的所有边中的节点是否和新增加的边的两个端点都重复，若新边的两个端点不都重复，则为真%直接说明新边符合条件，加入tree中。

shortestpathtree matlab 函数矩阵中的所有节点之间都有一些路径连接着。

某些路径可能是直接的，而有些可能需要经过其他节点。

寻找从一个节点到另一个节点的最短路径是图论中一个经典的问题。

在 MATLAB 中，可以使用 shortestpathtree 函数来解决这个问题。

首先，让我们了解一下最短路径树（Shortest Path Tree）是什么。

最短路径树是一个有向图，它以某个源节点为根节点，并将所有其他节点连接到根节点的最短路径。

最短路径树通常用于网络中的路由选择和通信网络中的拓扑控制。

在 MATLAB 中，你可以使用 shortestpathtree 函数来计算具有有向边的有向图的最短路径树。

这个函数采用一个邻接矩阵作为输入，并返回一个有向图的最短路径树。

邻接矩阵是一个 N×N 的矩阵，其中 N 是图中节点的数量。

邻接矩阵的第 i 行第 j 列的元素表示从节点 i 到节点 j 是否有一条边。

如果有边连接，则该元素的值为非零，否则为零。

在有向图中，边是有方向的，所以邻接矩阵是对称的。

为了使用 shortestpathtree 函数，我们首先需要创建一个邻接矩阵。

我们可以使用 MATLAB 中的矩阵操作来实现这一点。

例如，我们可以使用 zeros 函数创建一个全零矩阵，然后使用索引操作将适当的元素设置为非零值，从而表示边的存在。

例如，假设我们有一个图，其中有四个节点，从节点 1 到节点 3 有一条权重为2 的边，从节点 1 到节点 4 有一条权重为 5 的边，从节点 2 到节点 3 有一条权重为 1 的边，从节点 2 到节点 4 有一条权重为 3 的边。

我们可以通过以下方式创建邻接矩阵：matlabadjacency_matrix = zeros(4);adjacency_matrix(1, 3) = 2;adjacency_matrix(1, 4) = 5;adjacency_matrix(2, 3) = 1;adjacency_matrix(2, 4) = 3;现在我们已经创建了邻接矩阵，我们可以使用 shortestpathtree 函数来计算最短路径树。

matlab 普里姆算法普里姆算法是一种最小生成树算法，用于求解给定图的最小生成树。

该算法基于贪心策略，每次选择当前已选中的点集到未选中的顶点集中距离最近的一条边，将该边所连接的点加入到已选中的点集中。

在实现普里姆算法时，我们需要使用一个优先队列用于存储当前已选中的点集到未选中的顶点集中的边，以及每个顶点到已选中的点集中最小距离。

在每次选取最小距离的边时，我们将该边所连接的点加入到已选中的点集中，并将该点与未选中的点集中的所有点之间的距离加入到优先队列中，同时更新已选中的点集到未选中的顶点集中的最小距离。

该过程重复进行，直到所有的顶点都已经被加入到已选中点集中，最终得到的图就是原图的最小生成树。

下面是使用matlab实现普里姆算法的示例代码：function MST = prim_algorithm(graph)% graph为邻接矩阵，MST为最小生成树的邻接矩阵表示n = size(graph, 1); % 获取图中节点数key = Inf(1,n); % 存储每个顶点与已选中点集的最小距离mst = zeros(n, n); % 存储最小生成树的邻接矩阵表示visited = false(1,n); % 存储每个顶点是否已加入到已选中点集中pq = PriorityQueue(n); % 创建优先队列start = 1; % 从任意一个顶点开始寻找最小生成树key(start) = 0; % 起始点距离已选中点集的最小距离为0pq.insert(start, 0); % 将起始点加入到优先队列中while ~pq.isempty() % 当优先队列非空时进行迭代[u, cost] = pq.deleteMin(); % 选取距离已选中点集最近的边visited(u) = true; % 将选中的顶点加入到已选中点集中if u ~= start % 将当前边加入到最小生成树的邻接矩阵中mst(parent(u), u) = cost;mst(u, parent(u)) = cost;endfor v = 1:n % 更新与已选点集中每个顶点的最小距离if ~visited(v) && graph(u,v) < key(v)parent(v) = u;key(v) = graph(u,v);if pq.contains(v)pq.updatePriority(v, key(v));elsepq.insert(v, key(v));endendendendMST = mst;end该代码中借助matlab的优先队列类PriorityQueue实现了优先队列的功能，其中包括了队列插入、队列删除、队列是否为空、队列中是否包含某元素以及队列中某元素优先级的更新等方法。

最小生成树matlab代码在Matlab中，最小生成树可以通过Kruskal算法和Prim算法来实现。

本文将分别介绍两种算法的代码实现，并对其进行详细解析。

Kruskal算法Kruskal算法是基于贪心算法的最小生成树算法。

其基本思想是将边按照权值从小到大进行排序，然后逐个加入到树中，直到树连通为止。

如果加入一条边使得形成环，则不加入该边。

定义一个函数Kruskal(weight,n)来实现Kruskal算法。

参数weight是一个n*n的矩阵，表示图的邻接矩阵；n表示图中节点的个数。

该函数的返回值为最小生成树的边集。

function edges=Kruskal(weight,n)%初始化[rows,cols,vals]=find(weight);edge_num=length(rows);%边数edges=zeros(n-1,2);%初始化，存放最小生成树的边%边按照权重从小到大排序[~,idx]=sort(vals);rows=rows(idx);cols=cols(idx);%初始化并查集par=1:n;rank=zeros(1,n);%依次加入边n_edge=0;%表示已加入的边数for i=1:edge_num%如果两个节点已经在同一连通块中，则不能加入当前边if FindPar(par,rows(i))==FindPar(par,cols(i))continue;end%将当前边加入到最小生成树中n_edge=n_edge+1;edges(n_edge,:)=[rows(i),cols(i)];%将两个节点合并Union(par,rank,rows(i),cols(i));%如果当前已经加入足够的边，则退出循环if n_edge==n-1break;endendFindPar函数和Union函数是实现并查集的两个函数，用于判断是否形成环以及将两个节点合并。

具体代码如下：%查找节点的祖先function par=FindPar(par,idx)if par(idx)==idxpar=idx;elsepar=FindPar(par,par(idx));end%将两个节点合并function Union(par,rank,x,y)x_par=FindPar(par,x);y_par=FindPar(par,y);if rank(x_par)>rank(y_par)par(y_par)=x_par;elsepar(x_par)=y_par;if rank(x_par)==rank(y_par)rank(y_par)=rank(y_par)+1;endendPrim算法Prim算法也是一种贪心算法，基本思想是从任意一个点开始，找到与该点相邻的最短边，然后将这个边连接的点加入到集合中，继续寻找与该集合相邻的最短边。

数学建模——Matlab中求解最小生成树关键词：Matlab、最小生成树、破圈法、避圈法、运筹学要求：选择一道编程题自己独立完成，必须自己编写源代码，不能从网上下载。

先编写算法的通用程序，然后以例子运行，论文内容包括程序代码、程序说明、例子运行结果，最终程序文件连同论文一起发至e-mail，便于老师运行程序是否正确。

编程使用C或MATLAB。

选择题目：编写实现生成树、最小生成树的程序（包括避圈法、破圈法）。

题目分析：本题要求编写实现生成树、最小生成树的程序，首先来了解一下关于关于生成树的概念：1、树的概念：树是无向图的特殊情况，即对于一个N个节点的无向图，其中只有N-1条边，且图中任意两点间有且只有一条路径，即图中不存在环，这样的图称为树。

2、生成树的概念：对于一个无向连通图G=(V,E)，其中V代表顶点，E代表边，对它做一次遍历，每个节点经过一次，那么图中的N个节点再加上遍历过程中经过的N-1条边所构成的子图就是图G的一个生成树。

3、最小生成树的概念：对于一个无向连通图G=(V,E),给它的每条边（u,v）赋一个权值w(u,v)。

若图G 的生成树不止一个，那么其中包含的N-1条边的权值之和的最小的生成树就是图G的最小生成树。

4、关于运筹学中最小生成树有2种不错的算法，即避圈法和破圈法，下面来看一下求解最小生成树的算法：先看一下图示法表示的最小生成树：<1>避圈法求解上面无向带权连通图的基本步骤是：每步从未选的边中选取边e，使它与已选边不构成圈，且e是未选边中的最小权边，直到选够n-1条边为止。

<2>破圈法基本思想如下:(1) 每次从图中选取任意一个圈, 然后去掉该圈中权值最大的边(如果存在多条相同权值的最大边，可以任意选择一条去掉即可) 使之不构成圈.(2) 重复上述过程. 直到图中不再含圈且所有顶点均包含在图中为止, 就构成最小生成树.它的算法图解如下：5、我们在用matlab程序求解最小生成树的时候需要用到无向图的邻接矩阵，首先来了解一下邻接矩阵的概念。