Note: here are the synchronous notes and records of JAVA self-study and understanding. If you have any questions, please correct them

catalogue

1, About coloring

2, Code implementation ideas

3, Code implementation process

1. Initialization

2. Core code (DFS part)

3. Judgment of dyeing rationality

4, Data simulation

summary

1, About coloring

Coloring problem is a kind of very classic combination and arrangement problem. Many of you must have been exposed to this kind of problem in high school. Here, in the form of a topic, let's review this kind of classic questions:

Now there are the above map areas. In order to clearly represent the map boundary, we require different colors on each area of the map. However, due to the priority of color, only five different colors can be used to paint the parts of A, B, C and D in the map. Each part is painted with only one color, and the adjacent parts are painted with different colors to ensure differentiation. How many different painting methods are there?

The solution of this kind of problem may be familiar to us in high school. In short, enumeration. Let's first assume that A chooses one of the five colors, so there are five cases; At this time, regardless of C, B only knows that A has used one color, so adjacent B can only choose A to use one of the remaining four; C similarly, regardless of D, it can only choose one of the remaining colors used by A and B, which is obviously the case in 3; D is the same as 4. To sum up, the total situation is 5 * 4 * 3 * 4 = 240.

This problem is specifically mentioned in the exercise of graph today. Obviously, this kind of problem has very obvious characteristics of data structure graph. Because the close connection between map regions is equivalent to the connection of nodes in the graph. Specifically, because the adjacency is bidirectional, it corresponds to our undirected graph structure. As shown in the figure below:

Suppose today's task is to find out the combination of each dyeing with code, would you think so? When we wrote this question, we adopted the idea of enumeration, which is also true in the program. We will use the method of enumeration search to complete this process, which is commonly known as "violence" solution. Therefore, the enumeration of graph structure involves violence at the same time, so it is natural to come to the conclusion that DFS is used.

2, Code implementation ideas

Firstly, the coloring problem can be abstracted as an undirected graph. Each node of the undirected graph can carry a weight as the color of the graph, and then the weight of any node must be different from its adjacent nodes; Then determine our information carrier. We can give the weight (color) of each node in turn according to the number of nodes, so there is no need to set an additional graph structure to store color information; Finally, determine the characteristics of the data type. The color does not need to be explained by special characters. We default to the natural sequence 0, 1, 2, n indicates a certain color (we don't consider which colors these subscripts correspond to). The default color tag array is - 1 by default, indicating that there is no coloring. At the same time, the subscript index of the linear table corresponds to the node serial number (in the following figure, it is ABCD).

Although the calculation of this problem adopts the idea of DFS and involves the simulation of graph, the routine it completes is not node traversal based on DFS. Through the above analysis, the goal of the algorithm is to get a color marker array paraCurrentColoring, because this array corresponds to the region through subscript, which can guide us to dye. Just right, you can only traverse the color array to get the node corresponding to the subscript, and then judge the dyeing of other nodes connected to the node, so as to determine the color of the current node. In conclusion, although this topic involves graphs, it is essentially a linear DFS enumeration problem. The function of graphs is only reflected in: the rules of linear enumeration are based on the connectivity of graphs.         

When we just analyzed the coloring problem, i made an obvious emphasis (the underlined part). When we consider a coloring area, we ignore the rest of the parts we don't care about, so when considering the conflict in the program implementation, we only need to consider the colored area. Since this algorithm plans to search the color array from left to right, if it is currently located at the \ (i \) position of the color tag array, then any position \ (k (0 \ leqslant k < i) \) has been dyed, so we only need to consider the \ (k \) node when considering the connectivity problem.

3, Code implementation process

1. Initialize

	/**
	 *********************
	 * 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

Many search problems need basic search data preparation. The common method is to set a "set" around the recursive part of the search. In this set, we can complete many basic initialization (here we complete the initialization of the color tag array), and also increase the expansibility and maintainability of the recursive part.

2. Core code (DFS part)

	/**
	 *********************
	 * 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, paraCurrentColoring)) {
				coloring(paraNumColors, paraCurrentNumNodes + 1, paraCurrentColoring);
			} // Of if
		} // Of for i
	}// Of coloring

It can be found that this function is an overload of the previous function. This writing can avoid various naming problems in the same function direction. Of course, it depends on your own habits.

The DFS operation is initialized from the top to the bottom (the two parts of the DFS operation are usually ignored):

1. Conditional exit judgment part
2. Circular branch finding part (multipurpose for)

In the specific implementation, these two parts can play many tricks. For example, you can put the access operation of the current function part of the team in the middle of step 1 and step 2 or before step 1; In the second step, the content placed behind the function entry can be used as the code specially executed during backtracking (this code is not required, and the process is used for unmarking and other functions)

This recursion problem uses paraCurrentNumNodes to represent the index subscript of the current linear part, and the recursion body takes this as the in-depth identification of recursion. Therefore, the conditional exit part is to judge whether the current paraCurrentNumNodes is out of bounds.

The access part is above the exit entry. Because the code goal is to enumerate all dyeing codes, the access operation is basic printing.

The loop branch part enumerates the number of available colors (paraNumColors) respectively, records the colors in the color tag array, and judges whether the dyeing is reasonable. If it is reasonable, it will enter the next step of dyeing, enter the recursive body, and the recursive depth identification + 1. Here, the operation of "judging whether the dyeing is reasonable" is specially encapsulated by a function, as shown below.

3. Judgment of dyeing rationality

The rationality judgment of dyeing has been described in the second part. It only needs to judge whether the part before the current subscript of the linear array marked with color constitutes a connected relationship:

	/**
	 *********************
	 * 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; i++) {
			// No direct connection.
			if (connectivityMatrix.getValue(paraCurrentNumNodes, i) == 0) {
				continue;
			} // Of if

			if (paraColoring[paraCurrentNumNodes] == paraColoring[i]) {
				return true;
			} // Of if
		} // Of for i
		return false;
	}// Of colorConflict

The reverse judgment of the positive judgment adopted here is the conflict judgment. In short, if true is returned, it indicates that the dyeing is unreasonable. In the for loop, the connected part is filtered first, and then the color is judged.

4, Data simulation

Because the connectivity of the graph is too complex to verify, a relatively simple undirected graph is used to simulate

It can be seen that the adjacency matrix of an undirected graph is a strictly symmetric matrix.  

Unit test code:

	/**
	 *********************
	 * 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(2);
		tempGraph.coloring(3);
		System.out.println(tempGraph);
	}// Of coloringTest

Output results (display only part)

summary

The dyeing problem is an enumeration problem. This process is cumbersome, but it seems very convenient to give it to the violent search of the computer. There are not a few enumeration phenomena in reality. Although some problems can be calculated by using the arrangement and combination idea of combinatorial mathematics, theoretical things sometimes can not adapt to a very flexible environment. Therefore, enumeration is still a key method. Often, computers are the key to realize these methods. After all, it is impossible to spend time and manpower enumerating large-scale enumeration problems in real life.

Therefore, in order to deal with real problems with computers, we must learn how to enumerate and search data violently with computers, which should be the basic idea of data processing after data abstraction. At the same time, the violent algorithm is often an optimized wall beam, because the characteristics of specific problems will always be revealed in the process of the implementation of the violent algorithm, which are not easy to find in the case of a single dead buckle problem. This process we used to call pruning.