学习来源：日撸 Java 三百行（31-40天，图）_闵帆的博客-CSDN博客
- 十字链表
- 一、描述
- 二、具体代码
- 三、运行截图
- Dijkstra 算法与 Prim 算法
- 一、Dijkstra算法
- 1. 描述
- 2. 具体代码
- 3. 运行截图
- 二、Prim算法
- 1. 描述
- 2. 具体代码
- 3. 运行截图
- 总结
与邻接表不同, 十字链表法仅适用于存储有向图和有向网. 不仅如此, 十字链表法还改善了邻接表计算图中顶点入度的问题.
十字链表存储有向图的方式与邻接表有一些相同, 都以图中各顶点为首元节点建立多条链表, 同时为了便于管理, 还将所有链表的首元节点存储到同一数组(或链表)中.
归根到底就是弧做为一种节点, 顶点做为另一种节点并以顺序表的形式存储.
用十字链表存储下面的有向图:
存储状态如图所示:
package datastructure.graph;
public class OrthogonalList {
class OrthogonalNode {
int row;
int column;
OrthogonalNode nextOut;
OrthogonalNode nextIn;
public OrthogonalNode(int paraRow, int paraColumn) {
row = paraRow;
column = paraColumn;
nextOut = null;
nextIn = null;
}// Of OrthogonalNode
}// Of class OrthogonalNode
int numNodes;
OrthogonalNode[] headers;
public OrthogonalList(int[][] paraMatrix) {
numNodes = paraMatrix.length;
// Step 1. Initialize. The data in the headers are not meaningful.
OrthogonalNode tempPreviousNode, 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);
tempPreviousNode = 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.
tempPreviousNode.nextOut = tempNode;
tempPreviousNode = 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 i
for (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
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 while
resultString += "rn";
} // Of for i
resultString += "rnIn arcs: ";
for (int i = 0; i < numNodes; i++) {
tempNode = headers[i].nextIn;
while (tempNode != null) {
resultString += " (" + tempNode.row + ", " + tempNode.column + ")";
tempNode = tempNode.nextIn;
} // Of while
resultString += "rn";
} // Of for i
return resultString;
}// Of toString
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 are:rn" + tempList);
}// Of main
} // Of class OrthogonalList
三、运行截图
Dijkstra 算法与 Prim 算法
一、Dijkstra算法
1. 描述
Dijkstra 算法用于构建单源点的最短路径树——即树中某个点到任何其他点的距离都是最短的. 例如, 构建地图应用时查找自己的坐标离某个地标的最短距离. 可以用于有向图, 但是不能存在负权值( Bellman-Ford 可以处理负权值). 与之对应的还有另一种 Floyd 算法.
2. 具体代码
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 i
int[] 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 - 1; 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 if
if (tempMinDistance > tempDistanceArray[j]) {
tempMinDistance = tempDistanceArray[j];
tempBestNode = j;
} // Of if
} // Of for j
tempVisitedArray[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
if (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 test
System.out.println("The distance to each node: " + Arrays.toString(tempDistanceArray));
System.out.println("The parent of each node: " + Arrays.toString(tempParentArray));
} // Of for 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 parent of each node: " + Arrays.toString(tempParentArray));
return tempDistanceArray;
}// Of dijkstra
3. 运行截图
二、Prim算法
1. 描述
Prim算法用于构建最小生成树——即树中所有边的权值之和最小. 例如, 构建电路板, 使所有边的和花费最少. 只能用于无向图. 与之对应的是 Kruskal 算法.
2. 具体代码
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 i
int[] 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 - 1; 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 if
if (tempMinDistance > tempDistanceArray[j]) {
tempMinDistance = tempDistanceArray[j];
tempBestNode = j;
} // Of if
} // Of for j
tempVisitedArray[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 test
System.out.println("The selected distance for each node: " + Arrays.toString(tempDistanceArray));
System.out.println("The parent of each node: " + Arrays.toString(tempParentArray));
} // Of for i
int resultCost = 0;
for (int i = 0; i < numNodes; i++) {
resultCost += tempDistanceArray[i];
} // Of for i
// Step 3. Output for debug.
System.out.println("Finally");
System.out.println("The parent of each node: " + Arrays.toString(tempParentArray));
System.out.println("The total cost: " + resultCost);
return resultCost;
}// Of prim
3. 运行截图
总结
在十字链表中有了多的结构, 虽然使得管理方便但是在第一次理解的过程中存在问题. 所有我们要在两个复杂之间找到一个合适的界限.
无论是 Dijkstra 还是 Prim 算法, 它们都是在一个动态更新的过程中, 要走向未来就要时刻审视当下.
