C#，图颜色问题（MCP，M-coloring problem）的回溯（Backtracking）算法与源代码

 给定一个无向图和一个数字m，确定该图是否最多可以使用m种颜色着色，以确保该图的两个相邻顶点没有使用相同的颜色着色。这里，图的着色意味着将颜色分配给所有顶点。
输入：
二维数组图[V][V]，其中V是图中的顶点数，图[V][V]是图的邻接矩阵表示。如果从i到j有一条直边，则值图[i][j]为1，否则图[i][j]为0。
整数m是可以使用的最大颜色数。
输出：
数组颜色[V]的数字应为1到m。颜色[i]应表示指定给第i个顶点的颜色。如果图形不能用m颜色着色，代码也应该返回false。

我们将使用回溯来解决上述问题。

回溯是通过测试所有可能的组合来解决问题的方法。如果有任何子问题不符合给定的约束，那么我们将放弃完整的子问题（回溯），后退一步，然后尝试其他可能的组合。回溯算法在时间上通常是指数的。

我们将使用颜色数组color[]来存储M种颜色。现在遍历颜色[]，然后将每个颜色逐个指定给所有顶点。如果任何颜色分配与约束不匹配，则我们将回溯并取消分配先前分配给顶点的颜色。如果顶点计数达到顶点总数，我们将返回true，如果任何赋值都不符合给定条件（相邻顶点必须具有不同的颜色），那么我们将返回false。

递归：

在for a循环的帮助下尝试从1到m的每种颜色。

如果可以使用该颜色对其进行着色，即相邻节点均不具有相同的颜色，则Is safe函数将返回true。

如果这是一个算法并遵循某种直觉，请提及它。

将其着色，然后调用下一个节点的递归函数，如果它返回true，我们将返回true。

如果为假，则去掉颜色。

现在，如果我们已经尝试了从1到m的每种颜色，并且不可能用m种颜色中的任何一种来着色，那么返回false。

源程序（POWER BY TRUFFER）：

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;
 
namespace Legalsoft.Truffer.Algorithm
{
	public class MCP_Node
	{
		public int color { get; set; } = 1;
		public HashSet<int> edges { get; set; } = new HashSet<int>();
	}
 
	public static partial class Algorithm_Gallery
	{
		private static int Vertex_Number = 4;
 
		#region  算法1
		private static bool MCP_IsSafe(bool[,] graph, int[] color)
		{
			for (int i = 0; i < Vertex_Number; i++)
			{
				for (int j = i + 1; j < Vertex_Number; j++)
				{
					if (graph[i, j] && color[j] == color[i])
					{
						return false;
					}
				}
			}
			return true;
		}
 
		public static bool MCP_Solve(bool[,] graph, int m, int i, int[] color)
		{
			if (i == Vertex_Number)
			{
				if (MCP_IsSafe(graph, color))
				{
					return true;
				}
				return false;
			}
 
			for (int j = 1; j <= m; j++)
			{
				color[i] = j;
 
				if (MCP_Solve(graph, m, i + 1, color))
				{
					return true;
				}
				color[i] = 0;
			}
 
			return false;
		}
		#endregion
 
		#region  算法2
 
		private static bool MCP_IsSafe(int v, int[,] graph, int[] color, int c)
		{
			for (int i = 0; i < Vertex_Number; i++)
			{
				if (graph[v, i] == 1 && c == color[i])
				{
					return false;
				}
			}
			return true;
		}
 
		private static bool MCP_Solve_Utility(int[,] graph, int m, ref int[] color, int v)
		{
			if (v == Vertex_Number)
			{
				return true;
			}
			for (int c = 1; c <= m; c++)
			{
				if (MCP_IsSafe(v, graph, color, c))
				{
					color[v] = c;
 
					if (MCP_Solve_Utility(graph, m, ref color, v + 1))
					{
						return true;
					}
					color[v] = 0;
				}
			}
 
			return false;
		}
 
		private static bool MCP_Solve(int[,] graph, int m)
		{
			int[] color = new int[Vertex_Number];
			for (int i = 0; i < Vertex_Number; i++)
			{
				color[i] = 0;
			}
			if (MCP_Solve_Utility(graph, m, ref color, 0) == false)
			{
				return false;
			}
 
			return true;
		}
		#endregion
 
		#region  算法3
 
		public static bool MCP_Solve(List<MCP_Node> nodes, int n, int m)
		{
			List<int> visited = new List<int>();
 
			for (int i = 0; i < n + 1; i++)
			{
				visited.Add(0);
			}
 
			int maxColors = 1;
 
			for (int sv = 1; sv <= n; sv++)
			{
				if (visited[sv] > 0)
				{
					continue;
				}
				visited[sv] = 1;
				Queue q = new Queue();
				q.Enqueue(sv);
 
				while (q.Count != 0)
				{
					int top = (int)q.Peek();
					q.Dequeue();
 
					foreach (int it in nodes[top].edges)
					{
						if (nodes[top].color == nodes[it].color)
						{
							nodes[it].color += 1;
						}
						maxColors = Math.Max(maxColors, Math.Max(nodes[top].color, nodes[it].color));
						if (maxColors > m)
						{
							return false;
						}
						if (visited[it] == 0)
						{
							visited[it] = 1;
							q.Enqueue(it);
						}
					}
				}
			}
			return true;
		}
		#endregion
	}
}