From 030c4ad9573cfc6ecda996a7b59d5e16fbb10a42 Mon Sep 17 00:00:00 2001
From: luxiaotao1123 <t1341870251@163.com>
Date: 星期四, 24 十月 2024 13:54:34 +0800
Subject: [PATCH] #
---
zy-acs-manager/src/main/java/com/zy/acs/manager/core/service/TrafficService.java | 1
zy-acs-manager/src/main/java/com/zy/acs/manager/common/utils/DFS.java | 58 +++++++++++++++++++
zy-acs-manager/src/main/java/com/zy/acs/manager/common/utils/BFS.java | 79 ++++++++++++++++++++++++++
3 files changed, 138 insertions(+), 0 deletions(-)
diff --git a/zy-acs-manager/src/main/java/com/zy/acs/manager/common/utils/BFS.java b/zy-acs-manager/src/main/java/com/zy/acs/manager/common/utils/BFS.java
new file mode 100644
index 0000000..c809f24
--- /dev/null
+++ b/zy-acs-manager/src/main/java/com/zy/acs/manager/common/utils/BFS.java
@@ -0,0 +1,79 @@
+package com.zy.acs.manager.common.utils;
+
+import java.util.*;
+
+/**
+ * Breadth-First Search
+ * 1.鍙敤浜庤绠楁渶鐭矾寰� 鎴栬�� 蹇�熷弽鎺ㄤ簩鍙夋爲鐨勬牴鑺傜偣
+ * https://www.bilibili.com/video/BV1Ks411575U/?vd_source=6f04e61f1b57e41e7986c65388d892fb
+ * 2.濡傛灉杩炴帴鏈夋潈閲嶏紝閭ｄ箞鎶奞ueue鍙樻垚PriorityQueue => Dijkstra
+ * https://www.bilibili.com/video/BV1ts41157Sy/?spm_id_from=333.999.0.0&vd_source=6f04e61f1b57e41e7986c65388d892fb
+ */
+public class BFS {
+
+ private final Map<String, List<String>> graph;
+
+ private final Set<String> visited = new HashSet<>();
+
+ // 鍙互閫氳繃BFS鎵弿鑺傜偣杩炴帴鍏崇郴锛屾潵鑾峰彇鑺傜偣鐨勬渶杩戣矾寰勭殑鐖惰妭鐐筯ash琛�
+ private final Map<String, String> parent = new HashMap<>();
+
+ public BFS(Map<String, List<String>> graph) {
+ this.graph = graph;
+ }
+
+ public List<String> execute(String startNode) {
+ if (null == graph) {
+ throw new RuntimeException("the graph was empty");
+ }
+
+ List<String> list = new ArrayList<>();
+
+ Queue<String> queue = new LinkedList<>();
+
+ queue.add(startNode);
+ visited.add(startNode);
+ parent.put(startNode, null);
+
+ while (queue.size() > 0) {
+ String node = queue.poll();
+
+ List<String> nears = graph.get(node);
+ for (String near : nears) {
+ if (!visited.contains(near)) {
+ queue.offer(near);
+ visited.add(near);
+
+ parent.put(near, node);
+ }
+ }
+
+ list.add(node);
+ }
+
+ return list;
+ }
+
+ public static void main(String[] args) {
+ Map<String, List<String>> graph = new HashMap<>();
+ graph.put("A", new ArrayList<String>(){{add("B");add("C");}});
+ graph.put("B", new ArrayList<String>(){{add("A");add("C");add("D");}});
+ graph.put("C", new ArrayList<String>(){{add("A");add("B");add("D");add("E");}});
+ graph.put("D", new ArrayList<String>(){{add("B");add("C");add("E");add("F");}});
+ graph.put("E", new ArrayList<String>(){{add("C");add("D");}});
+ graph.put("F", new ArrayList<String>(){{add("D");}});
+
+ BFS bfs = new BFS(graph);
+ bfs.execute("E");
+ String endNode = "B";
+ List<String> shortestPath = new ArrayList<>();
+ while (endNode != null) {
+ shortestPath.add(endNode);
+ endNode = bfs.parent.get(endNode);
+ }
+ Collections.reverse(shortestPath);
+
+ System.out.println("shortestPath: " + shortestPath);
+ }
+
+}
diff --git a/zy-acs-manager/src/main/java/com/zy/acs/manager/common/utils/DFS.java b/zy-acs-manager/src/main/java/com/zy/acs/manager/common/utils/DFS.java
new file mode 100644
index 0000000..f6da737
--- /dev/null
+++ b/zy-acs-manager/src/main/java/com/zy/acs/manager/common/utils/DFS.java
@@ -0,0 +1,58 @@
+package com.zy.acs.manager.common.utils;
+
+import java.util.*;
+
+/**
+ * Depth-First Search
+ * https://www.bilibili.com/video/BV1Ks411575U/?vd_source=6f04e61f1b57e41e7986c65388d892fb
+ */
+public class DFS {
+
+ private final Map<String, List<String>> graph;
+
+ private final Set<String> visited = new HashSet<>();
+
+ public DFS(Map<String, List<String>> graph) {
+ this.graph = graph;
+ }
+
+ public void execute(String startNode) {
+ if (null == graph) {
+ throw new RuntimeException("the graph was empty");
+ }
+ Stack<String> stack = new Stack();
+
+ stack.add(startNode);
+ visited.add(startNode);
+
+ while (stack.size() > 0) {
+ String node = stack.pop();
+
+ List<String> nears = graph.get(node);
+ for (String near : nears) {
+ if (!visited.contains(near)) {
+ stack.push(near);
+ visited.add(near);
+ }
+ }
+
+ System.out.println(node);
+ }
+
+ }
+
+ public static void main(String[] args) {
+ Map<String, List<String>> graph = new HashMap<>();
+ graph.put("A", new ArrayList<String>(){{add("B");add("C");}});
+ graph.put("B", new ArrayList<String>(){{add("A");add("C");add("D");}});
+ graph.put("C", new ArrayList<String>(){{add("A");add("B");add("D");add("E");}});
+ graph.put("D", new ArrayList<String>(){{add("B");add("C");add("E");add("F");}});
+ graph.put("E", new ArrayList<String>(){{add("C");add("D");}});
+ graph.put("F", new ArrayList<String>(){{add("D");}});
+
+ DFS bfs = new DFS(graph);
+ bfs.execute("B");
+ }
+
+
+}
diff --git a/zy-acs-manager/src/main/java/com/zy/acs/manager/core/service/TrafficService.java b/zy-acs-manager/src/main/java/com/zy/acs/manager/core/service/TrafficService.java
index f593aa1..7922cee 100644
--- a/zy-acs-manager/src/main/java/com/zy/acs/manager/core/service/TrafficService.java
+++ b/zy-acs-manager/src/main/java/com/zy/acs/manager/core/service/TrafficService.java
@@ -32,6 +32,7 @@
import java.util.List;
/**
+ * Wavefront
* Created by vincent on 6/25/2024
*/
@Slf4j
--
Gitblit v1.9.1