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");
|
}
|
|
|
}
|
