Matlab全连通图迭代简化优化：寻求高效算法及代码改进方案

我在Matlab中处理若干全连通图，需要迭代移除权值较小的边：如果移除某条边会破坏图的连通性，就保留该边并尝试下一条。现有一段实现功能的代码，但运行速度极慢且较为原始，求改进方法或现成算法。

原代码如下：

close all
clear all
clc
rng(2023)
%% generate fake data
X = rand(100,10);
R = corr(X);
R = (R+R')./2; % remove numerical problems. Make matrix symmetric
G = graph(R.^2,'omitselfloops');
%% simplify the graph
G.Edges.isChecked(:)=0;
G.Edges.edgeID=[1:size(G.Edges,1)]';
while true
    
    % find minimal edge, which is not checked already
    notCheckedEdges = G.Edges(G.Edges.isChecked==0,:);
    [~,minID] = min(notCheckedEdges.Weight);
    minID = notCheckedEdges.edgeID(minID); % substitute to original ID
    % remove minimal edges
    G1 = rmedge(G,find(G.Edges.edgeID==minID));
    % check if graph is still connected
    isConnected = numel(unique(conncomp(G1)))==1;
    if isConnected
        G = G1; % remove edge
    else
        G.Edges.isChecked(G.Edges.edgeID==minID)=1; % mark edges as checked and keep it for next iterations
    end
    if all(G.Edges.isChecked==1), break; end % terminate loop when all edges were checked
end

一、现成算法：最大生成树（Maximum Spanning Tree, MST） #

你的需求本质是保留维持图连通性的最大权值边集合，这完全对应最大生成树的定义：最大生成树包含原图所有顶点，总权值最大，且是无环连通的树结构。所有不在生成树里的边，都是可以安全移除的（移除后不会破坏连通性）。

直接用Matlab自带的maxspantree函数就能一步完成，效率远超手动迭代：

close all
clear all
clc
rng(2023)
%% 生成测试数据
X = rand(100,10);
R = corr(X);
R = (R+R')./2; % 确保对称，消除数值误差
G = graph(R.^2,'omitselfloops');

%% 直接生成最大生成树，得到最终的连通图
G_mst = maxspantree(G);

该方法时间复杂度为O(E log V)（E为边数，V为顶点数），相比原代码的O(E²)，大图下速度提升极为明显，且结果和手动迭代完全一致。

二、手动迭代代码优化方案（特殊场景下使用） #

如果因为特殊需求不能直接用MST，可从以下几点优化原代码：

• 预排序边权，避免重复查找最小值
  提前将所有边按权值从小到大排序，按顺序处理即可，无需每次循环重复查找最小值：

  % 预排序边，按权值升序排列
  [~, sortedIdx] = sort(G.Edges.Weight);
  sortedEdgeIDs = G.Edges.edgeID(sortedIdx);
  
  for i = 1:length(sortedEdgeIDs)
      currentEdgeID = sortedEdgeIDs(i);
      % 尝试移除当前边
      G1 = rmedge(G, find(G.Edges.edgeID == currentEdgeID));
      % 检查连通性
      if numel(unique(conncomp(G1))) == 1
          G = G1;
      end
  end
  

• 优化连通性检查
  原代码用unique(conncomp(G1))判断连通性，可改用更高效的isgraphconnected函数（Matlab R2021b及以后版本支持）：

  isConnected = isgraphconnected(G1);
  

• 减少图对象的频繁创建
  原代码每次移除边都创建新的G1，可直接在原G对象上操作（移除成功就保留，失败则跳过），减少对象创建开销。

内容的提问来源于stack exchange，提问作者zlon