Java（14）

学习来源：日撸 Java 三百行（31-40天，图）

第 35 天: 图的 m 着色问题

经典的回溯算法，万能的暴力解题法。
输入：输入整型二维矩阵构造图和整型数m代表m种颜色
输出：输出图是否m可着色并输出不同的着色法
优化目标：无

	/**
	 * @Description: Coloring. 
	 * @param paraNumColors The number of colors.
	 */
	public void coloring(int paraNumColors) {
		int tempNumNodes = connectivityMatrix.getRows();
		int[] tempColorScheme = new int[tempNumNodes];
		Arrays.fill(tempColorScheme, -1);

		coloring(paraNumColors, 0, tempColorScheme);
	}// Of coloring

	/**
	 * @Description: 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) {
		int tempNumNodes = connectivityMatrix.getRows();

		System.out.println("coloring: paraNumColors = " + paraNumColors + ", paraCurrentNumNodes = "
				+ paraCurrentNumNodes + ", paraCurrentColoring" + Arrays.toString(paraCurrentColoring));
		if (paraCurrentNumNodes >= tempNumNodes) {
			System.out.println("Find one:" + Arrays.toString(paraCurrentColoring));
			return;
		} // Of if

		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

	/**
	 * @Description: 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++) {
			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

	public static void main(String args[]) {
		System.out.println("Hello!");
		Graph tempGraph = new Graph(3);
		System.out.println(tempGraph);

		getConnectivityTest();

		breadthFirstTraversalTest();

		depthFirstTraversalTest();

		coloringTest();
	}// Of main

运行截图：

第 36 天: 邻连表

相当于图的压缩存储，每一行数据用一个单链表存储。
输入：输入整型二维数组构造邻接表表示图
输出：输出广度优先遍历序列
优化目标：无

package my_java;

import my_java.CircleObjectQueue;

/**
 * @Description: Adjacency list for directed graph.
 * @author: Xin-Yu Li
 * @date: 2022年4月25日
 */
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;
		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

				tempNode = new AdjacencyNode(j);
				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 += "\r\n";
		} // 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;
		tempVisitedArray[paraStartIndex] = true;
		resultString += paraStartIndex;
		tempQueue.enqueue(new Integer(paraStartIndex));

		int tempIndex;
		Integer tempInteger = (Integer) tempQueue.dequeue();
		AdjacencyNode tempNode;
		while (tempInteger != null) {
			tempIndex = tempInteger.intValue();
			tempNode = headers[tempIndex].next;
			while (tempNode != null) {
				if (!tempVisitedArray[tempNode.column]) {
					tempVisitedArray[tempNode.column] = true;
					resultString += tempNode.column;
					tempQueue.enqueue(new Integer(tempNode.column));
				} // Of if
				tempNode = tempNode.next;
			} // Of for i

			tempInteger = (Integer) tempQueue.dequeue();
		} // Of while

		return resultString;
	}// Of breadthFirstTraversal

	public static void breadthFirstTraversalTest() {
		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:\r\n" + tempTable);

		breadthFirstTraversalTest();
	}// Of main

}// Of class AdjacencyList

运行截图：