学习来源：日撸 Java 三百行（31-40天，图）_闵帆的博客-CSDN博客
- 图的 m 着色问题
- 一、描述
- 二、解决思路
- 三、具体实现
- 1. 输入
- 2. 输出
- 3. 代码
- 4. 运行截图
- 邻接链表
- 一、描述
- 二、具体实现
- 1. 描述
- 2. 代码
- 3. 运行截图
- 总结
给定无向连通图 G 和 m 种不同的颜色.
用这些颜色为图 G 的各顶点着色, 每个顶点着一种颜色. 是否有一种着色法使 G 中每条边的 2 个顶点着不同颜色. 这个问题是图的 m 可着色判定问题.
若一个图最少需要 m 种颜色才能使图中每条边连接的 2 个顶点着不同颜色, 则称这个数 m 为该图的色数.
二、解决思路可以把这个问题的解空间转换为高度为 G + 1 层 的完全 m 叉树.
如何在这棵树中找到解呢？ 就是在深度优先遍历的前提下, 利用相邻节点颜色不能相同对这棵树进行"剪枝".
三、具体实现 1. 输入三个整数, 分别表示颜色数、已被着色节点数和存储着色的数组.
2. 输出若符合着色规则就打印着色的数组.
3. 代码
public void coloring(int paraNumColors) {
// Step 1. Initialize.
int tempNumNodes = connectivityMatrix.getRows();
int[] tempColorScheme = new int[tempNumNodes];
Arrays.fill(tempColorScheme, -1);
coloring(paraNumColors, 0, tempColorScheme);
}// Of coloring
public void coloring(int paraNumColors, int paraCurrentNumNodes, int[] paraCurrentColoring) {
// Step 1. Initialize.
int tempNumNodes = connectivityMatrix.getRows();
System.out.println("coloring: paraNumColors = " + paraNumColors + ", paraCurrentNumNodes = "
+ paraCurrentNumNodes + ", paraCurrentColoring" + Arrays.toString(paraCurrentColoring));
// A complete scheme.
if (paraCurrentNumNodes >= tempNumNodes) {
System.out.println("Find one:" + Arrays.toString(paraCurrentColoring));
return;
} // Of if
// Try all possible colors.
for (int i = 0; i < paraNumColors; i++) {
paraCurrentColoring[paraCurrentNumNodes] = i;
if (!colorConflict(paraCurrentNumNodes + 1, paraCurrentColoring)) {
coloring(paraNumColors, paraCurrentNumNodes + 1, paraCurrentColoring);
} // Of if
} // Of for i
}// Of coloring
public boolean colorConflict(int paraCurrentNumNodes, int[] paraColoring) {
for (int i = 0; i < paraCurrentNumNodes - 1; i++) {
// No direct connection.
if (connectivityMatrix.getValue(paraCurrentNumNodes - 1, i) == 0) {
continue;
} // Of if
if (paraColoring[paraCurrentNumNodes - 1] == paraColoring[i]) {
return true;
} // Of if
} // Of for i
return false;
}// Of colorConflict
public static void coloringTest() {
int[][] tempMatrix = { { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 0 }, { 0, 1, 0, 0 } };
Graph tempGraph = new Graph(tempMatrix);
tempGraph.coloring(3);
}// Of coloringTest
4. 运行截图
之前是通过矩阵来表示图, 这种存储方式被叫做邻接矩阵. 但是这种存储方式有一种缺点就是每个点都要记录, 如果面对连接不是很多的图就会浪费空间. 于是将邻接的节点组成一条链表, 然后再以各节点形成一个数组. 这样邻接链表就诞生了.
二、具体实现 1. 描述相当于图的压缩存储. 每一行数据用一个单链表存储.
重写了广度优先遍历. 可以发现, 使用队列的机制不变. 仅仅是把其中的 for 循环换成了 while, 避免检查不存在的边. 如果图很稀疏的话, 可以降低时间复杂度.
2. 代码package datastructure.graph;
import datastructure.queue.CircleObjectQueue;
public class AdjacencyList {
class AdjacencyNode {
int column;
AdjacencyNode next;
public AdjacencyNode(int paraColumn) {
column = paraColumn;
next = null;
}// Of AdjacencyNode
}// Of class AdjacencyNode
int numNodes;
AdjacencyNode[] headers;
public AdjacencyList(int[][] paraMatrix) {
numNodes = paraMatrix.length;
// Step 1. Initialize. The data in the headers are not meaningful.
AdjacencyNode tempPreviousNode, tempNode;
headers = new AdjacencyNode[numNodes];
for (int i = 0; i < numNodes; i++) {
headers[i] = new AdjacencyNode(-1);
tempPreviousNode = headers[i];
for (int j = 0; j < numNodes; j++) {
if (paraMatrix[i][j] == 0) {
continue;
} // Of if
// Create a new node.
tempNode = new AdjacencyNode(j);
// Link.
tempPreviousNode.next = tempNode;
tempPreviousNode = tempNode;
} // Of for j
} // Of for i
}// Of class AdjacentTable
public String toString() {
String resultString = "";
AdjacencyNode tempNode;
for (int i = 0; i < numNodes; i++) {
tempNode = headers[i].next;
while (tempNode != null) {
resultString += " (" + i + ", " + tempNode.column + ")";
tempNode = tempNode.next;
} // Of while
resultString += "rn";
} // Of for i
return resultString;
}// Of toString
public String breadthFirstTraversal(int paraStartIndex) {
CircleObjectQueue tempQueue = new CircleObjectQueue();
String resultString = "";
boolean[] tempVisitedArray = new boolean[numNodes];
tempVisitedArray[paraStartIndex] = true;
// Initialize the queue.
// Visit before enqueue.
tempVisitedArray[paraStartIndex] = true;
resultString += paraStartIndex;
tempQueue.enqueue(Integer.valueOf(paraStartIndex));
// Now visit the rest of the graph.
int tempIndex;
Integer tempInteger = (Integer) tempQueue.dequeue();
AdjacencyNode tempNode;
while (tempInteger != null) {
tempIndex = tempInteger.intValue();
// Enqueue all its unvisited neighbors. The neighbors are linked
// already.
tempNode = headers[tempIndex].next;
while (tempNode != null) {
if (!tempVisitedArray[tempNode.column]) {
// Visit before enqueue.
tempVisitedArray[tempNode.column] = true;
resultString += tempNode.column;
tempQueue.enqueue(Integer.valueOf(tempNode.column));
} // Of if
tempNode = tempNode.next;
} // Of for i
// Take out one from the head.
tempInteger = (Integer) tempQueue.dequeue();
} // Of while
return resultString;
}// Of breadthFirstTraversal
public static void breadthFirstTraversalTest() {
// Test an undirected graph.
int[][] tempMatrix = { { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 1 }, { 0, 1, 1, 0 } };
Graph tempGraph = new Graph(tempMatrix);
System.out.println(tempGraph);
AdjacencyList tempAdjList = new AdjacencyList(tempMatrix);
String tempSequence = "";
try {
tempSequence = tempAdjList.breadthFirstTraversal(2);
} catch (Exception ee) {
System.out.println(ee);
} // Of try.
System.out.println("The breadth first order of visit: " + tempSequence);
}// Of breadthFirstTraversalTest
public static void main(String args[]) {
int[][] tempMatrix = { { 0, 1, 0 }, { 1, 0, 1 }, { 0, 1, 0 } };
AdjacencyList tempTable = new AdjacencyList(tempMatrix);
System.out.println("The data are:rn" + tempTable);
breadthFirstTraversalTest();
}// Of main
} // Of class AdjacencyList
3. 运行截图
总结
暴力破解看起来没有什么逻辑, 但是面对有些问题还是很有效的.
着色问题感性上来看很难下手, 要是转换成了完全多叉树就能够很轻易地解决. 编程的诀窍就是在于把事物抽象. 不是任何问题都有现成的解, 或许某天打开 CSDN GitHub 甚至于 StackOverflow 你都找不到适合的解, 那么此时自己就应该想到该把问题用自己的方式转化了.
庆幸的是前人已经完成了许多工作, 我的学习不过是站在巨人的肩膀上罢了.
