创建网站大约,网站搭建需要多少钱,制作企业网站与app有什么不同,精准软件深度优先遍历#xff08;Depth First Search#xff0c;DFS#xff09;和广度优先遍历#xff08;Breadth First Search#xff0c;BFS#xff09;是图的遍历算法。其中#xff0c;深度优先遍历从某个起始点开始#xff0c;先访问一个节点#xff0c;然后跳到它的一个…深度优先遍历Depth First SearchDFS和广度优先遍历Breadth First SearchBFS是图的遍历算法。其中深度优先遍历从某个起始点开始先访问一个节点然后跳到它的一个相邻节点继续遍历直到没有未遍历的节点此时回溯到上一个节点继续遍历其他的相邻节点。而广度优先遍历则是从某个起始点开始依次遍历该节点的所有相邻节点然后再依次遍历这些相邻节点的相邻节点直到遍历完图中所有节点。
以Spring Boot项目中的REST API接口为例可以通过遍历接口中的URI路径实现DFS和BFS算法。具体实现可以在Spring Boot的控制器类中编写遍历代码如下所示 java // DFS遍历实现
GetMapping(/dfs)
public ListString dfs() {ListString result new ArrayListString();StackString stack new StackString();stack.push(/);while (!stack.empty()) {String path stack.pop();result.add(path);String[] subs getSubPaths(path); // 获取当前路径的子路径for (String sub : subs) {stack.push(sub);}}return result;
}// BFS遍历实现
GetMapping(/bfs)
public ListString bfs() {ListString result new ArrayListString();QueueString queue new LinkedListString();queue.offer(/);while (!queue.isEmpty()) {String path queue.poll();result.add(path);String[] subs getSubPaths(path); // 获取当前路径的子路径for (String sub : subs) {queue.offer(sub);}}return result;
}// 获取路径的子路径
private String[] getSubPaths(String path) {// 从Spring MVC的RequestMappingHandlerMapping中获取当前路径的所有子路径RequestMappingHandlerMapping handlerMapping applicationContext.getBean(RequestMappingHandlerMapping.class);MapRequestMappingInfo, HandlerMethod map handlerMapping.getHandlerMethods();SetString subs new HashSetString();for (RequestMappingInfo info : map.keySet()) {String pattern info.getPatternsCondition().getPatterns().iterator().next();if (pattern.startsWith(path) !pattern.equals(path)) {int index pattern.indexOf(/, path.length() 1);if (index -1) {subs.add(pattern.substring(0, index 1));} else {subs.add(pattern);}}}return subs.toArray(new String[subs.size()]);
}以上代码中getSubPaths()方法使用Spring MVC的RequestMappingHandlerMapping获取所有的REST API接口路径并过滤出当前路径的子路径。DFS遍历使用栈来实现BFS遍历使用队列来实现。当遍历完成后返回遍历得到的路径列表。这样就可以使用REST API接口来演示DFS和BFS算法的实现了。
