学习来源：日撸 Java 三百行（31-40天，图）_闵帆的博客-CSDN博客
36 邻接表
36.1 相当于图的压缩存储. 每一行数据用一个单链表存储。
36.2 重写了广度优先遍历. 可以发现, 使用队列的机制不变. 仅仅是把其中的 for 循环换成了 while, 避免检查不存在的边. 如果图很稀疏的话, 可以降低时间复杂度。
36.3 深度优先遍历可以当作作业, 这里不写了。
代码：
package 日撸Java300行_31_40;/*** Adjacency list for directed graph.* @time 2022/4/20* @author Hui Xiao*/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 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);//LinktempPreviousNode.next = tempNode;tempPreviousNode = tempNode;} // Of for j} // Of for i} // Of class AdjacenTable/********************** Override 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 whileresultString += "\r\n";} // Of for ireturn resultString;} // Of toString/********************** Breadth first traversal.* * @param paraStartIndex* The start index.* @return The sequeue of the visit.********************/public String breadthFirstTraversal(int paraStartIndex) {CircleObjectQueue tempQueue = new CircleObjectQueue();String resultString = "";boolean[] tempVisitedArray = new boolean[numNodes];tempVisitedArray[paraStartIndex] = true;// Initialize the queque.// 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();AdjacencyNode tempNode;while (tempInteger != null) {tempIndex = tempInteger.intValue();// Enqueue all its unvisited neighbors. The neighbor are linked// already.tempNode = headers[tempIndex].next;while (tempNode != null) {if (!tempVisitedArray[tempNode.column]) {// Viisit before enqueue.tempVisitedArray[tempNode.column] = true;resultString += tempNode.column;tempQueue.enqueue(new Integer(tempNode.column));} // Of iftempNode = tempNode.next;} // Of for i//Take out one from the head.tempInteger = (Integer) tempQueue.dequeue();} // Of whilereturn 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 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
截图：
37 十字链表
37.1 比邻接表难一点点, 毕竟多一个指针域。
37.2 为控制代码量, 只做了建表和 toString。
代码：
package 日撸Java300行_31_40;/*** Orthogonal List for directed graph.* @time 2022/4/20* @author Hui Xiao*/public class OrthogonalList {/*** An inner class for adjacent node.*/class OrthogonalNode {/*** The row index.*/int row;/*** The column index.*/int column;/*** The next out node.*/OrthogonalNode nextOut;/*** The next in node.*/OrthogonalNode nextIn;/********************** The first constructor.* * @param paraRow The row.* @param paraColumn The column.********************/public OrthogonalNode(int paraRow, int paraColumn) {row = paraRow;column = paraColumn;nextOut = null;nextIn = null;} // Of OrthogonalNode}// Of class OrthogonalNode/*** The number of nodes. This member variable may be redundant since it is always* equal to header.length.*/int numNodes;/*** The header for each row.*/OrthogonalNode[] headers;/********************** The first constructor.* * @param paraMatrix The matrix indicating the graph.********************/public OrthogonalList(int[][] paraMatrix) {numNodes = paraMatrix.length;// Step 1. Initialize. The data in the headers are not meaningful.OrthogonalNode tempPreviousNodes,tempNode;headers = new OrthogonalNode[numNodes];// Step 2. Link to its out nodes.for (int i = 0; i < numNodes; i++) {headers[i] = new OrthogonalNode(i, -1);tempPreviousNodes = headers[i];for (int j = 0; j < numNodes; j++) {if (paraMatrix[i][j] == 0) {continue;} // Of if// Create a new node.tempNode = new OrthogonalNode(i, j);// Link.tempPreviousNodes.nextOut = tempNode;tempPreviousNodes = tempNode;} // Of for j} // Of for i// Step 3. Link to its in nodes. This step is harder.OrthogonalNode[] tempColumnNodes = new OrthogonalNode[numNodes];for (int i = 0; i < numNodes; i++) {tempColumnNodes[i] = headers[i];} // Of for ifor (int i = 0; i < numNodes; i++) {tempNode = headers[i].nextOut;while (tempNode != null) {tempColumnNodes[tempNode.column].nextIn = tempNode;tempColumnNodes[tempNode.column] = tempNode;tempNode = tempNode.nextOut;} // Of while} // Of for i} // Of the constructor/********************** Overrides the method claimed in Object, the superclass of any class.********************/public String toString() {String resultString = "Out arcs: ";OrthogonalNode tempNode;for (int i = 0; i < numNodes; i++) {tempNode = headers[i].nextOut;while (tempNode != null) {resultString += " (" + tempNode.row + ", " + tempNode.column + ")";tempNode = tempNode.nextOut;} // Of whileresultString += "\r\n";} // Of for iresultString += "\r\nIn arcs:";for (int i = 0; i < numNodes; i++) {tempNode = headers[i].nextIn;while (tempNode !=null) {resultString += " (" + tempNode.row + ", " + tempNode.column + ")";tempNode = tempNode.nextIn;} // Of whileresultString += "\r\n";} // Of for ireturn resultString;} // Of toString/********************** The entrance of the program.* * @param args Not used now.********************/public static void main(String[] args) {int[][] tempMatrix = { { 0, 1, 0, 0 }, { 0, 0, 0, 1 }, { 1, 0, 0, 0}, { 0, 1, 1, 0 } };OrthogonalList tempList = new OrthogonalList(tempMatrix);System.out.println("The data ars: \r\n" + tempList);} // Of main
} // Of class OrthogonalList
截图：
38 Dijkstra 算法与 Prim 算法
38.1 Dijkstra 算法需要有向图, Prim 算法需要无向图. 代码中也需要更换后者。
38.2 两个算法的结构相同. 不同之处是比较距离的时候, 是用累计的 (Dijkstra) 还是当前边的 (Prim). 建议先写 Dijkstra, 然后拷贝、修改变成 Prim. 到这个阶段, 应该已经具备这样的能力。
代码：
package 日撸Java300行_31_40;import java.util.Arrays;/*** Weighted graph are called nets.* @time 2022/4/6* @author Hui Xiao*/public class Net {/*** The maximal distance. Do not use Integer.MAX_VALUE.*/public static final int MAX_DISTANCE = 10000;/*** The number of nodes.*/int numNodes;/*** The weight matrix. We use int to represent weight for simplisity.*/IntMatrix weightMatrix;/********************** The first constructor.* * @param paraNumNodes* The number of nodes in the graph.********************/public Net(int paraNumNodes) {numNodes = paraNumNodes;weightMatrix = new IntMatrix(numNodes,numNodes);for (int i = 0; i < numNodes; i++) {// For better readability, you may need to write fill() in class// IntMatrix.Arrays.fill(weightMatrix.getData()[i], MAX_DISTANCE);} // Of for i} // Of the first constructor/********************** The second constructor.* * @param paraMatrix* The data matrix.********************/public Net(int[][] paraMatrix) {weightMatrix = new IntMatrix(paraMatrix);numNodes = weightMatrix.getRows();} // Of the second constructor/************************ Overrides the method claimed in Object, the superclass of any class.**********************/public String toString() {String resultString = "This is the weight matrix of the graph.\r\n" + weightMatrix;return resultString;} // Of toString/********************** The Dijkstra algorithm: shortest path from source to all nodes.* * @param paraSource* The source node.* @return The distances to all nodes.********************/public int[] dijkstra(int paraSource) {// Step 1. Initialize.int[] tempDistanceArray = new int[numNodes];for (int i = 0; i < numNodes; i++) {tempDistanceArray[i] = weightMatrix.getValue(paraSource, i);} // Of for iint[] tempParentArray = new int[numNodes];Arrays.fill(tempParentArray, paraSource);// -1 for no parent.tempParentArray[paraSource] = -1;// Visited nodes will not be considered further.boolean[] tempVisitedArray = new boolean[numNodes];tempVisitedArray[paraSource] = true;// Step 2. Main loops.int tempMinDistance;int tempBestNode = -1;for (int i = 0; i < numNodes; i++) {// Step 2.1 Find out the best next node.tempMinDistance = Integer.MAX_VALUE;for (int j = 0; j < numNodes; j++) {// This node is visited.if (tempVisitedArray[j]) {continue;} // Of ifif (tempMinDistance > tempDistanceArray[j]) {tempMinDistance = tempDistanceArray[j];tempBestNode = j;} // Of if} // Of for jtempVisitedArray[tempBestNode] = true;// Step 2.2 Prepare for the next round.for (int j = 0; j < numNodes; j++) {//This node is visited.if (tempVisitedArray[j]) {continue;} // Of ifif (tempMinDistance > tempDistanceArray[j]) {tempMinDistance = tempDistanceArray[j];tempBestNode = j;} // Of if} // Of for jtempVisitedArray[tempBestNode] = true;// Step 2.2 Prepare for the next round.for (int j = 0; j < numNodes; j++) {// This node is visited.if (tempVisitedArray[j]) {continue;} // Of if// This node cannot be reached.if (weightMatrix.getValue(tempBestNode, j) >= MAX_DISTANCE) {continue; } // Of ifif (tempDistanceArray[j] > tempDistanceArray[tempBestNode] + weightMatrix.getValue(tempBestNode, j)) {// Change the distance.tempDistanceArray[j] = tempDistanceArray[tempBestNode]+ weightMatrix.getValue(tempBestNode, j);// Change the parent.tempParentArray[j] = tempBestNode;} // Of if} // Of for j// For testSystem.out.println("The distance to each node: " + Arrays.toString(tempDistanceArray));System.out.println("The parent of each node: " + Arrays.toString(tempParentArray));} // Of for j// Step 3. Output for debug.System.out.println("Finally");System.out.println("The distance to each node: " + Arrays.toString(tempDistanceArray));System.out.println("The parent of each node: " + Arrays.toString(tempParentArray));return tempDistanceArray;} // Of dijksta/********************** The minial spanning tree.* * @return The total cost of the tree.********************/public int prim() {// Step 1. Initialize.// Any node can be the source.int tempSource = 0;int[] tempDistanceArray = new int[numNodes];for (int i = 0; i < numNodes; i++) {tempDistanceArray[i] = weightMatrix.getValue(tempSource, i);} // Of for iint[] tempParentArray = new int[numNodes];Arrays.fill(tempParentArray, tempSource);// -1 for no parent.tempParentArray[tempSource] = -1;// Visited nodes will not be considered further.boolean[] tempVisitedArray = new boolean[numNodes];tempVisitedArray[tempSource] =true;// Step 2. Main loops.int tempMinDistance;int tempBestNode = -1;for (int i = 0; i < numNodes; i++) {// Step 2.1 Find out the best next node.tempMinDistance = Integer.MAX_VALUE;for (int j = 0; j < numNodes; j++) {// This node is visited.if (tempVisitedArray[j]) {continue;} // Of ifif (tempMinDistance > tempDistanceArray[j]) {tempMinDistance = tempDistanceArray[j];tempBestNode = j;} // Of if} // Of for jtempVisitedArray[tempBestNode] = true;// Step 2.2 Prepare for the next round.for (int j = 0; j < numNodes; j++) {// This node is visited.if (tempVisitedArray[j]) {continue;} // Of if// This node cannot be reached.if (weightMatrix.getValue(tempBestNode, j) >= MAX_DISTANCE) {continue;} // Of if//Attention the difference from the Dijkstra algorithm.if (tempDistanceArray[j] > weightMatrix.getValue(tempBestNode, j)) {// Change the distance.tempDistanceArray[j] = weightMatrix.getValue(tempBestNode, j);// Change the parent.tempParentArray[j] = tempBestNode;} // Of if} // Of for j// For testSystem.out.println("The selected disatnce to each node: " + Arrays.toString(tempDistanceArray));System.out.println("The parent of each node: " + Arrays.toString(tempParentArray));} // Of for iint resultCost = 0;for (int i = 0; i < numNodes; i++) {resultCost += tempDistanceArray[i];}// Step 3. Output for debug.System.out.println("Finally");System.out.println("The distance to each node: " + Arrays.toString(tempDistanceArray));System.out.println("The total cost: " + resultCost);return resultCost;} // Of prim/************************ The entrance of the program.* * @param args* Not used now.**********************/public static void main(String[] args) {Net tempNet0 = new Net(3);System.out.println(tempNet0);int[][] tempMatrix1 = { { 0, 9, 3, 6 }, { 5, 0, 2, 4 }, { 3, 2, 0, 1}, { 2, 8, 7, 0 } };Net tempNet1 = new Net(tempMatrix1);System.out.println(tempNet1);// DijkstratempNet1.dijkstra(1);// An undirected net is requiredint[][] tempMatrix2 = { { 0, 7, MAX_DISTANCE, 5, MAX_DISTANCE }, { 7, 0, 8, 9, 7 },{ MAX_DISTANCE, 8, 0, MAX_DISTANCE, 5 }, { 5, 9, MAX_DISTANCE, 0, 15 },{ MAX_DISTANCE, 7, 5, 15, 0 } };Net tempNet2 = new Net(tempMatrix2);tempNet2.prim();} // Of main} // Of class Net截图：
