无向图中寻找指定路径：深度优先遍历算法

刷题记录

1. 节点依赖

背景: 类似于无向图中, 寻找从 起始节点 --> 目标节点 的 线路.

需求: 现在需要从 起始节点 A, 找到所有到 终点 H 的所有路径

A – B ： 路径由一个对象构成

public class NodeAssociation {private String leftNodeName;private String rightNodeName;
}

A – B 可以是：

{ leftNodeName = A ， rightNodeName = B }或者{ leftNodeName = B ， rightNodeName = A }

找到 A --> E 的所有路径：

以及

找到 A --> D 的所有路径：

【注意】

1. 可能存在 A --B ， B – A 这种干扰项
2. 可能存在 A – A 这种干扰项

【思路】

深度优先遍历算法解决

这个就是一个典型的无向图中求 路径的问题; 从A 开始找到 A的邻接点列表, 然后选择其中一个结点, 再依次选择其下一个结点, 再找到其邻接点列表,再从列表中选择一个访问, 再访问其下一个结点, 直到找到E为止.具体: 
从 A 开始, A 的邻接列表 [B, C, D]
访问 B , B不是目标节点,继续向下~  B 的邻接列表 [E]
访问 E, E是目标, 存储路径 (A-B-E)然后回退到A, 访问 A的邻接列表的第2个节点 C ..... 

具体代码实现

@Data
public class Solution {// 原始数据private List<NodeAssociation> rawData;// 测试public static void main(String[] args) {Solution solution = new Solution();NodeAssociation nodeAssociation1 = new NodeAssociation("A",  "B");NodeAssociation nodeAssociation2 = new NodeAssociation("A",  "C" );NodeAssociation nodeAssociation3 = new NodeAssociation("A",  "D" );NodeAssociation nodeAssociation4 = new NodeAssociation("B",  "E" );NodeAssociation nodeAssociation5 = new NodeAssociation("E",  "C" );NodeAssociation nodeAssociation6 = new NodeAssociation("E",  "H" );NodeAssociation nodeAssociation7 = new NodeAssociation("D",  "F" );NodeAssociation nodeAssociation8 = new NodeAssociation("H",  "F" );NodeAssociation nodeAssociation9 = new NodeAssociation("D",  "A" ); // 干扰项NodeAssociation nodeAssociation10 = new NodeAssociation("C",  "F" );ArrayList<NodeAssociation> list = new ArrayList<>();list.add(nodeAssociation1);list.add(nodeAssociation2);list.add(nodeAssociation3);list.add(nodeAssociation4);list.add(nodeAssociation5);list.add(nodeAssociation6);list.add(nodeAssociation7);list.add(nodeAssociation8);list.add(nodeAssociation9);list.add(nodeAssociation10);solution.setRawData(list);System.out.println("打印原始数据");for (NodeAssociation rawDatum : solution.rawData) {System.out.println(rawDatum);}solution.find("A", "E", "D");}public void find(String rootNodeName, String target1, String target2) {// 1. 对模型对去重 (A-B) (B-A) --> (A-B);  (A-A)无效节点直接删除List<String> tempList = new ArrayList<>();for (int i = rawData.size() - 1; i >= 0; i--) {NodeAssociation nodeAssociation = rawData.get(i);String leftNodeName = nodeAssociation.getLeftNodeName();String rightNodeName = nodeAssociation.getRightNodeName();// 若有重复,则去重 (A-B) (B-A) --> (A-B)if (tempList.contains(leftNodeName + rightNodeName) || tempList.contains(rightNodeName + leftNodeName)) {rawData.remove(i);continue;}// (A-A) 直接删除if (leftNodeName.equals(rightNodeName)){rawData.remove(i);continue;}tempList.add(leftNodeName + rightNodeName);}// 2. 从索引模型开始遍历List<String> roadList = new ArrayList<>();roadList.add(rootNodeName);List<NodeAssociation> roadNodeList = new ArrayList<>();// 2.1 找到 target1List<List<NodeAssociation>> result1 = new ArrayList<>();dfs(result1, roadList, roadNodeList, rootNodeName, target1);System.out.println("打印  "+rootNodeName+"  -->  "+target1+"结果集:" );for (int i = 0; i < result1.size(); i++) {System.out.println("打印第"+(i+1)+"条路:");for (NodeAssociation nodeAssociation : result1.get(i)) {System.out.println(nodeAssociation);}}// 2.2 找到 target2List<List<NodeAssociation>> result2 = new ArrayList<>();dfs(result2, roadList, roadNodeList, rootNodeName, target2);System.out.println("打印  "+rootNodeName+"  -->  "+target2+"结果集:" );for (int i = 0; i < result2.size(); i++) {System.out.println("打印第"+(i+1)+"条路:");for (NodeAssociation nodeAssociation : result2.get(i)) {System.out.println(nodeAssociation);}}}// 1. 当前走过的路public void dfs(List<List<NodeAssociation>> finalList, List<String> roadList, List<NodeAssociation> roadNodeList, String startName, String targetName) {// 0. 对数据处理 - 放在上一层方法中.// 1. 边界条件: ① 如果 开始节点没有子节点 可以结束 ② 该节点为 目标节点, 则对list进行结果的收取 并返回// 1.1 判断该节点是否为目标节点:if (startName.equals(targetName)) {// 拷贝List<NodeAssociation> result = new ArrayList<>(roadNodeList);// 结果收割finalList.add(result);return;}// 1.2 如果不是目标节点,则需要判断有没有子节点, 从原始数据中List<NodeAssociation> sonNodeList = findSonNodeList(rawData, startName);// 对子节点list进行过滤,过滤掉已经走过的路的结点List<NodeAssociation> collect = sonNodeList.stream().filter((item) -> {String leftNodeName = item.getLeftNodeName();String rightNodeName = item.getRightNodeName();String nextNode = startName.equals(leftNodeName) ? rightNodeName : leftNodeName;return !roadList.contains(nextNode);}).collect(Collectors.toList());if (collect.size() == 0) {return;}// 3. 开始遍历--> 横向遍历for (int i = 0; i < collect.size(); i++) {// 3.1 把当前遍历节点加入路径NodeAssociation curNode = collect.get(i);String leftNodeName = curNode.getLeftNodeName();String rightNodeName = curNode.getRightNodeName();String nextNode = startName.equals(leftNodeName) ? rightNodeName : leftNodeName;roadList.add(nextNode);roadNodeList.add(curNode);// 3.2 开始遍历递归dfs(finalList, roadList, roadNodeList, nextNode, targetName);// 3.3 回溯roadList.remove(roadList.size() - 1);roadNodeList.remove(roadNodeList.size() - 1);}}// 找到子节点listprivate List<NodeAssociation> findSonNodeList(List<NodeAssociation> data, String startName) {return data.stream().filter((item) -> startName.equals(item.getLeftNodeName()) || startName.equals(item.getRightNodeName())).collect(Collectors.toList());}
}

