無向圖中尋找指定路徑：深度優先遍歷算法

刷題記錄

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 的所有路徑：

【注意】

可能存在 A --B ， B – A 這種干擾項
可能存在 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，便可得到最短路徑。

歡迎討論~~~