使用DFS求任意两点的所有路径
2024-10-19 17:30:57
先上代码:
public static void findAllPaths(Integer nodeId,Integer targetNodeId, Map<Integer,ArrayList<Integer>> reachMap) {
for (Integer nextNode : reachMap.get(nodeId)) {
if (nextNode.equals(targetNodeId)) {
Stack temp = new Stack();
for (Integer node1 : connectionPath) {
temp.add(node1);
}
temp.push(demandRouterArray[1]);
temp.add(0, demandRouterArray[0]);
connectionPaths.add(temp);
} else if (!connectionPath.contains(nextNode)) {
connectionPath.push(nextNode);
findAllPaths(nextNode, targetNodeId,reachMap);
connectionPath.pop();
}
}
}
1)reachMap的key是图中一个节点的id,而对应的value是列表形式,存储了这个节点可以直接到达的所有节点。其实,reachMap就是图的邻接表存储形式。
2)搜索得到的一条路径存储在connectionPath中,使用Stack实现:
static Stack<Integer> connectionPath=new Stack();
3)所有的路径存储在connectionPaths中,是以Stack为元素的列表:
static List<Stack> connectionPaths=new ArrayList<>();
最新文章
- Mac git提交步骤小记
- 数据结构与算法JavaScript (二) 队列
- jQuery:年月日三级联动
- 4.3、Libgdx启动类和配置
- (转)Ubuntu 12.04 LTS 构建高可用分布式 MySQL 集群
- SQL Server查询性能优化——堆表、碎片与索引(一)
- 各大Oj平台介绍[转]
- jni使用
- LeetCode_Permutations
- C#中Linq延迟执行问题
- easyui使用总结
- 产品经理学Python:条件控制
- Linux入门(10)——Ubuntu16.04使用pip3和pip安装numpy,scipy,matplotlib等第三方库
- datable中table.row() not a funtion 解决方法
- Android开发:修改eclipse里的Android虚拟机路径
- 深入理解Java虚拟机(类文件结构+类加载机制+字节码执行引擎)
- Http怎么处理长连接
- windows BLE编程 net winform 连接蓝牙4.0
- Assign the task HDU - 3974(dfs序+线段树)
- go 练习