最后的结果：

打印原始数据
NodeAssociation{leftNodeName='A', rightNodeName='B'}
NodeAssociation{leftNodeName='A', rightNodeName='C'}
NodeAssociation{leftNodeName='A', rightNodeName='D'}
NodeAssociation{leftNodeName='B', rightNodeName='E'}
NodeAssociation{leftNodeName='E', rightNodeName='C'}
NodeAssociation{leftNodeName='E', rightNodeName='H'}
NodeAssociation{leftNodeName='D', rightNodeName='F'}
NodeAssociation{leftNodeName='H', rightNodeName='F'}
NodeAssociation{leftNodeName='D', rightNodeName='A'}
NodeAssociation{leftNodeName='C', rightNodeName='F'}
打印  A  -->  E结果集:
打印第1条路:
NodeAssociation{leftNodeName='A', rightNodeName='B'}
NodeAssociation{leftNodeName='B', rightNodeName='E'}
打印第2条路:
NodeAssociation{leftNodeName='A', rightNodeName='C'}
NodeAssociation{leftNodeName='E', rightNodeName='C'}
打印第3条路:
NodeAssociation{leftNodeName='A', rightNodeName='C'}
NodeAssociation{leftNodeName='C', rightNodeName='F'}
NodeAssociation{leftNodeName='H', rightNodeName='F'}
NodeAssociation{leftNodeName='E', rightNodeName='H'}
打印第4条路:
NodeAssociation{leftNodeName='D', rightNodeName='A'}
NodeAssociation{leftNodeName='D', rightNodeName='F'}
NodeAssociation{leftNodeName='H', rightNodeName='F'}
NodeAssociation{leftNodeName='E', rightNodeName='H'}
打印第5条路:
NodeAssociation{leftNodeName='D', rightNodeName='A'}
NodeAssociation{leftNodeName='D', rightNodeName='F'}
NodeAssociation{leftNodeName='C', rightNodeName='F'}
NodeAssociation{leftNodeName='E', rightNodeName='C'}打印  A  -->  D结果集:
打印第1条路:
NodeAssociation{leftNodeName='A', rightNodeName='B'}
NodeAssociation{leftNodeName='B', rightNodeName='E'}
NodeAssociation{leftNodeName='E', rightNodeName='C'}
NodeAssociation{leftNodeName='C', rightNodeName='F'}
NodeAssociation{leftNodeName='D', rightNodeName='F'}
打印第2条路:
NodeAssociation{leftNodeName='A', rightNodeName='B'}
NodeAssociation{leftNodeName='B', rightNodeName='E'}
NodeAssociation{leftNodeName='E', rightNodeName='H'}
NodeAssociation{leftNodeName='H', rightNodeName='F'}
NodeAssociation{leftNodeName='D', rightNodeName='F'}
打印第3条路:
NodeAssociation{leftNodeName='A', rightNodeName='C'}
NodeAssociation{leftNodeName='E', rightNodeName='C'}
NodeAssociation{leftNodeName='E', rightNodeName='H'}
NodeAssociation{leftNodeName='H', rightNodeName='F'}
NodeAssociation{leftNodeName='D', rightNodeName='F'}
打印第4条路:
NodeAssociation{leftNodeName='A', rightNodeName='C'}
NodeAssociation{leftNodeName='C', rightNodeName='F'}
NodeAssociation{leftNodeName='D', rightNodeName='F'}
打印第5条路:
NodeAssociation{leftNodeName='D', rightNodeName='A'}

如果想要得到最短路径， 那么也很简单， 在每次收割结果时，对list做一下判断即可， 每次取最小的list， 便可得到最短路径。

欢迎讨论~~~