学习来源：日撸 Java 三百行（31-40天，图）_闵帆的博客-CSDN博客

33 图的广度优先遍历

33.1与树的广度优先遍历类似。

33.2为每个核心方法写一个测试方法。这叫单元测试。

代码：

/********************** Breadth first traversal.* * @param paraStarIndex The star index.* @return The sequence of the visit.********************/public String breadthFirstTraversal(int paraStartIndex) {CircleObjectQueue tempQueue = new CircleObjectQueue();String resultString = "";int tempNumNodes = connectivityMatrix.getRows();boolean[] tempVisitedArray = new boolean[tempNumNodes];// Initialize the queue.// visit before enqueue.tempVisitedArray[paraStartIndex] = true;resultString += paraStartIndex;tempQueue.enqueue(new Integer(paraStartIndex));// Now visit the rest of the graph.int tempIndex;Integer tempInteger = (Integer)tempQueue.dequeue();while (tempInteger != null) {tempIndex = tempInteger.intValue();//Enqueue all the its unvisited neighbors.for (int i = 0; i < tempNumNodes; i++) {if (tempVisitedArray[i]) {continue; // Already visited.} // Of ifif (connectivityMatrix.getData()[tempIndex][i] == 0) {continue; // Not directly connected.} // Of if// Visit before enqueue.tempVisitedArray[i] = true;resultString += i;tempQueue.enqueue(new Integer(i));} // Of for i//Take out one from the head.tempInteger = (Integer)tempQueue.dequeue();} // Of whilereturn resultString;} // Of breadthFirstTraversal/********************** Unit test for breadthFirstTraversal.********************/public static void breadthFistTraversalTest() {// 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);String tempSequeuece = "";try {tempSequeuece = tempGraph.breadthFirstTraversal(2);} catch (Exception ee) {System.out.println(ee);} // Of trySystem.out.println("The breadth first order of visit: " + tempSequeuece);} // Of breadthFirstTraversalTest/************************ The entrance of the program.* * @param args*            Not used now.**********************/public static void main(String[] args) {System.out.println("Hello!");Graph tempGraph = new Graph(3);System.out.println(tempGraph);// Unit test.getConnectivityTest();breadthFistTraversalTest();} // Of main
} // Of class Graph

截图：

 

34 图的深度优先遍历

34.1 与二叉树的深度优先遍历类似。

34.2 while (true)，循环的退出条件是栈为空。

代码：

    /********************** Depth first traversal.* * @param paraStartIndex The start index.* @return The sequenen of visit.********************/public String depthFirstTraversal(int paraStartIndex) {ObjectStack tempStack = new ObjectStack();String resultString = "";int tempNumNodes = connectivityMatrix.getRows();boolean[] tempVisitedArray = new boolean[tempNumNodes];// Initialize the stack.// Visit before push.tempVisitedArray[paraStartIndex] = true;resultString += paraStartIndex;tempStack.push(new Integer(paraStartIndex));System.out.println("Push " + paraStartIndex);System.out.println("Visited " + resultString);// Now visit the rest of graph.int tempIndex = paraStartIndex;int tempNext;Integer tempInteger;while (true) {// Find an unvisited neighbor.tempNext = -1;for (int i = 0; i < tempNumNodes; i++) {if (tempVisitedArray[i]) {continue; // Aleady visited.} // Of ifif (connectivityMatrix.getData()[tempIndex][i] == 0) {continue; // Not directly connected.} // Of if// Visit this one.tempVisitedArray[i] = true;resultString += i;tempStack.push(new Integer(i));System.out.println("Push " + i);tempNext = i;// One is enough.break;} // Of for iif (tempNext == -1) {// No unvisited neighbor. Backtracking to the last stored in the stack.// Attention: This is the terminate condition!if (tempStack.isEmpty()) {break;} // Of iftempInteger = (Integer)tempStack.pop();System.out.println("Pop " + tempInteger);tempIndex = tempInteger.intValue();} else {tempIndex = tempNext;} // Of if} // Of whilereturn resultString;} // Of depthFirstTraversal/********************** Unit test for depthFirstTraversal.********************/public static void depthFirstTraversalTest() {// Test an undirected graph.int[][] tempMatrix = { { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 0}, { 0, 1, 0, 0 } };Graph tempGraph = new Graph(tempMatrix);System.out.println(tempGraph);String tempSequeue = "";try {tempSequeue = tempGraph.depthFirstTraversal(0);} catch (Exception ee) {System.out.println(ee);} // Of try.System.out.println("The depth first order of visit: " + tempSequeue);} // Of depthFirstTraversalTest/************************ The entrance of the program.* * @param args*            Not used now.**********************/public static void main(String[] args) {System.out.println("Hello!");Graph tempGraph = new Graph(3);System.out.println(tempGraph);// Unit test.getConnectivityTest();breadthFistTraversalTest();depthFirstTraversalTest();} // Of main

截图：

 

35 图的m着色问题

35.1 经典的回溯算法。

35.2 调拭时注意 +1, -1 之类的下标控制。

35.3 单独写一个冲突检测方法。

代码：

/********************** 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 paraCurentNumNodes, int[] paraColoring) {for (int i = 0; i < paraCurentNumNodes - 1; i++) {// No direct connection.if (connectivityMatrix.getValue(paraCurentNumNodes - 1, i) == 0) {continue;} // Of ifif (paraColoring[paraCurentNumNodes - 1] == paraColoring[i]) {return true;} // Of if} // Of for ireturn 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(2);tempGraph.coloring(3);} // Of coloringTest/************************ The entrance of the program.* * @param args*            Not used now.**********************/public static void main(String[] args) {System.out.println("Hello!");Graph tempGraph = new Graph(3);System.out.println(tempGraph);// Unit test.getConnectivityTest();breadthFistTraversalTest();depthFirstTraversalTest();coloringTest();} // Of main

截图：