连通图的中心和加权中心的算法及其matlab程序详解

#################本文为学习《图论算法及其MATLAB实现》的学习笔记#################

连通图中心是选址问题的重要部分

所有顶点中与离它自身最远顶点的距离取得极小值的顶点称为该图的中心。

若图的每一个顶点均赋有各自的权值,在考虑到各顶点权值的条件下,选出的中心称为该图的加权中心。

算法用途

连通图的中心和加权中心的求法

算法思想

程序参数说明

W: 图的权值矩阵 
A: 顶点的权重
d0: 图的中心
d: 加权中心

算法程序详解

%连通图的中心和加权中心算法
function [ d0,d ] = centgraf( W,A )
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% 输入：     W: 图的权值矩阵 
%%%%%%%%%            A: 顶点的权重
%%%%%%%%% 输出：    d0: 图的中心
%%%%%%%%%            d: 加权中心
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 若只求图中心，用 d0 = centgraf(W)

%%%%%% 计算最短距离矩阵 %%%%%%
n = length(W);  % 计算顶点数
U = W;
m = 1;
while m <= n   
    for i = 1:n
        for j = 1:n
            if U(i,j) > U(i,m) + U(m,j)
                U(i,j) = U(i,m) + U(m,j);     
            end
        end
    end
    m = m+1;
end

d1 = max(U,[],2);     % 计算各行最大值
d0t = min(d1);        % 在最大值中选取最小者
d0 = find(d1 == min(d1));  % 最小者对应的顶点即为图的中心

dt = zeros(1,n);
for i = 1:n
    dt(i) = dot(U(i,:),A);    % 计算矩阵di1
end
d = find(dt == min(dt));      % 选取最小者对应的顶点即为图的加权中心
ddt = min(dt);