C++ 图论算法实现项目日程安排 - 最少比赛场次

#include /是C++程序中非常常见的一条预处理指令，它包含了iostream库。 iostream库提供了C++程序中用于处理标准输入/输出流的基本功能/

#include /vector是一种顺序容器，事实上和数组差不多，但它比数组更优越。 一般来说数组不能动态拓展，因此在程序运行的时候不是浪费内存， 就是造成越界。而vector正好弥补了这个缺陷，它的特征是相当于可 分配拓展的数组，它的随机访问快，在中间插入和删除慢，但在末端 插入和删除快，而且如果你用.at()访问的话，也可以做越界检查/

#include /是C++中一个常用的预处理指令，它包含了algorithm库。这个库提 供了大量用于操作序列（例如数组、向量、列表等容器）的通用算 法，这些算法包括查找、排序、复制、移动、修改和其他操作/

#include /是C++程序中常用的预处理指令，它包含了fstream库。这个库提供了 用于处理文件输入/输出的类/ #include <string.h> /表示包含字符串处理函数的头文件，是C语言中的预处理命令/

#include <stdio.h> /stdio.h是标准输出/输出头文件。可以简单理解为在这个文件中包含 了一些输入和输出的函数。换句话说，要用到printf（）和scanf（） 这两个打印和输入函数，就必须要有这个文件/

#include <windows.h> /是写window程序需要的重要头文件,之后用到system("pause")/

using namespace std; /namespace 被称为 命名空间，使用时可以将其认为是一块单独开 辟出的空间。这块空间内，可以随意定义 变量、函数等。命名空 间内的变量 是不会与 命名空间外 的 其他同名变量 冲突的。将 命为 std 的空间展开了，而 std 可以看作是C++提供的标准库的 函数所在的 命名空间/

int map[49] = { 0 };

void Create(int a[]) { //根据用户输入进行建图 for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) if ((a[i] != a[j]) && (a[i] != 0) && (a[j] != 0)) { map[(a[i] - 1) * 7 + (a[j] - 1)] = 1; } }

struct Node { //图结点 int index;//结点在矩阵中的行数即位置 int degree;//结点度数，用于根据从大到小的度数关系进行涂色 int mark;//结点染色标记 };

string name[] = { '标枪', '铅球', '铁饼', '100m', '200m', '跳远', '跳高' };

bool cmp(Node a, Node b) { //自定义'小于' return a.degree > b.degree; }

void Print(vector mark, int n, vector node, int Mark) { //创建可视化图表 int a[10] = { 0 };//存储标记对应的项目数 int b = 0, c = 1; for (int j = 0; j < mark.size(); j++) { //同一标记对应项目数的赋值 for (int i = 0; i < n; i++) if (node[i].mark == mark[j]) a[j]++; } int max = a[0]; for (int j = 0; j < mark.size() - 1; j++) { //确定项目日程表中列数的最大值 if (a[j + 1] > max) max = a[j + 1]; } cout << ' _________________________________' << endl;//实现项目日程的可视化 for (int p = 0; p < Mark; p++) { cout << ' | | | | |' << endl; if (c == 1) cout << '|' << '|'; else if (c == 2) cout << '|' << '|'; else if (c == 3) cout << '|' << '|'; else if (c == 4) cout << '|' << '|'; else if (c == 5) cout << '|' << '|'; for (int i = 0; i < n; i++) { if (node[i].mark == c) { cout << name[node[i].index] << ' |'; b++; } } if (b < max) for (int i = 0; i < max - b; i++) cout << ' |'; b = 0; c++; cout << endl; cout << ' ------------------' << endl; } }

int fillcolor(int map[], int n) { //涂色 cout << '邻接矩阵' << endl; int Mark = 0; vectormark;//动态标记集 vectornode;//动态结点集 node.resize(n);//为结点集分配空间 for (int i = 0; i < n; i++) { //统计图中结点的度 node[i].degree = node[i].mark = 0;//度数、标记均初始化为0 node[i].index = i; for (int j = 0; j < n; j++) { if (map[i * n + j] == 1) node[i].degree++; } } sort(node.begin(), node.end(), cmp);//将图结点降序排列

for (int i = 0; i < n; i++) {
	for (int j = 0; j < mark.size(); j++) { //取染色集元素进行染色
		if (node[i].mark == 0)
			node[i].mark = mark[j];
		for (int k = 0; k < n; k++) {
			if ((map[node[i].index * n + k] == 1) && (node[k].mark == node[i].mark)) { //两结点相邻且颜色相同，取消标记
				node[i].mark = 0;
				break;
			}
		}
	}
	if (node[i].mark == 0) {
		mark.push_back(++Mark);
		node[i].mark = mark.back();
	}
}
Print(mark, n, node, Mark); //创建可视化图表
return Mark;//返回所需场次

};

int main() { cout << '各项目对应编号为：标枪(1),铅球(2),铁饼(3),100m(4),200m(5),跳远(6),跳高(7) ' << endl; cout << '请依次将选手所报项目编号输入' << endl; int a[3] = { 0 }; string b[5] = { '张三', '李四', '王五', '赵六', '李七' }; for (int i = 0; i < 5; i++) { cout << '请输入 ' << b[i] << ' 所报项目编号：'; for (int j = 0; j < 3; j++) { a[j] = cin.get() - 48; if (j == 2 && a[j] != -38) cin.get(); else if (a[j] == -38) { a[j] = 0; break; } } Create(a); } for (int i = 0; i < 7; i++) { for (int j = 0; j < 7; j++) cout << map[i * 7 + j] << ' '; cout << endl; } int n = fillcolor(map, 7); cout << '将需要比赛' << n << '场' << endl; system('pause'); }

系统功能模块结构图及主要函数说明？内容：系统功能模块结构图如下：

+-----------------+
|     主函数      |
+-----------------+
         |
         | 
+-----------------+
|      Create     |
+-----------------+
         |
         |
+-----------------+
|   fillcolor     |
+-----------------+
         |
         |
+-----------------+
|     Print       |
+-----------------+

主要函数说明如下：

1. Create(int a[]): 根据用户输入的项目编号，建立图的邻接矩阵。
2. fillcolor(int map[], int n): 对图进行涂色操作，返回所需的比赛场次。
3. Print(vector<int> mark, int n, vector<Node> node, int Mark): 创建可视化图表，将图的涂色结果输出。
4. main(): 主函数，负责用户输入和调用其他函数实现系统功能。