Java数据结构——关键路径_java 关键路径

一、更新ALGraph

（一）、Java代码

package graph;

/**
 * 邻接表
 * 
 * Adjacency List Graph
 * 
 * @author 己千之
 * @time 2022/2/16(周三)
 */
public class ALGraph {
   
	
	/**
	 * @vexs
	 * 顶点数组
	 */
	public VexNode[] vexs;
	
	/**
	 * @arcs 
	 * 边数组 
	 */
	ArcNode[] arcs;
	
	
	/**
	 * 顶点,边个数
	 */
	int vexNum, arcNum;

	/**
	 * 边的信息结点，如权值
	 */
	static class Info {
   
		String value;
		int weight;

		public Info(String value) {
   
			this.value = value;
		}

		public Info(int weight) {
   
			this.weight = weight;
		}

		public Info(String value, int weight) {
   
			this.value = value;
			this.weight = weight;
		}
		
		public String toString() {
   
			return this.value + "=" + this.weight;
		}
	}
	
	/**
	 * 弧结点，表结点
	 */
	class ArcNode {
   
		int index;
		Info info; // 把int改为String
		ArcNode nextNode;
	}

	/**
	 * 顶点，表头结点
	 */
	class VexNode {
   
		String data;
		ArcNode firstArc;
	}

	/**
	 * 边关系
	 * 
	 * @static:测试方法中，用到了Edge数组 Edge是个内部类，你要用，只能： 1.把Edge作为参数，可以用 2.把Edge设为静态调用
	 */
	static class Edge {
   
		String start;
		String end;
		Info info;

		public Edge(String start, String end, Info info) {
   
			this.start = start;
			this.end = end;
			this.info = new Info(info.value, info.weight);
		}
	}

	/**
	 * 构造方法，构造有向图
	 * 
	 * @param vertex
	 * @param edge
	 */
	public ALGraph(String[] vertexs, Edge[] edges) {
   
		// TODO
		// 1.设置成员变量大小
		vexs = new VexNode[vertexs.length];
		arcs = new ArcNode[edges.length];
		vexNum = vertexs.length;
		arcNum = edges.length;

		// 2.初始化数组
		for (int i = 0; i < vexs.length; i++) {
   
			vexs[i] = new VexNode();
			vexs[i].data = vertexs[i];
			vexs[i].firstArc = null;
		}

		// 3.链接
		for (int i = 0; i < edges.length; i++) {
   

			// 3.1 由new Edge('A', 'B', 10)来链接
			String start = edges[i].start;
			String end = edges[i].end;
			int indexOfStart = indexOfVex(start);
			int indexOfEnd = indexOfVex(end);

			// 3.2 构造一个新的arcNode类型的结点
			ArcNode arcNode = new ArcNode();
			
			// one: index
			arcNode.index = indexOfEnd;
			
			// two: info
			arcNode.info = edges[i].info; // TODO ？

			// three: nextNode
			linkedLast(indexOfStart, arcNode); // 尾插法，有向，不是无向
			
			// 3.3 更新arcs
			arcs[i] = arcNode;
		}
	} // stucture

	/**
	 * 获取顶点元素位置
	 * 
	 * @param v
	 * @return
	 */
	public int indexOfVex(String v) {
   
		// 定位顶点的位置

		for (int i = 0; i < vexs.length; i++) {
   
			if (vexs[i].data == v)
				return i;
		}
		return -1;
	} // indexOfVex

	/**
	 * 尾插法，将新元素插在链表尾部
	 * 
	 * @param index
	 * @param node
	 */
	public void linkedLast(int indexofstart, ArcNode arcnode) {
   
		if (vexs[indexofstart].firstArc == null) {
   

			// 关键代码
			vexs[indexofstart].firstArc = arcnode;
		} else {
   
			ArcNode tempNode = vexs[indexofstart].firstArc;
			while (tempNode.nextNode != null) {
   
				tempNode = tempNode.nextNode;
			}

			// 关键代码
			tempNode.nextNode = arcnode;
		}
	} // linkedLast

	/**
	 * 像邻接表一样打印
	 */
	public void printALGraphByChar() {
   
		System.out.println("邻接表存储的图：");
		for (int i = 0; i < vexs.length; i++) {
   

			// 1.打印顶点
			System.out.print(vexs[i].data + "----->");

			// 2.打印挂接链表
			if (vexs[i].firstArc != null) {
   

				// 2.1 firstArc
				ArcNode tempNode = vexs[i].firstArc;

				// 2.2 nextArc
				while (tempNode.nextNode != null) {
   
					System.out.print(vexs[tempNode.index].data + "--->");
					tempNode = tempNode.nextNode;
				}

				// 2.2 tempNode.nextNode = null
				System.out.print(vexs[tempNode.index].data);
			} else {
   
				System.out.print("NULL");
			}

			// 3. 换行
			System.out.println();
		}
	} // printALGraph

	pu
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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231