• 数据结构与算法(java版)第二季 - 7 图 BFS DFS 拓扑排序

    图(Graph)

    ◼ 图由 顶点 （vertex）和 边 （edge）组成，通常表示为 G = (V, E)
    G表示一个图，V是顶点集，E是边集
    顶点集V有穷且非空
    任意两个顶点之间都可以用边来表示它们之间的关系，边集E可以是空的

    有向图（Directed Graph）

    有向图的边是有明确方向的

    有向无环图（Directed Acyclic Graph，简称 DAG）

    如果一个有向图，从任意顶点出发无法经过若干条边回到该顶点，那么它就是一个有向无环图

    出度、入度 

    ◼ 出度（Out-degree）
    一个顶点的出度为 x，是指有 x 条边以该顶点为起点
    顶点11的出度是3
    ◼ 入度（In-degree）
    一个顶点的入度为 x，是指有 x 条边以该顶点为终点
    顶点11的入度是2

     无向图（Undirected Graph）

     混合图（Mixed Graph）

     简单图、多重图

    ◼ 平行边
    在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边
    在有向图中，关联一对顶点的有向边如果多于1条，并且它们的的方向相同，则称这些边为平行边
    ◼ 多重图（Multigraph）
    有平行边或者有自环的图
    ◼ 简单图（Simple Graph）
    既没有平行边也不没有自环的图
    课程中讨论的基本都是简单图

     无向完全图

    ◼ 无向完全图的任意两个顶点之间都存在边
    n 个顶点的无向完全图有 n(n − 1)/2 条边
    ✓ n − 1 + n − 2 + n − 3 + ⋯ + 3 + 2 + 1

    有向完全图（Directed Complete Graph）

    ◼ 有向完全图的任意两个顶点之间都存在方向相反的两条边
    n 个顶点的有向完全图有 n(n − 1) 条边

    ◼ 稠密图（Dense Graph）：边数接近于或等于完全图
    ◼ 稀疏图（Sparse Graph）：边数远远少于完全图

    有权图（Weighted Graph）

    有权图的边可以拥有权值（Weight)

     连通图（Connected Graph）

     如果顶点 x 和 y 之间存在可相互抵达的路径（直接或间接的路径），则称 x 和 y 是连通的

    连通分量（Connected Component）

    ◼ 连通分量：无向图的极大连通子图
    连通图只有一个连通分量，即其自身；非连通的无向图有多个连通分量
    ◼ 下面的无向图有3个连通分量

    强连通图（Strongly Connected Graph）

     如果有向图 G 中任意2个顶点都是连通的，则称G为强连通图

    强连通分量（Strongly Connected Component）

    ◼ 强连通分量：有向图的极大强连通子图
    强连通图只有一个强连通分量，即其自身；非强连通的有向图有多个强连通分量

     上面的图了解,过一遍就是可以的,去干饭干饭.

    图的实现方案

    ◼ 图有2种常见的实现方案
    邻接矩阵（Adjacency Matrix）
    邻接表（Adjacency List）

    邻接矩阵（Adjacency Matrix）

    ◼ 邻接矩阵的存储方式
    一维数组存放顶点信息
    二维数组存放边信息
    ◼ 邻接矩阵比较适合稠密图
    不然会比较浪费内存

     通过上面的图可以知道,它是关于对角线对称的.

    邻接矩阵 – 有权图

     邻接表（Adjacency List）

     

    邻接表 – 有权图 

     上面的概念真是乱的很,下面开始写代码了.

     抽象类:

    1. package com.mj.graph;
    2.  
    3. import java.util.LinkedList;
    4. import java.util.List;
    5. import java.util.Map;
    6. import java.util.Set;
    7.  
    8. public abstract class Graph {
    9. 	protected WeightManager weightManager;
    10. 	
    11. 	public Graph() {}
    12. 	
    13. 	public Graph(WeightManager weightManager) {
    14. 		this.weightManager = weightManager;
    15. 	}
    16. 	
    17. 	public abstract int edgesSize();
    18. 	public abstract int verticesSize();
    19. 	
    20. 	public abstract void addVertex(V v);//顶点
    21. 	public abstract void addEdge(V from, V to);//边
    22. 	public abstract void addEdge(V from, V to, E weight);//权重
    23. 	
    24. 	public abstract void removeVertex(V v);
    25. 	public abstract void removeEdge(V from, V to);
    26. 	
    27. 	public abstract void bfs(V begin, VertexVisitor visitor);
    28. 	public abstract void dfs(V begin, VertexVisitor visitor);
    29. 	
    30. 	public abstract Set> mst();
    31. 	
    32. 	public abstract List topologicalSort();
    33. 	
    34. //	public abstract Map shortestPath(V begin);
    35. 	public abstract Map> shortestPath(V begin);
    36. 	
    37. 	public abstract Map>> shortestPath();
    38. 	
    39. 	public interface WeightManager {
    40. 		int compare(E w1, E w2);
    41. 		E add(E w1, E w2);
    42. 		E zero();
    43. 	}
    44. 	
    45. 	public interface VertexVisitor {
    46. 		boolean visit(V v);
    47. 	}
    48. 	
    49. 	public static class PathInfo {
    50. 		protected E weight;
    51. 		protected List> edgeInfos = new LinkedList<>();
    52. 		public PathInfo() {}
    53. 		public PathInfo(E weight) {
    54. 			this.weight = weight;
    55. 		}
    56. 		public E getWeight() {
    57. 			return weight;
    58. 		}
    59. 		public void setWeight(E weight) {
    60. 			this.weight = weight;
    61. 		}
    62. 		public List> getEdgeInfos() {
    63. 			return edgeInfos;
    64. 		}
    65. 		public void setEdgeInfos(List> edgeInfos) {
    66. 			this.edgeInfos = edgeInfos;
    67. 		}
    68. 		@Override
    69. 		public String toString() {
    70. 			return "PathInfo [weight=" + weight + ", edgeInfos=" + edgeInfos + "]";
    71. 		}
    72. 	}
    73.  
    74. 	//定义的边
    75. 	public static class EdgeInfo {
    76. 		private V from;//起始
    77. 		private V to;//终止
    78. 		private E weight;//权值
    79. 		public EdgeInfo(V from, V to, E weight) {
    80. 			this.from = from;
    81. 			this.to = to;
    82. 			this.weight = weight;
    83. 		}
    84. 		public V getFrom() {
    85. 			return from;
    86. 		}
    87. 		public void setFrom(V from) {
    88. 			this.from = from;
    89. 		}
    90. 		public V getTo() {
    91. 			return to;
    92. 		}
    93. 		public void setTo(V to) {
    94. 			this.to = to;
    95. 		}
    96. 		public E getWeight() {
    97. 			return weight;
    98. 		}
    99. 		public void setWeight(E weight) {
    100. 			this.weight = weight;
    101. 		}
    102. 		@Override
    103. 		public String toString() {
    104. 			return "EdgeInfo [from=" + from + ", to=" + to + ", weight=" + weight + "]";
    105. 		}
    106. 	}
    107. }

    实现类:

    1. package com.mj.graph;
    2.  
    3. import java.util.ArrayList;
    4. import java.util.Comparator;
    5. import java.util.HashMap;
    6. import java.util.HashSet;
    7. import java.util.Iterator;
    8. import java.util.LinkedList;
    9. import java.util.List;
    10. import java.util.Map;
    11. import java.util.Map.Entry;
    12. import java.util.Objects;
    13. import java.util.Queue;
    14. import java.util.Set;
    15. import java.util.Stack;
    16.  
    17. import com.mj.MinHeap;
    18. import com.mj.UnionFind;
    19.  
    20. @SuppressWarnings("unchecked")
    21. public class ListGraph extends Graph {
    22. 	public ListGraph() {}
    23. 	public ListGraph(WeightManager weightManager) {
    24. 		super(weightManager);
    25. 	}
    26.  
    27. 	private static class Vertex {
    28. 		V value;
    29. 		Set> inEdges = new HashSet<>();
    30. 		Set> outEdges = new HashSet<>();
    31. 		Vertex(V value) {
    32. 			this.value = value;
    33. 		}
    34. 		@Override
    35. 		public boolean equals(Object obj) {
    36. 			return Objects.equals(value, ((Vertex)obj).value);
    37. 		}
    38. 		@Override
    39. 		public int hashCode() {
    40. 			return value == null ? 0 : value.hashCode();
    41. 		}
    42. 		@Override
    43. 		public String toString() {
    44. 			return value == null ? "null" : value.toString();
    45. 		}
    46. 	}
    47. 	
    48. 	private static class Edge {
    49. 		Vertex from;
    50. 		Vertex to;
    51. 		E weight;
    52. 		
    53. 		Edge(Vertex from, Vertex to) {
    54. 			this.from = from;
    55. 			this.to = to;
    56. 		}
    57. 		
    58. 		EdgeInfo info() {
    59. 			return new EdgeInfo<>(from.value, to.value, weight);
    60. 		}
    61. 		
    62. 		@Override
    63. 		public boolean equals(Object obj) {
    64. 			Edge edge = (Edge) obj;
    65. 			return Objects.equals(from, edge.from) && Objects.equals(to, edge.to);
    66. 		}
    67. 		@Override
    68. 		public int hashCode() {
    69. 			return from.hashCode() * 31 + to.hashCode();
    70. 		}
    71.  
    72. 		@Override
    73. 		public String toString() {
    74. 			return "Edge [from=" + from + ", to=" + to + ", weight=" + weight + "]";
    75. 		}
    76. 	}
    77. 	
    78. 	private Map> vertices = new HashMap<>();
    79. 	private Set> edges = new HashSet<>();
    80. 	private Comparator> edgeComparator = (Edge e1, Edge e2) -> {
    81. 		return weightManager.compare(e1.weight, e2.weight);
    82. 	};
    83. 	
    84. 	public void print() {
    85. 		System.out.println("[顶点]-------------------");
    86. 		vertices.forEach((V v, Vertex vertex) -> {
    87. 			System.out.println(v);
    88. 			System.out.println("out-----------");
    89. 			System.out.println(vertex.outEdges);
    90. 			System.out.println("in-----------");
    91. 			System.out.println(vertex.inEdges);
    92. 		});
    93.  
    94. 		System.out.println("[边]-------------------");
    95. 		edges.forEach((Edge edge) -> {
    96. 			System.out.println(edge);
    97. 		});
    98. 	}
    99.  
    100. 	@Override
    101. 	public int edgesSize() {
    102. 		return edges.size();
    103. 	}
    104.  
    105. 	@Override
    106. 	public int verticesSize() {
    107. 		return vertices.size();
    108. 	}
    109.  
    110. 	@Override
    111. 	public void addVertex(V v) {
    112. 		if (vertices.containsKey(v)) return;
    113. 		vertices.put(v, new Vertex<>(v));
    114. 	}
    115.  
    116. 	@Override
    117. 	public void addEdge(V from, V to) {
    118. 		addEdge(from, to, null);
    119. 	}
    120.  
    121. 	@Override
    122. 	public void addEdge(V from, V to, E weight) {
    123. 		Vertex fromVertex = vertices.get(from);
    124. 		if (fromVertex == null) {
    125. 			fromVertex = new Vertex<>(from);
    126. 			vertices.put(from, fromVertex);
    127. 		}
    128. 		
    129. 		Vertex toVertex = vertices.get(to);
    130. 		if (toVertex == null) {
    131. 			toVertex = new Vertex<>(to);
    132. 			vertices.put(to, toVertex);
    133. 		}
    134.  
    135. 		Edge edge = new Edge<>(fromVertex, toVertex);
    136. 		edge.weight = weight;
    137. 		if (fromVertex.outEdges.remove(edge)) {
    138. 			toVertex.inEdges.remove(edge);
    139. 			edges.remove(edge);
    140. 		}
    141. 		fromVertex.outEdges.add(edge);
    142. 		toVertex.inEdges.add(edge);
    143. 		edges.add(edge);
    144. 	}
    145.  
    146. 	@Override
    147. 	public void removeEdge(V from, V to) {
    148. 		Vertex fromVertex = vertices.get(from);
    149. 		if (fromVertex == null) return;
    150. 		
    151. 		Vertex toVertex = vertices.get(to);
    152. 		if (toVertex == null) return;
    153. 		
    154. 		Edge edge = new Edge<>(fromVertex, toVertex);
    155. 		if (fromVertex.outEdges.remove(edge)) {
    156. 			toVertex.inEdges.remove(edge);
    157. 			edges.remove(edge);
    158. 		}
    159. 	}
    160.  
    161. 	@Override
    162. 	public void removeVertex(V v) {
    163. 		Vertex vertex = vertices.remove(v);
    164. 		if (vertex == null) return;
    165.  
    166. 		for (Iterator> iterator = vertex.outEdges.iterator(); iterator.hasNext();) {
    167. 			Edge edge = iterator.next();
    168. 			edge.to.inEdges.remove(edge);
    169. 			// 将当前遍历到的元素edge从集合vertex.outEdges中删掉
    170. 			iterator.remove(); 
    171. 			edges.remove(edge);
    172. 		}
    173.  
    174. 		for (Iterator> iterator = vertex.inEdges.iterator(); iterator.hasNext();) {
    175. 			Edge edge = iterator.next();
    176. 			edge.from.outEdges.remove(edge);
    177. 			// 将当前遍历到的元素edge从集合vertex.inEdges中删掉
    178. 			iterator.remove(); 
    179. 			edges.remove(edge);
    180. 		}
    181. 	}
    182.  
    183. 	@Override
    184. 	public void bfs(V begin, VertexVisitor visitor) {
    185. 		if (visitor == null) return;
    186. 		Vertex beginVertex = vertices.get(begin);
    187. 		if (beginVertex == null) return;
    188. 		
    189. 		Set> visitedVertices = new HashSet<>();
    190. 		Queue> queue = new LinkedList<>();
    191. 		queue.offer(beginVertex);
    192. 		visitedVertices.add(beginVertex);
    193. 		
    194. 		while (!queue.isEmpty()) {
    195. 			Vertex vertex = queue.poll();
    196. 			if (visitor.visit(vertex.value)) return;
    197. 			
    198. 			for (Edge edge : vertex.outEdges) {
    199. 				if (visitedVertices.contains(edge.to)) continue;
    200. 				queue.offer(edge.to);
    201. 				visitedVertices.add(edge.to);
    202. 			}
    203. 		}
    204. 	}
    205.  
    206. 	@Override
    207. 	public void dfs(V begin, VertexVisitor visitor) {
    208. 		if (visitor == null) return;
    209. 		Vertex beginVertex = vertices.get(begin);
    210. 		if (beginVertex == null) return;
    211.  
    212. 		Set> visitedVertices = new HashSet<>();
    213. 		Stack> stack = new Stack<>();
    214. 		
    215. 		// 先访问起点
    216. 		stack.push(beginVertex);
    217. 		visitedVertices.add(beginVertex);
    218. 		if (visitor.visit(begin)) return;
    219. 		
    220. 		while (!stack.isEmpty()) {
    221. 			Vertex vertex = stack.pop();
    222. 			
    223. 			for (Edge edge : vertex.outEdges) {
    224. 				if (visitedVertices.contains(edge.to)) continue;
    225. 				
    226. 				stack.push(edge.from);
    227. 				stack.push(edge.to);
    228. 				visitedVertices.add(edge.to);
    229. 				if (visitor.visit(edge.to.value)) return;
    230. 				
    231. 				break;
    232. 			}
    233. 		}
    234. 	}
    235.  
    236. 	@Override
    237. 	public List topologicalSort() {
    238. 		List list = new ArrayList<>();
    239. 		Queue> queue = new LinkedList<>();
    240. 		Map, Integer> ins = new HashMap<>();
    241. 		// 初始化（将度为0的节点都放入队列）
    242. 		vertices.forEach((V v, Vertex vertex) -> {
    243. 			int in = vertex.inEdges.size();
    244. 			if (in == 0) {
    245. 				queue.offer(vertex);
    246. 			} else {
    247. 				ins.put(vertex, in);
    248. 			}
    249. 		});
    250. 		
    251. 		while (!queue.isEmpty()) {
    252. 			Vertex vertex = queue.poll();
    253. 			// 放入返回结果中
    254. 			list.add(vertex.value);
    255. 			
    256. 			for (Edge edge : vertex.outEdges) {
    257. 				int toIn = ins.get(edge.to) - 1;
    258. 				if (toIn == 0) {
    259. 					queue.offer(edge.to);
    260. 				} else {
    261. 					ins.put(edge.to, toIn);
    262. 				}
    263. 			}
    264. 		}
    265. 		
    266. 		return list;
    267. 	}
    268.  
    269. 	@Override
    270. 	public Set> mst() {
    271. 		return Math.random() > 0.5 ? prim() : kruskal();
    272. 	}
    273. 	
    274. 	private Set> prim() {
    275. 		Iterator> it = vertices.values().iterator();
    276. 		if (!it.hasNext()) return null;
    277. 		Vertex vertex = it.next();
    278. 		Set> edgeInfos = new HashSet<>();
    279. 		Set> addedVertices = new HashSet<>();
    280. 		addedVertices.add(vertex);
    281. 		MinHeap> heap = new MinHeap<>(vertex.outEdges, edgeComparator);
    282. 		int verticesSize = vertices.size();
    283. 		while (!heap.isEmpty() && addedVertices.size() < verticesSize) {
    284. 			Edge edge = heap.remove();
    285. 			if (addedVertices.contains(edge.to)) continue;
    286. 			edgeInfos.add(edge.info());
    287. 			addedVertices.add(edge.to);
    288. 			heap.addAll(edge.to.outEdges);
    289. 		}
    290. 		return edgeInfos;
    291. 	}
    292. 	
    293. 	private Set> kruskal() {
    294. 		int edgeSize = vertices.size() - 1;
    295. 		if (edgeSize == -1) return null;
    296. 		Set> edgeInfos = new HashSet<>();
    297. 		MinHeap> heap = new MinHeap<>(edges, edgeComparator);
    298. 		UnionFind> uf = new UnionFind<>();
    299. 		vertices.forEach((V v, Vertex vertex) -> {
    300. 			uf.makeSet(vertex);
    301. 		});
    302. 		while (!heap.isEmpty() && edgeInfos.size() < edgeSize) {
    303. 			Edge edge = heap.remove(); 
    304. 			if (uf.isSame(edge.from, edge.to)) continue; 
    305. 			edgeInfos.add(edge.info());
    306. 			uf.union(edge.from, edge.to);
    307. 		}
    308. 		return edgeInfos;
    309. 	}
    310.  
    311. //	public Map shortestPath(V begin) {
    312. //		Vertex beginVertex = vertices.get(begin);
    313. //		if (beginVertex == null) return null;
    314. //		
    315. //		Map selectedPaths = new HashMap<>();
    316. //		Map, E> paths = new HashMap<>();
    317. //		// 初始化paths
    318. //		for (Edge edge : beginVertex.outEdges) {
    319. //			paths.put(edge.to, edge.weight);
    320. //		}
    321. //
    322. //		while (!paths.isEmpty()) {
    323. //			Entry, E> minEntry = getMinPath(paths);
    324. //			// minVertex离开桌面
    325. //			Vertex minVertex = minEntry.getKey();
    326. //			selectedPaths.put(minVertex.value, minEntry.getValue());
    327. //			paths.remove(minVertex);
    328. //			// 对它的minVertex的outEdges进行松弛操作
    329. //			for (Edge edge : minVertex.outEdges) {
    330. //				// 如果edge.to已经离开桌面，就没必要进行松弛操作
    331. //				if (selectedPaths.containsKey(edge.to.value)) continue;
    332. //				// 新的可选择的最短路径：beginVertex到edge.from的最短路径 + edge.weight
    333. //				E newWeight = weightManager.add(minEntry.getValue(), edge.weight);
    334. //				// 以前的最短路径：beginVertex到edge.to的最短路径
    335. //				E oldWeight = paths.get(edge.to);
    336. //				if (oldWeight == null || weightManager.compare(newWeight, oldWeight) < 0) {
    337. //					paths.put(edge.to, newWeight);
    338. //				}
    339. //			}
    340. //		}
    341. //		
    342. //		selectedPaths.remove(begin);
    343. //		return selectedPaths;
    344. //	}
    345. 	
    346. 	@Override
    347. 	public Map> shortestPath(V begin) {
    348. 		return dijkstra(begin);
    349. 	}
    350.  
    351. 	@SuppressWarnings("unused")
    352. 	private Map> bellmanFord(V begin) {
    353. 		Vertex beginVertex = vertices.get(begin);
    354. 		if (beginVertex == null) return null;
    355. 		
    356. 		Map> selectedPaths = new HashMap<>();
    357. 		selectedPaths.put(begin, new PathInfo<>(weightManager.zero()));
    358. 		
    359. 		int count = vertices.size() - 1;
    360. 		for (int i = 0; i < count; i++) { // v - 1 次
    361. 			for (Edge edge : edges) {
    362. 				PathInfo fromPath = selectedPaths.get(edge.from.value);
    363. 				if (fromPath == null) continue;
    364. 				relax(edge, fromPath, selectedPaths);
    365. 			}
    366. 		}
    367. 		
    368. 		for (Edge edge : edges) {
    369. 			PathInfo fromPath = selectedPaths.get(edge.from.value);
    370. 			if (fromPath == null) continue;
    371. 			if (relax(edge, fromPath, selectedPaths)) {
    372. 				System.out.println("有负权环");
    373. 				return null;
    374. 			}
    375. 		}
    376. 		
    377. 		selectedPaths.remove(begin);
    378. 		return selectedPaths;
    379. 	}
    380.  
    381. 	
    382. 	/**
    383. 	 * 松弛
    384. 	 * @param edge 需要进行松弛的边
    385. 	 * @param fromPath edge的from的最短路径信息
    386. 	 * @param paths 存放着其他点（对于dijkstra来说，就是还没有离开桌面的点）的最短路径信息
    387. 	 */
    388. 	private boolean relax(Edge edge, PathInfo fromPath, Map> paths) {
    389. 		// 新的可选择的最短路径：beginVertex到edge.from的最短路径 + edge.weight
    390. 		E newWeight = weightManager.add(fromPath.weight, edge.weight);
    391. 		// 以前的最短路径：beginVertex到edge.to的最短路径
    392. 		PathInfo oldPath = paths.get(edge.to.value);
    393. 		if (oldPath != null && weightManager.compare(newWeight, oldPath.weight) >= 0) return false;
    394. 		
    395. 		if (oldPath == null) {
    396. 			oldPath = new PathInfo<>();
    397. 			paths.put(edge.to.value, oldPath);
    398. 		} else {
    399. 			oldPath.edgeInfos.clear();
    400. 		}
    401.  
    402. 		oldPath.weight = newWeight;
    403. 		oldPath.edgeInfos.addAll(fromPath.edgeInfos);
    404. 		oldPath.edgeInfos.add(edge.info());
    405. 		
    406. 		return true;
    407. 	}
    408. 	
    409. 	private Map> dijkstra(V begin) {
    410. 		Vertex beginVertex = vertices.get(begin);
    411. 		if (beginVertex == null) return null;
    412. 		
    413. 		Map> selectedPaths = new HashMap<>();
    414. 		Map, PathInfo> paths = new HashMap<>();
    415. 		paths.put(beginVertex, new PathInfo<>(weightManager.zero()));
    416. 		// 初始化paths
    417. //		for (Edge edge : beginVertex.outEdges) {
    418. //			PathInfo path = new PathInfo<>();
    419. //			path.weight = edge.weight;
    420. //			path.edgeInfos.add(edge.info());
    421. //			paths.put(edge.to, path);
    422. //		}
    423.  
    424. 		while (!paths.isEmpty()) {
    425. 			Entry, PathInfo> minEntry = getMinPath(paths);
    426. 			// minVertex离开桌面
    427. 			Vertex minVertex = minEntry.getKey();
    428. 			PathInfo minPath = minEntry.getValue();
    429. 			selectedPaths.put(minVertex.value, minPath);
    430. 			paths.remove(minVertex);
    431. 			// 对它的minVertex的outEdges进行松弛操作
    432. 			for (Edge edge : minVertex.outEdges) {
    433. 				// 如果edge.to已经离开桌面，就没必要进行松弛操作
    434. 				if (selectedPaths.containsKey(edge.to.value)) continue;
    435. 				relaxForDijkstra(edge, minPath, paths);
    436. 			}
    437. 		}
    438. 		
    439. 		selectedPaths.remove(begin);
    440. 		return selectedPaths;
    441. 	}
    442. 	
    443. 	/**
    444. 	 * 松弛
    445. 	 * @param edge 需要进行松弛的边
    446. 	 * @param fromPath edge的from的最短路径信息
    447. 	 * @param paths 存放着其他点（对于dijkstra来说，就是还没有离开桌面的点）的最短路径信息
    448. 	 */
    449. 	private void relaxForDijkstra(Edge edge, PathInfo fromPath, Map, PathInfo> paths) {
    450. 		// 新的可选择的最短路径：beginVertex到edge.from的最短路径 + edge.weight
    451. 		E newWeight = weightManager.add(fromPath.weight, edge.weight);
    452. 		// 以前的最短路径：beginVertex到edge.to的最短路径
    453. 		PathInfo oldPath = paths.get(edge.to);
    454. 		if (oldPath != null && weightManager.compare(newWeight, oldPath.weight) >= 0) return;
    455. 		
    456. 		if (oldPath == null) {
    457. 			oldPath = new PathInfo<>();
    458. 			paths.put(edge.to, oldPath);
    459. 		} else {
    460. 			oldPath.edgeInfos.clear();
    461. 		}
    462.  
    463. 		oldPath.weight = newWeight;
    464. 		oldPath.edgeInfos.addAll(fromPath.edgeInfos);
    465. 		oldPath.edgeInfos.add(edge.info());
    466. 	}
    467. 	
    468. 	/**
    469. 	 * 从paths中挑一个最小的路径出来
    470. 	 * @param paths
    471. 	 * @return
    472. 	 */
    473. 	private Entry, PathInfo> getMinPath(Map, PathInfo> paths) {
    474. 		Iterator, PathInfo>> it = paths.entrySet().iterator();
    475. 		Entry, PathInfo> minEntry = it.next();
    476. 		while (it.hasNext()) {
    477. 			Entry, PathInfo> entry = it.next();
    478. 			if (weightManager.compare(entry.getValue().weight, minEntry.getValue().weight) < 0) {
    479. 				minEntry = entry;
    480. 			}
    481. 		}
    482. 		return minEntry;
    483. 	}
    484. 	
    485. 	@Override
    486. 	public Map>> shortestPath() {
    487. 		Map>> paths = new HashMap<>();
    488. 		// 初始化
    489. 		for (Edge edge : edges) {
    490. 			Map> map = paths.get(edge.from.value);
    491. 			if (map == null) {
    492. 				map = new HashMap<>();
    493. 				paths.put(edge.from.value, map);
    494. 			}
    495. 			
    496. 			PathInfo pathInfo = new PathInfo<>(edge.weight);
    497. 			pathInfo.edgeInfos.add(edge.info());
    498. 			map.put(edge.to.value, pathInfo);
    499. 		}
    500.  
    501. 		vertices.forEach((V v2, Vertex vertex2) -> {
    502. 			vertices.forEach((V v1, Vertex vertex1) -> {
    503. 				vertices.forEach((V v3, Vertex vertex3) -> {
    504. 					if (v1.equals(v2) || v2.equals(v3) || v1.equals(v3)) return;
    505. 					
    506. 					// v1 -> v2
    507. 					PathInfo path12 = getPathInfo(v1, v2, paths);
    508. 					if (path12 == null) return;
    509. 					
    510. 					// v2 -> v3
    511. 					PathInfo path23 = getPathInfo(v2, v3, paths);
    512. 					if (path23 == null) return;
    513. 					
    514. 					// v1 -> v3 
    515. 					PathInfo path13 = getPathInfo(v1, v3, paths);
    516. 					
    517. 					E newWeight = weightManager.add(path12.weight, path23.weight);
    518. 					if (path13 != null && weightManager.compare(newWeight, path13.weight) >= 0) return;
    519. 					
    520. 					if (path13 == null) {
    521. 						path13 = new PathInfo();
    522. 						paths.get(v1).put(v3, path13);
    523. 					} else {
    524. 						path13.edgeInfos.clear();
    525. 					}
    526. 					
    527. 					path13.weight = newWeight;
    528. 					path13.edgeInfos.addAll(path12.edgeInfos);
    529. 					path13.edgeInfos.addAll(path23.edgeInfos);
    530. 				});
    531. 			});
    532. 		});
    533. 		
    534. 		return paths;
    535. 	}
    536. 	
    537. 	private PathInfo getPathInfo(V from, V to, Map>> paths) {
    538. 		Map> map = paths.get(from);
    539. 		return map == null ? null : map.get(to);
    540. 	}
    541.  
    542. //	@Override
    543. //	public void bfs(V begin) {
    544. //		Vertex beginVertex = vertices.get(begin);
    545. //		if (beginVertex == null) return;
    546. //		
    547. //		Set> visitedVertices = new HashSet<>();
    548. //		Queue> queue = new LinkedList<>();
    549. //		queue.offer(beginVertex);
    550. //		visitedVertices.add(beginVertex);
    551. //		
    552. //		while (!queue.isEmpty()) {
    553. //			Vertex vertex = queue.poll();
    554. //			System.out.println(vertex.value);
    555. //			
    556. //			for (Edge edge : vertex.outEdges) {
    557. //				if (visitedVertices.contains(edge.to)) continue;
    558. //				queue.offer(edge.to);
    559. //				visitedVertices.add(edge.to);
    560. //			}
    561. //		}
    562. //	}
    563. //
    564. //	@Override
    565. //	public void dfs(V begin) {
    566. //		Vertex beginVertex = vertices.get(begin);
    567. //		if (beginVertex == null) return;
    568. //
    569. //		Set> visitedVertices = new HashSet<>();
    570. //		Stack> stack = new Stack<>();
    571. //		
    572. //		// 先访问起点
    573. //		stack.push(beginVertex);
    574. //		visitedVertices.add(beginVertex);
    575. //		System.out.println(beginVertex.value);
    576. //		
    577. //		while (!stack.isEmpty()) {
    578. //			Vertex vertex = stack.pop();
    579. //			
    580. //			for (Edge edge : vertex.outEdges) {
    581. //				if (visitedVertices.contains(edge.to)) continue;
    582. //				
    583. //				stack.push(edge.from);
    584. //				stack.push(edge.to);
    585. //				visitedVertices.add(edge.to);
    586. //				System.out.println(edge.to.value);
    587. //				
    588. //				break;
    589. //			}
    590. //		}
    591. //	}
    592. 	
    593. //	public void dfs2(V begin) {
    594. //		Vertex beginVertex = vertices.get(begin);
    595. //		if (beginVertex == null) return;
    596. //		dfs2(beginVertex, new HashSet<>());
    597. //	}
    598. //	
    599. //	private void dfs2(Vertex vertex, Set> visitedVertices) {
    600. //		System.out.println(vertex.value);
    601. //		visitedVertices.add(vertex);
    602. //
    603. //		for (Edge edge : vertex.outEdges) {
    604. //			if (visitedVertices.contains(edge.to)) continue;
    605. //			dfs2(edge.to, visitedVertices);
    606. //		}
    607. //	}
    608. }

  • 相关阅读:
    poi+ResultSet+线程池导出数据库表结构
    Apifox : 不仅是Api调试工具，更是开发团队的协作神器
    sealos爆火后依然要开发sealer，背后原因有哪些？
    Config
    数说故事《汽车行业全场景数字化解决方案》之数字化营销平台搭建
    【浅谈DBA 最重要的素质---读书笔记】
    WPS中样式和编号的关系
    1747. 应该被禁止的 Leetflex 账户
    UE5 ChaosVehicles载具换皮 （连载二）
    测试接触不到第一手需求，如何保证不漏测？
  • 原文地址：https://blog.csdn.net/m0_47489229/article/details/127423605