Java学习-Day18

图的 m 着色问题

一、描述

给定无向连通图 G 和 m 种不同的颜色.

用这些颜色为图 G 的各顶点着色, 每个顶点着一种颜色. 是否有一种着色法使 G 中每条边的 2 个顶点着不同颜色. 这个问题是图的 m 可着色判定问题.

若一个图最少需要 m 种颜色才能使图中每条边连接的 2 个顶点着不同颜色, 则称这个数 m 为该图的色数.

二、解决思路

可以把这个问题的解空间转换为高度为 G + 1 层 的完全 m 叉树.

如何在这棵树中找到解呢？ 就是在深度优先遍历的前提下, 利用相邻节点颜色不能相同对这棵树进行"剪枝".

三、具体实现

1. 输入

三个整数, 分别表示颜色数、已被着色节点数和存储着色的数组.

2. 输出

若符合着色规则就打印着色的数组.

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/**
 *********************
 * Coloring. Output all possible schemes.
 * 
 * @param paraNumColors The number of colors.
 *********************
 */
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

/**
 *********************
 * Coloring. Output all possible schemes.
 * 
 * @param paraNumColors       The number of colors.
 * @param paraCurrentNumNodes The number of nodes that have been colored.
 * @param paraCurrentColoring The array recording the coloring scheme.
 *********************
 */
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

/**
 *********************
 * Coloring conflict or not. Only compare the current last node with previous
 * ones.
 * 
 * @param paraCurrentNumNodes The current number of nodes.
 * @param paraColoring        The current coloring scheme.
 * @return Conflict or not.
 *********************
 */
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

/**
 *********************
 * Coloring test.
 *********************
 */
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. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
package datastructure.graph;

import datastructure.queue.CircleObjectQueue;

/**
 * Adjacency list for directed graph.
 * 
 * @author ShiHuai Wen shihuaiwen@outlook.com.
 */
public class AdjacencyList {
	/**
	 * An inner class for adjacent node.
	 */
	class AdjacencyNode {
		/**
		 * The column index.
		 */
		int column;

		/**
		 * The next adjacent node.
		 */
		AdjacencyNode next;

		/**
		 *********************
		 * The first constructor.
		 * 
		 * @param paraColumn The column.
		 *********************
		 */
		public AdjacencyNode(int paraColumn) {
			column = paraColumn;
			next = null;
		}// Of AdjacencyNode
	}// Of class AdjacencyNode

	/**
	 * The number of nodes. This member variable may be redundant since it is always
	 * equal to headers.length.
	 */
	int numNodes;

	/**
	 * The headers for each row.
	 */
	AdjacencyNode[] headers;

	/**
	 *********************
	 * The first constructor.
	 * 
	 * @param paraMatrix The the matrix indicating the graph.
	 *********************
	 */
	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

	/**
	 *********************
	 * Overrides the method claimed in Object, the superclass of any class.
	 *********************
	 */
	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 += "\r\n";
		} // Of for i

		return resultString;
	}// Of toString

	/**
	 *********************
	 * Breadth first traversal.
	 * 
	 * @param paraStartIndex The start index.
	 * @return The sequence of the visit.
	 *********************
	 */
	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

	/**
	 *********************
	 * Unit test for breadthFirstTraversal. The same as the one in class Graph.
	 *********************
	 */
	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

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	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:\r\n" + tempTable);

		breadthFirstTraversalTest();
	}// Of main
} // Of class AdjacencyList

3. 运行截图

总结

暴力破解看起来没有什么逻辑, 但是面对有些问题还是很有效的.

着色问题感性上来看很难下手, 要是转换成了完全多叉树就能够很轻易地解决. 编程的诀窍就是在于把事物抽象. 不是任何问题都有现成的解, 或许某天打开 CSDN GitHub 甚至于 StackOverflow 你都找不到适合的解, 那么此时自己就应该想到该把问题用自己的方式转化了.

庆幸的是前人已经完成了许多工作, 我的学习不过是站在巨人的肩膀上罢了.