Java学习-Day19

十字链表

一、描述

与邻接表不同, 十字链表法仅适用于存储有向图和有向网. 不仅如此, 十字链表法还改善了邻接表计算图中顶点入度的问题.

十字链表存储有向图的方式与邻接表有一些相同, 都以图中各顶点为首元节点建立多条链表, 同时为了便于管理, 还将所有链表的首元节点存储到同一数组(或链表)中.

归根到底就是弧做为一种节点, 顶点做为另一种节点并以顺序表的形式存储.

用十字链表存储下面的有向图:

存储状态如图所示:

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
package datastructure.graph;

/**
 * Orthogonal List for directed graph.
 * 
 * @author ShiHuai Wen shihuaiwen@outlook.com.
 */
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 headers.length.
	 */
	int numNodes;

	/**
	 * The headers 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 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

	/**
	 *********************
	 * 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 while
			resultString += "\r\n";
		} // Of for i

		resultString += "\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 while
			resultString += "\r\n";
		} // Of for i

		return 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 are:\r\n" + tempList);
	}// Of main
} // Of class OrthogonalList

三、运行截图

Dijkstra 算法与 Prim 算法

一、Dijkstra算法

1. 描述

Dijkstra 算法用于构建单源点的最短路径树——即树中某个点到任何其他点的距离都是最短的. 例如, 构建地图应用时查找自己的坐标离某个地标的最短距离. 可以用于有向图, 但是不能存在负权值( Bellman-Ford 可以处理负权值). 与之对应的还有另一种 Floyd 算法.

2. 具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/**
 *********************
 * The Dijkstra algorithm: shortest path from the 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 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. 具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/**
 *********************
 * The minimal 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 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 算法, 它们都是在一个动态更新的过程中, 要走向未来就要时刻审视当下.