代码来自闵老师”日撸 Java 三百行(31-40天)“,链接:https://blog.csdn.net/minfanphd/article/details/116975772
今天深度优先遍历自己没有写,最近几天感觉继续新的知识学习难度有点儿大。等学完这个小结(40天),要留两天时间好好消化一下前面学习的东西。现在理解新内容的代码越来越吃力,并且感觉之前学习的内容掌握的也不牢固,需要巩固巩固了。
package datastructure.graph;
import datastructure.queue.*;
public class AdjacencyList {
class AdjacencyNode{
/**
* The column index.
*/
int column;
/**
* The next adjacent node.
*/
AdjacencyNode next;
/**
* The first constructor of AdjacencyNode
*/
public AdjacencyNode(int paraColumn) {
// TODO Auto-generated constructor stub
column = paraColumn;
next = null;
}//The first constructor of AdjacencyNode
}//of AdjacencyNode
/**
* The number of nodes. This member variable may be redundant
* since it is always equal to headers.length.
*/
int numNodes;
/**
* The header for each row.
*/
AdjacencyNode[] headers;
/**
* *************************************************************
* The first constructor of AdjacencyList.
* @param paraMatrix The matrix indicating the graph.
* *************************************************************
*/
public AdjacencyList(int[][] paraMatrix) {
// TODO Auto-generated constructor stub
numNodes = paraMatrix.length;
headers = new AdjacencyNode[numNodes];
AdjacencyNode tempNode, tempPreviousNode;
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
}//The first constructor of AdjacencyList.
/**
* *********************************************************************
* Overrides the method claimed in Object, the superclass of any class.
* *********************************************************************
*/
public String toString() {
String resultString = "";
AdjacencyNode tempNode;
for (int i = 0; i < headers.length; 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) {
//Declare variables.
String resultString = "";
CircleObjectQueue tempQueue = new CircleObjectQueue();
boolean[] tempVisitArrays = new boolean[numNodes];
//Initialize the queue.
tempVisitArrays[paraStartIndex] = true;
resultString += (paraStartIndex + ", ");
tempQueue.enqueue((Integer) paraStartIndex);
int tempIndex;
Integer tempInteger = (Integer) tempQueue.dequeue();
while (tempInteger != null) {
AdjacencyNode tempNode = headers[tempInteger].next;
tempIndex = tempInteger.intValue();
while (tempNode != null) {
if (!tempVisitArrays[tempNode.column]) {
tempQueue.enqueue((Integer) tempNode.column);
resultString += (tempNode.column + ", ");
tempVisitArrays[tempNode.column] = true;
}//of if
tempNode = tempNode.next;
}//of while
// 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);
String tempSequence = "";
try {
tempSequence = tempGraph.breadthFirstTraversal(2);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e);
}//of try
System.out.println("The breadth first order of visit: " + tempSequence);
}//of breadthFirstTraversalTest
/**
* *********************************************************************
* The entrance of 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