39.1 拓扑排序是关键路径的一部分。
39.2 关键路径长度, 其实是最远路径长度。
39.3 正向算每个节点的最早开始时间, 逆向算每个节点的最晚开始时间。
代码：
package 日撸Java300行_31_40;
import java.util.Arrays;
/**
* Weighted graph are called nets.
* @time 2022/4/22
* @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 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; 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
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 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 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; 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 disatnce to 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];
}
// 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
/**
*******************
* Critical path. Net validity checks such as lool check not implemented.
* The source should be 0 and the destination should be n-1.
*
* @return The node sequence of the path.
*******************
*/
public boolean[] criticalPath() {
// One more value to save simple computation.
int tempValue;
// Step 1. The in-degree of each node.
int[] tempInDegrees = new int[numNodes];
for (int i = 0; i < numNodes; i++) {
for (int j = 0; j < numNodes; j++) {
if (weightMatrix.getValue(i, j) != -1) {
tempInDegrees[j]++;
} // Of if
} // Of for j
} // Of for i
System.out.println("In-degree of nodes: " + Arrays.toString(tempInDegrees));
// Step 2. Topology sorting.
int[] tempEarliesTimeArray = new int[numNodes];
for (int i = 0; i < numNodes; i++) {
// This node cannot be removed.
if (tempInDegrees[i] > 0) {
continue;
} // Of if
System.out.println("Removing " + i);
for (int j = 0; j < numNodes; j++) {
if (weightMatrix.getValue(i, j) != -1) {
tempValue = tempEarliesTimeArray[i] + weightMatrix.getValue(i, j);
if (tempEarliesTimeArray[j] < tempValue) {
tempEarliesTimeArray[j] = tempValue;
} // Of if
tempInDegrees[j]--;
} // Of if
} // Of for j
} // Of for i
System.out.println("Out-degree of nodes: " + Arrays.toString(tempEarliesTimeArray));
// Step 3. The out-degree of each node.
int[] tempOutDegrees = new int[numNodes];
for (int i = 0; i < numNodes; i++) {
for (int j = 0; j < numNodes; j++) {
if (weightMatrix.getValue(i, j) != -1) {
tempOutDegrees[i]++;
} // Of if
} // Of for j
} // Of for i
System.out.println("Out-degree of nodes: " + Arrays.toString(tempOutDegrees));
// Step 4. Reverse topology sorting.
int[] tempLatestTimeArray = new int[numNodes];
for (int i = 0; i < numNodes; i++) {
tempLatestTimeArray[i] = tempEarliesTimeArray[numNodes - 1];
} // Of for i
for (int i = 0; i < numNodes; i++) {
// This node cannot be removed.
if (tempOutDegrees[i] > 0) {
continue;
} // Of if
System.out.println("Removing " + i);
for (int j = 0; j < numNodes; j++) {
if (weightMatrix.getValue(j, i) != -1) {
tempValue = tempLatestTimeArray[i] - weightMatrix.getValue(j, i);
if (tempLatestTimeArray[j] > tempValue) {
tempLatestTimeArray[j] = tempValue;
} // Of if
tempOutDegrees[j]--;
System.out.println("The out-degree of " + j + "decreases by 1.");
} // Of if
} // Of for j
} // Of for i
System.out.println("Latest start time: " + Arrays.toString(tempLatestTimeArray));
boolean[] resultCriticalArray = new boolean[numNodes];
for (int i = 0; i < numNodes; i++) {
if (tempEarliesTimeArray[i] == tempLatestTimeArray[i]) {
resultCriticalArray[i] = true;
} // Of if
} // Of for i
System.out.println("Critical array: " + Arrays.toString(resultCriticalArray));
System.out.println("Critical nodes: ");
for (int i = 0; i < numNodes; i++) {
if (resultCriticalArray[i]) {
System.out.println(" " + i);
} // Of if
} // Of for i
System.out.println();
return resultCriticalArray;
} // Of creticalPath
/**
*********************
* 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);
// Dijkstra
tempNet1.dijkstra(1);
// An undirected net is required
int[][] 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();
// A directed net without loop is required.
// Node cannot reach itself. It is indicated by -1.
int[][] tempMatrix3 = { { -1, 3, 2, -1, -1, -1 }, { -1, -1, -1, 2, 3, -1 },
{ -1, -1, -1, 4, -1, 3 }, { -1, -1, -1, -1, -1, 2 }, { -1, -1, -1, -1, -1, 1 },
{ -1, -1, -1, -1, -1, -1 } };
Net tempNet3 = new Net(tempMatrix3);
System.out.println("----------critical path");
tempNet3.criticalPath();
} // Of main
} // Of class Net截图：
41 顺序表
41.1 顺序查找使用岗哨可以节约一半的时间。为此, 第 0 个位置不可以放有意义的数据, 即有效数据只有 length - 1 个。
41.2 顺序查找时间复杂度为 O(n) O(n) O(n)。
41.3 折半查找时间复杂度为 O(log n) O(\log n)O(logn).
代码：
package 日撸Java300行_41_50;
/**
* Data array for searching and sorting algorithms.
* @time 2022/4/23
* @author Hui Xiao
*/
public class DataArray {
/**
* An inner class for data nodes. The test book usually use an int value to
* represent the data. I would like to use a key-value pair instead.
*/
class DataNode {
/**
* The key.
*/
int key;
/**
* The data content.
*/
String content;
/**
*******************
* The first constructor.
*******************
*/
DataNode(int paraKey, String paraContent) {
key = paraKey;
content = paraContent;
} // Of the first constructor
/**
*******************
* Overeides the method claimed in Object, the superclass of any class.
*******************
*/
public String toString() {
return "(" + key + ", " + content + ")";
} // Of toString
} // Of class DataNode
/**
* The data array.
*/
DataNode[] data;
/**
* The length of the data array;
*/
int length;
/**
*******************
* The first constructor.
*
* @param paraKeyArray The array of the keys.
* @param paraContentArray The array of contents.
*******************
*/
public DataArray(int[] paraKeyArray, String[] paraContentArray) {
length = paraKeyArray.length;
data = new DataNode[length];
for (int i = 0; i < length; i++) {
data[i] = new DataNode(paraKeyArray[i], paraContentArray[i]);
} // Of for i
} // Of the first constructor
/**
*******************
* Overeides the method claimed in Object, the superclass of any class.
*******************
*/
public String toString() {
String resultString = "I am a data array with " + length + " items\r\n";
for (int i = 0; i < length; i++) {
resultString += data[i] + " ";
} // Of for i
return resultString;
} // Of toString
/**
*******************
* Sequential search. Attention: It is assume that the index 0 is NOT used.
*
* @param paraKey The given key.
* @return The content of the key.
*******************
*/
public String sequentialSearch(int paraKey) {
data[0].key = paraKey;
int i;
// Note that we do not judge i >= 0 since data[0].key = parakey.
// In this way the runtime is saved about 1/2.
// This for statement is equivalent to
// for (i = length - 1; data[i].key != paraKey; i--);
for (i = length - 1; data[i].key != paraKey; i--) {
;
} // Of for i
return data[i].content;
} // Of sequentialSearch
/**
*******************
* Test the method.
*******************
*/
public static void sequentialSearchTest() {
int[] tempUnsortedKeys = { -1, 5, 3, 6, 10, 7, 1, 9 };
String[] tempContents = { "null", "if", "then", "else", "switch", "case", "for", "while" };
DataArray tempDataArray = new DataArray(tempUnsortedKeys, tempContents);
System.out.println(tempDataArray);
System.out.println("Search result of 10 is: " + tempDataArray.sequentialSearch(10));
System.out.println("Search result of 5 is: " + tempDataArray.sequentialSearch(5));
System.out.println("Search result of 4 is: " + tempDataArray.sequentialSearch(4));
} // Of sequentialSearchTest
/**
*******************
* Binary search. Attention: It is assume that keys are sorted in ascending
* order.
*
* @param paraKey The given key.
* @return The content of the key.
*******************
*/
public String binarySearch(int paraKey) {
int tempLeft = 0;
int tempRight = length - 1;
int tempMiddle = (tempLeft + tempRight) / 2;
while (tempLeft <= tempRight) {
tempMiddle = (tempLeft + tempRight) / 2;
if (data[tempMiddle].key == paraKey) {
return data[tempMiddle].content;
} else if (data[tempMiddle].key <= paraKey){
tempLeft = tempMiddle + 1;
} else {
tempRight = tempMiddle - 1;
} // Of if
} // Of while
// Not found.
return "null";
} // Of binary Search
/**
*******************
* Test the method.
*******************
*/
public static void binarySearchTest() {
int[] tempUnsortedKeys = { 1, 3, 5, 6, 7, 9, 10 };
String[] tempContents = { "if", "then", "else", "switch", "case", "for", "while" };
DataArray tempDataArray = new DataArray(tempUnsortedKeys, tempContents);
System.out.println(tempDataArray);
System.out.println("Search result of 10 is: " + tempDataArray.binarySearch(10));
System.out.println("Search result of 5 is: " + tempDataArray.binarySearch(5));
System.out.println("Search result of 4 is: " + tempDataArray.binarySearch(4));
} // Of binarySearchTest
/**
*********************
* The entrance of the program.
*
* @param args
* Not used now.
*********************
*/
public static void main(String[] args) {
System.out.println("\r\n-------------sequentialSearchTest-------------");
sequentialSearchTest();
System.out.println("\r\n-------------binarySearchTest-------------");
binarySearchTest();
} // Of main
} // Of class DataArray
截图：
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）