C#,图论与图算法,图着色问题(Graph Coloring)的威尔士-鲍威尔(Welch Powell Algorithm)算法与源代码

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》
1 图着色算法概述
1967年,Welsh和Powell算法引入了图色数的上界。它提供了一个在静态图上运行的贪婪算法。
顶点根据其度数排序,得到的贪婪着色最多使用颜色,最多比图的最大度数多一个。这种启发式被称为威尔士-鲍威尔算法。

2 伪代码
威尔士鲍威尔算法:
- 求每个顶点的阶数。
- 按降价顺序列出顶点,即价度(v(i))>=度(v(i+1))。
- 为列表中的第一个顶点上色。
- 沿着已排序的列表向下,为每个未连接到相同颜色上方的有色顶点着色,然后划掉列表中的所有有色顶点。
- 对未着色的顶点重复此过程,使用新颜色始终按度数降序操作,直到所有顶点都按度数降序操作,直到所有顶点都着色为止。






3 源程序
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#,图论与图算法,图着色问题(Graph Coloring)的威尔士-鲍威尔(Welch Powell Algorithm)算法与源代码
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》 1 图着色算法概述 1967年,Welsh和Powell算法引入了…...
用python写一个脚本,实现加速3X并压缩mp4视频以降低文件大小。
为了实现您的需求,我们将使用Python的moviepy库来加速MP4视频3倍并使用ffmpeg选项来进行压缩,以降低文件大小。如果您还没有安装这些库,请先通过以下命令进行安装: pip install moviepy这是一个步骤概述: 读取视频文…...
Flink广播流 BroadcastStream
文章目录 前言BroadcastStream代码示例Broadcast 使用注意事项 前言 Flink中的广播流(BroadcastStream)是一种特殊的流处理方式,它允许将一个流(通常是一个较小的流)广播到所有的并行任务中,从而实现在不同…...
IP数据报格式
每一行都由32位比特,即4个字节组成,每个格子称为字段或者域。IP数据报由20字节的固定部分和最大40字节的可变部分组成。 总长度 总长度为16个比特,该字段的取值以字节为单位,用来表示IPv4数据报的长度(首部长度数据载荷长度)最大…...
GET https://registry.npm.taobao.org/xxxx error (CERT_HAS_EXPIRED)解决
PNPM用的阿里源,提示意思是证书过期了,参考网上的解决办法。执行 pnpm config set registry https://registry.npmmirror.com 再用pnpm config get registry查看,确实是 https://registry.npmmirror.com 但是仍旧报错,发现还…...
SSM Java Web项目由于spring-mvc.xml配置不对带来的一系列问题
1 介绍 一年多前,我就买了好多关于Java开发类的书籍,内容关于Java Web实操、Spring 学习指南、Maven实战、IntelliJ IDEA软件开发与应用等等。可是由于工作繁忙,这些书没系统地看完。这也是参加工作后的无奈吧! 寒假期间的一周&…...
MySQL事务隔离
什么是事务隔离? 为了确保在并发事务执行时,各个事务之间能够相互独立、互不干扰地运行,从而保证数据的一致性。 事务的隔离级别 MySQL事务隔离为了满足不同场景,提供了4个事务隔离级别(严格来讲是InnoDB存储引擎支…...
Java基础知识总结(1)
Java概况 JavaSE是java分类中的标准版,是刚接触java要学习的基础知识。 JavaEE是java分类中的企业版,是java中的高级,涉及到的知识广泛。 JavaME中M是Micro的缩写,用在嵌入式等电子设备中。 Java软件工程师:通过Ja…...
脚手架原理之webpack处理html文件和模块打包
脚手架原理之webpack处理html文件和模块打包 为了更好的理解项目脚手架的使用,我们来学习一下webpack工具,因为脚手架的底层就是基于webpack工具实现的。 安装 webpack工具是基于nodejs的,所以首先要有nodejs环境,其次需要下载…...
Winform编程详解一:Form窗口
一、属性介绍 1. (Name) 窗体的对象标识符ID 2. Text 修改窗口左上角标题 3. Icon 修改窗口左上角图标,图标最合适大小 32*32 4. 修改窗体第一次出现位置 代码修改:StartPosition System.Windows.Forms.FormStartPosition.CenterScreen; 5…...
Windows Server 2025 Install Preview
前言 Windows Server 2025 带来了巨大的发展,例如面向所有人的热补丁、下一代 Active Directory 和 SMB、关键任务数据和存储、Hyper-V 和 AI 等 Windows Server 2025 Preview download 下载 已注册的预览体验成员可以直接导航到 Windows Server Insider Preview 下载页面。…...
四、MySQL
MySQL MySQL1.初识网站2.安装MySQL2.1 下载(最重要的一点是路径中不能有中文,哪怕是同级目录也不行)2.2安装补丁2.3安装2.4创建配置文件2.5初始化 3.启动MySQL4.连接测试4.1 设置密码4.2 查看已有的文件夹(数据库)4.3 …...
C#使用泛型自定义的方法设计队列CQueue<T>类
目录 一、涉及到的知识点 1.C#中的队列类 2.自定义队列的方法 (1)先设计一个CList<T>类 (2)再设计CQueue<T>类 二、自定义队列CQueue<T>类的实例 一、涉及到的知识点 1.C#中的队列类 在C#中实现队列类&a…...
IDEA自定义Maven仓库
Maven 是一款广泛应用于 Java 开发的工具,其作用类似于一个全自动的 JAR 包管理器,能够方便地导入开发所需的相关 JAR 包。在使用 Maven 进行 Java 程序开发时,开发者能够极大地提高开发效率。以下是关于如何安装 Maven 以及在 IDEA 中配置自…...
Codeql复现CVE-2018-11776学习笔记
基本使用 1、首先下载struts2漏洞版本源码: https://codeload.github.com/apache/struts/zip/refs/tags/STRUTS_2_3_20 2、构建codeql数据库(构建失败文末有解决办法): codeql database create ~/CodeQL/databases/struts2-2.3.…...
CVE-2024-27199 JetBrains TeamCity 身份验证绕过漏洞2
漏洞简介 TeamCity Web 服务器中发现了第二个身份验证绕过漏洞。这种身份验证旁路允许在没有身份验证的情况下访问有限数量的经过身份验证的端点。未经身份验证的攻击者可以利用此漏洞修改服务器上有限数量的系统设置,并泄露服务器上有限数量的敏感信息。 项目官网…...
ms office学习记录12:Excel学习记录㈥
数据工具 分列的其他运用:身份证号中“出生日期”切片:分列→固定宽度→下一步→切割出三列→下一步→不导入第一列→导入第二列且转换成日期→不导入第三列→完成 删除重复值:定位到要“数据”选项卡→删除重复项→取消全选再勾选要删除的…...
基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的条形码二维码检测系统(深度学习+UI界面+训练数据集+Python代码)
摘要:在物流和制造业中,开发一套高效的条形码与二维码识别系统显得尤为关键。本博文深入探讨了如何利用深度学习技术打造出一套先进的条形码及二维码检测系统,并且提供了一套完整的实施方案。该系统搭载了性能卓越的YOLOv8算法,并…...
npm yarn 一起使用报错
项目记录,具有独特性,仅供参考 项目好好的运行,前一天装个测试工具包, 突然就不行了,卸载重装也不行,所有的项目都安装失败,新起一个项目也不行,有时候某个单独安装一个包可以&…...
基于springboot实现驾校信息管理系统项目【项目源码+论文说明】计算机毕业设计
基于springboot实现驾校信息管理系统演示 摘要 随着人们生活水平的不断提高,出行方式多样化,也以私家车为主,那么既然私家车的需求不断增长,那么基于驾校的考核管理也就不断增强,那么业务系统也就慢慢的随之加大。信息…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
