C#,图论与图算法,图着色问题(Graph Coloring)的威尔士-鲍威尔(Welch Powell Algorithm)算法与源代码
2023-09-11 14:15:48 时间
Welsh, D.J.A. and Powell, M.B. (1967) An Upper Bound for the Chromatic Number of a Graph and Its Application to Timetabling Problems. 《The Computer Journal》, 10, 85-86.
《The Computer Journal》
图着色算法概述
1967年,Welsh和Powell算法引入了图色数的上界。它提供了一个在静态图上运行的贪婪算法。
顶点根据其度数排序,得到的贪婪着色最多使用颜色,最多比图的最大度数多一个。这种启发式被称为威尔士-鲍威尔算法。
伪代码
威尔士鲍威尔算法:
- 求每个顶点的阶数。
- 按降价顺序列出顶点,即价度(v(i))>=度(v(i+1))。
- 为列表中的第一个顶点上色。
- 沿着已排序的列表向下,为每个未连接到相同颜色上方的有色顶点着色,然后划掉列表中的所有有色顶点。
- 对未着色的顶点重复此过程,使用新颜色始终按度数降序操作,直到所有顶点都按度数降序操作,直到所有顶点都着色为止。
源程序
using System;
using System.Collections;
using System.Collections.Generic;
namespace Legalsoft.Truffer.Algorithm
{
public class Vertex : IComparable<Vertex>
{
public int color { get; set; } = 0;
public int degree { get; set; } = 0;
public int CompareTo(Vertex o)
{
return o.degree - this.degree;
}
}
public class Welch_Powell_Color
{
public void Welsh_Powell(int n, Vertex[] vertex, int[,] edges)
{
Array.Sort(vertex);
int ncolor = 0;
int colored_cnt = 0;
while (colored_cnt < n)
{
ncolor++;
for (int i = 1; i <= n; i++)
{
if (vertex[i].color == 0)
{
bool ok = true;
for (int j = 1; j <= n; j++)
{
if (edges[i, j] == 1 && vertex[j].color == ncolor)
{
ok = false;
break;
}
}
if (!ok)
{
continue;
}
vertex[i].color = ncolor;
colored_cnt++;
}
}
}
}
}
}
相关文章
- C#数据Encrypt加密Encrypt解密的算法使用--非对称算法RSACryptoServiceProvider
- C#数据Encrypt加密Encrypt解密的算法使用
- C#数据结构与算法揭秘15
- [C#] c# 验证手机号码 最新的17手机号
- 揽货最短路径解决方案算法 - V2(增加了时间维度-客户允许的服务时间段,C#/JAVA同步实现,带python作图)
- C# .NET 如何批量增加或取消注释
- 重学c#系列——linq(1) [二十七]
- 重新整理数据结构与算法(c#)——KMP破解[二十七]
- 重新整理数据结构与算法(c#)—— 算法套路动态规划算法[二十六]
- 重新整理数据结构与算法(c#)—— 算法套路分治算法[二十五]
- c# aspose操作word文档
- C#委托和事件机制
- 重新整理数据结构与算法(c#)——算法套佛洛伊德算法[三十二]
- 重新整理数据结构与算法(c#)——算法套路普利姆算法[二十九]
- 重新整理数据结构与算法(c#)——KMP破解[二十七]
- 重新整理数据结构与算法(c#)—— 算法套路动态规划算法[二十六]
- 重新整理数据结构与算法(c#)—— 算法套路分治算法[二十五]
- C# 结构(很少能用到)
- C# 归并排序
- (六十三)c#Winform自定义控件-箭头(工业)-HZHControls
- C#实现多人语音聊天
- C#枚举
- [C#]c#中数据的同步加锁机制 的几种方法