1.算法描述
一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。 最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。图的所有生成树中具有边上的权值之和最小的树称为图的最小生成树 (Minimum Spanning Tree，MST) ；一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有构成一棵树的 n − 1 n-1n−1 条边；对于一个带权 (假定每条边上的权均为大于零的数) 连通无向图 G GG 中的不同生成树，其每棵树的所有边上的权值之和也可能不同；简单来说，对于一个有 n nn 个点的图，边一定是大于等于 n − 1 n-1n−1 条的，最小生成树就是在这些边中选择 n − 1 n-1n−1 条出来连接所有的 n nn 个点，且这n − 1 n-1n−1 条边的边权之和是所有方案中最小的；
对于一个带权连通无向图G=(V,E)，生成树不同，每棵树的权（树中所有边上的权值和）也不同，设R为G的所有生成树的集合，若T为R中权值和最小的生成树，则T称为G的最小生成树（Minimum-Spanning-Tree，MST）
注：
1、最小生成树可能有多个，但边的权值之和总是唯一且最小的
2、最小生成树的边数=定点数-1，砍掉一条则不连通，增加一条则会出现回路
3、若一个连通图本身就是一颗树，则其最小生成树就是它本身
4、只有连通图才有生成树，非连通图只有生成森林
无线传感器网络(Wireless Sensor Networks, WSN)是一种整合了传感器，网络以及微机电的新型网络技术。WSN具有低功耗、自组织、低成本以及部署方便等优势。因此，WSN被广泛应用在各种通信场景中，如环境监测、火灾预警以及军事防化领域等[]。为了提升WSN的通信性能，降低WSN的能耗，构建WSN的最小连通支配集(Minimum Connected Dominating Set, MCDS)具有十分重要的意义。
在WSN对应的图定义为G=(V, E, R)，V表示的是WSN中所有的节点集合，E表示边的集合，R表示的是WSN节点的可通信半径。假设图G为全连通图，图中所有节点的连接为双向连接。其中，图G的支配集(Dominating Set, DS)可以定义为如下表达式：
公式1中，如果D中至少存在一个节点u与之相邻，此时D为图G的一个支配集。进一步，连通支配集(Connected Dominating Set, CDS)可以定义为如下表达式：
公式2的含义为当V中任意一个节点属于D或者至少与D中的某个节点连接。其中D表示支配集DS，。那么当DS为连通的，此时DS即为CDS。由于CDS的集合并不是唯一的，其中规模最小的即被称之为MCDS。
2.仿真效果预览
matlab2022a仿真结果如下：
3.MATLAB核心程序
Radius = 25;
Node_Nums = [40:10:150];
for ii = 1:length(Node_Nums)
ii
for jj = 1:50
rng(jj);
Node_Num = Node_Nums(ii);
for i=1:Node_Num
Posxy(i,1)=150*rand(1,1);
Posxy(i,2)=100*rand(1,1);
end
%网络图参数提取
%度
%将网络图转换为矩阵的变量
Connect_matrix = zeros(Node_Num,Node_Num);
W = zeros(Node_Num,Node_Num);
D = [];%度数
for i=1:Node_Num
num = 0;
for j=1:Node_Num
if i~=j
dist = (Posxy(i,1)-Posxy(j,1))^2+(Posxy(i,2)-Posxy(j,2))^2;
if dist < Radius^2
num = num+1;
Connect_matrix(i,j) = 1;
end
end
end
d(i) = num;
D = [D,d(i)];%计算度数
end
x = Posxy(:,1);
y = Posxy(:,2);
%%
%下面是对比算法，直接通过最小生成树来产生MCDS，放这里，我们作为对比使用
[X_,Y_,M,MD,T]=func_tree(Connect_matrix,Node_Num,W,x,y,D);
Sizes = length(M);
Ti(jj)= Sizes/Node_Num;
end
Ti1(ii)= mean(Ti);
end
p = polyfit(Node_Nums,Ti1,4);
Ti2 = polyval(p,Node_Nums);