采用C++实现区间图着色问题（贪心算法）实例详解_贪心法求解图的着色问题算法用c++语言描述

区间图着色

贪心算法

5星 · 超过95%的资源 8 浏览量更新于2023-03-16 评论 3 收藏 43KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

采用采用C++实现区间图着色问题（贪心算法）实例详解实现区间图着色问题（贪心算法）实例详解

主要介绍了采用C++实现区间图着色问题（贪心算法）,很经典的算法问题,需要的朋友可以参考下

本文所述算法即假设要用很多个教室对一组活动进行调度。我们希望使用尽可能少的教室来调度所有活动。采用C++的贪心算

法，来确定哪一个活动使用哪一间教室。

对于这个问题也常被称为区间图着色问题，即相容的活动着同色，不相容的着不同颜色，使得所用颜色数最少。

具体实现代码如下：

//贪心算法

#include "stdafx.h"

#include<iostream>

#define N 100

using namespace std;

struct Activity

{

int number; //活动编号

int begin; //活动开始时间

int end; //活动结束时间

bool flag;//此活动是否被选择

int roomNum; //此活动在哪间教室举行

};

//对于活动集，按照结束时间递增排序,使用快速排序

void fast_sort(Activity *act,int f,int t)

{

if(f<t)

{

int i = f-1,j = f;

Activity a = act[t];

while(j<t)

{

if(act[j].end<=a.end)

{

i++;

Activity temp1 = act[i];

act[i] = act[j];

act[j] = temp1;

}

j++;

}

Activity temp2 = act[t];

act[t] = act[i+1];

act[i+1] = temp2;

fast_sort(act,f,i);

fast_sort(act,i+2,t);

}

//把每一个相容的活动集添加到一个教室，使得教室数目最少

int select_room(Activity *act,int *time,int n)

{

int i = 1;

int j = 1;

int sumRoom;

//目前所用的教室数目

sumRoom = 1;

int sumAct;

//目前有多少活动被选择了

sumAct = 1;

//教室1目前最晚时间为排在最前面的活动的结束时间

time[1] = act[0].end;

//最先结束的活动放在教室1中

act[0].roomNum = 1;

for(i=1;i<n;i++)

{

for(j=1;j<=sumRoom;j++)

{

//如果活动act[i]的开始时间大于等于j教室目前的最晚结束时间且此活动还没有被选择，

//则此活动与目前这间教室里面的活动是兼容的，可以加入进去

if((act[i].begin>=time[j])&&(!act[i].flag))

{

//此活动的教室号码

act[i].roomNum = j;

//此活动被选择

act[i].flag = true;

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

maXZero

2023-07-26

文章使用了简单易懂的语言，没有过多的专业术语，让我在阅读时感到轻松愉快。

weixin_38641561

粉丝: 5
资源: 943

会员权益专享

采用C++实现区间图着色问题（贪心算法）实例详解

评论5

会员权益专享

最新资源

采用C++实现区间图着色问题（贪心算法）实例详解

评论5

着色问题的回溯解法(C语言)

C语言图的着色问题回溯法

采用贪心法求解着色问题（JAVA）

加权列表着色问题的分支和价格算法

"图着色问题的加权版本：分支和价格算法

C++实现二分查找算法详解

凸重着色问题的GRASP算法

c++广度优先解决迷宫问题【示例代码】C++实现广度优先搜索算法

图着色问题贪心算法c语言,采用C++实现区间图着色问题（贪心算法）实例详解...

图着色问题贪心算法c++

贪心算法实现图着色c++

无向图着色问题贪心算法c++

c++贪心算法图着色

贪心算法区间调度问题c++算法演示

C++ 实现背包问题的贪心算法，不是0-1背包问题

c++贪心算法实现会场安排问题

C++贪心实现区间覆盖问题

写出背包问题的贪心选择性质 自然语言描述背包问题贪心选择算法 C++语言描述背包问题贪心选择算法

C++贪心算法解决删数问题

tsp问题贪心算法c++

会员权益专享

最新资源

写出背包问题的贪心选择性质自然语言描述背包问题贪心选择算法 C++语言描述背包问题贪心选择算法