顶点染色算法的matlab程序详解

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

• 算法用途

给出简单图的染色数尽可能少的顶点染色方案

• 算法思想

从顶点度数最小的顶点开始染色，找到不与其相邻的顶点并选择其中一个顶点进行染色，再找与这两个顶点都不相邻的顶点集合，并对其中一个顶点染色，直到找不到为止。再找未染色的度数小的顶点，重复进行以上过程，直到所有顶点都已染色为止，程序结束。

• 算法程序

function [k,C] = colorcodf(W)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 顶点染色算法 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% 输入：     W: 邻接矩阵； 
%%%%%%%%% 输出：     k: 最终得到的染色数
%%%%%%%%%            C: 顶点染色方案
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

G = W;
G;
n = size(G,1);           %得出 G 的行数
k = 1;
C = zeros(1,n);          % C 为1行n列的全零数组
Z = [1:n];               % 建立一个1到n的数组
while sum(find(C == 0))
    %%%%%%%%%%%% 找到度数最小的顶点,并将其染成 1 色 %%%%%%%%%%%%
    tcol = find(C == 0);            % tcol为 C 中元素为0的索引值
    m = sum(G(tcol,:),2);           % m 为 G的 tcol 行元素的和,列矩阵
    minm = min(m);                  % minm 为 m 中每列元素的最小值
    k1 = min(find(m == minm));      % k1 为 m 中最小值的索引值的最小值
    c = G(tcol(k1),:);              % c 为 G 的第 tcol(k1) 行
    c(1,tcol(k1)) = 1;              % 使 c 的第 (1,tcol(k1)) 元素为1
    C(tcol(k1)) = k;                % 使数组 C 中的第 tcol(k1) 个元素为k
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
    Sn = find(c ~= 0);              % Sn 为 c 中元素不为0的索引值，即找到与最小度数顶点相邻的顶点
    flag = 1;
    while flag
        tc = setdiff(Z,Sn);         % tc 为在 Z 中而不在 Sn 中的元素，即找到不与最小度数顶点相邻的顶点
        if isempty(tc)              % 若 tc 为空集，即未找到
            flag = 0;
            k = k+1;                % 将待染颜色调整为 k+1 色（目前为 k 色）
        else
            c = G(tc(1),:);         % c 为 G 的第 tc(1) 行
            c(1,tc(1)) = 1;         % 使 c 的第 (1,tc(1)) 元素为1
            C(tc(1)) = k;           % 使数组 C 中的第 tc(1) 个元素为k，即将与最小度数顶点不相邻的顶点染成 1 色
            Sn1 = find(c ~= 0);     % Sn1 为 c 中元素不为0的索引值
            Sn = union(Sn,Sn1);     % Sn 为 Sn 与 Sn1 的并集
        end
    end
    trow = find(C == k-1);          % trow 为 C 中元素值为k-1的索引值，即为已染色的顶点
    G(:,trow) = 1;                  % 使 G 的第 trow 列元素值为1
end
k = k-1;
C;