www.gusucode.com > 里面有最大流，最小费用最大流和着色问题的matlab程序和lingo程序 > 里面有最大流，最小费用最大流和着色问题的matlab程序和lingo程序/最大流，最小费用流，着色程序/WelshPowell.m

    function [paint,totalcolor] = WelshPowell( E )
%采用最大度数优先的Welsh_Powell算法解决着色问题，E为邻接矩阵（取值0,1),E（i,i)=0
%paint为2*n矩阵，paint(1,:)为顶点集合，paint(2,:)为对应点所着的颜色集合；totalcolor为使用的颜色总数
% 李阳   2010年4月22日
% E=[0 1 1 1 0 1 1
%    1 0 1 0 1 1 0
%    1 1 0 1 1 0 0 
%    1 0 1 0 1 0 1
%    0 1 1 1 0 0 0 
%    1 1 0 0 0 0 0 
%    1 0 0 1 0 0 0];
n=size(E,2);   %求E的顶点个数
degree=sum(E);  %按列求各顶点的度
[~,q]=sort(degree,'descend');  %q为各顶点按度排列后的索引
bepaint=repmat(1:n,n,1);     %初始化着色矩阵，每点赋颜色集1:n
for j=1:n        %最大度数优先求着色方案，每点着最小颜色编号所代表的颜色
    pjci=min(bepaint(q(j),:));  %q(j)着pjci色
    for k=j+1:n
        if E(q(j),q(k))==1     %若相邻，则不能着相同颜色
            index= find(bepaint(q(k),:)==pjci);
            bepaint(q(k),index) = bepaint(q(k),index) + inf;
        end
    end
end
paint=[1:n ; (min(bepaint,[],2))'];
totalcolor=length(unique(paint(2,:)));  %求所用颜色总数