問題描述
給定一個有向的連線圖，找到從源到目的地的所有路徑。
尋找程式碼審查，最佳化和最佳做法。還需要幫助找出複雜性，我最好的嘗試是 O(E！)，其中 E 是邊數。
class GraphFindAllPaths<T> implements Iterable<T> {
/* A map from nodes in the graph to sets of outgoing edges. Each
* set of edges is represented by a map from edges to doubles.
*/
private final Map<T, Map<T, Double>> graph = new HashMap<T, Map<T, Double>>();
/**
* Adds a new node to the graph. If the node already exists then its a
* no-op.
*
* @param node Adds to a graph. If node is null then this is a no-op.
* @return true if node is added, false otherwise.
*/
public boolean addNode(T node) {
if (node == null) {
throw new NullPointerException("The input node cannot be null.");
}
if (graph.containsKey(node)) return false;
graph.put(node, new HashMap<T, Double>());
return true;
}
/**
* Given the source and destination node it would add an arc from source
* to destination node. If an arc already exists then the value would be
* updated the new value.
*
* @param source the source node.
* @param destination the destination node.
* @param length if length if
* @throws NullPointerException if source or destination is null.
* @throws NoSuchElementException if either source of destination does not exists.
*/
public void addEdge (T source, T destination, double length) {
if (source == null || destination == null) {
throw new NullPointerException("Source and Destination, both should be non-null.");
}
if (!graph.containsKey(source) || !graph.containsKey(destination)) {
throw new NoSuchElementException("Source and Destination, both should be part of graph");
}
/* A node would always be added so no point returning true or false */
graph.get(source).put(destination, length);
}
/**
* Removes an edge from the graph.
*
* @param source If the source node.
* @param destination If the destination node.
* @throws NullPointerException if either source or destination specified is null
* @throws NoSuchElementException if graph does not contain either source or destination
*/
public void removeEdge (T source, T destination) {
if (source == null || destination == null) {
throw new NullPointerException("Source and Destination, both should be non-null.");
}
if (!graph.containsKey(source) || !graph.containsKey(destination)) {
throw new NoSuchElementException("Source and Destination, both should be part of graph");
}
graph.get(source).remove(destination);
}
/**
* Given a node, returns the edges going outward that node,
* as an immutable map.
*
* @param node The node whose edges should be queried.
* @return An immutable view of the edges leaving that node.
* @throws NullPointerException If input node is null.
* @throws NoSuchElementException If node is not in graph.
*/
public Map<T, Double> edgesFrom(T node) {
if (node == null) {
throw new NullPointerException("The node should not be null.");
}
Map<T, Double> edges = graph.get(node);
if (edges == null) {
throw new NoSuchElementException("Source node does not exist.");
}
return Collections.unmodifiableMap(edges);
}
/**
* Returns the iterator that travels the nodes of a graph.
*
* @return an iterator that travels the nodes of a graph.
*/
@Override public Iterator<T> iterator() {
return graph.keySet().iterator();
}
}
/**
* Given a connected directed graph, find all paths between any two input points.
*/
public class FindAllPaths<T> {
private final GraphFindAllPaths<T> graph;
/**
* Takes in a graph. This graph should not be changed by the client
*/
public FindAllPaths(GraphFindAllPaths<T> graph) {
if (graph == null) {
throw new NullPointerException("The input graph cannot be null.");
}
this.graph = graph;
}
private void validate (T source, T destination) {
if (source == null) {
throw new NullPointerException("The source: " + source + " cannot be null.");
}
if (destination == null) {
throw new NullPointerException("The destination: " + destination + " cannot be null.");
}
if (source.equals(destination)) {
throw new IllegalArgumentException("The source and destination: " + source + " cannot be the same.");
}
}
/**
* Returns the list of paths, where path itself is a list of nodes.
*
* @param source the source node
* @param destination the destination node
* @return List of all paths
*/
public List<List<T>> getAllPaths(T source, T destination) {
validate(source, destination);
List<List<T>> paths = new ArrayList<List<T>>();
recursive(source, destination, paths, new LinkedHashSet<T>());
return paths;
}
// so far this dude ignore's cycles.
private void recursive (T current, T destination, List<List<T>> paths, LinkedHashSet<T> path) {
path.add(current);
if (current == destination) {
paths.add(new ArrayList<T>(path));
path.remove(current);
return;
}
final Set<T> edges = graph.edgesFrom(current).keySet();
for (T t : edges) {
if (!path.contains(t)) {
recursive (t, destination, paths, path);
}
}
path.remove(current);
}
public static void main(String[] args) {
GraphFindAllPaths<String> graphFindAllPaths = new GraphFindAllPaths<String>();
graphFindAllPaths.addNode("A");
graphFindAllPaths.addNode("B");
graphFindAllPaths.addNode("C");
graphFindAllPaths.addNode("D");
graphFindAllPaths.addEdge("A", "B", 10);
graphFindAllPaths.addEdge("A", "C", 10);
graphFindAllPaths.addEdge("B", "D", 10);
graphFindAllPaths.addEdge("C", "D", 10);
graphFindAllPaths.addEdge("B", "C", 10);
graphFindAllPaths.addEdge("C", "B", 10);
FindAllPaths<String> findAllPaths = new FindAllPaths<String>(graphFindAllPaths);
List<List<String>> paths = new ArrayList<List<String>>();
// ABD
List<String> path1 = new ArrayList<String>();
path1.add("A"); path1.add("B"); path1.add("D");
// ABCD
List<String> path2 = new ArrayList<String>();
path2.add("A"); path2.add("B"); path2.add("C"); path2.add("D");
//ACD
List<String> path3 = new ArrayList<String>();
path3.add("A"); path3.add("C"); path3.add("D");
//ABCD
List<String> path4 = new ArrayList<String>();
path4.add("A"); path4.add("C"); path4.add("B"); path4.add("D");
paths.add(path1);
paths.add(path2);
paths.add(path3);
paths.add(path4);
findAllPaths.getAllPaths("A", "D");
assertEquals(paths, findAllPaths.getAllPaths("A", "D"));
}
}
最佳解決方法
這是美麗，易於閱讀，和 well-documented 程式碼。閱讀這段程式碼是一種快樂，Java 方面幾乎沒有什麼改進。
在這段程式碼中顯示的最大的弱點不在於你對 Java 的技能 (遠遠超過我的)，而是你對英語的認識。
-
在
addEdgeJavaDoc 中，您可以談論弧線而不是邊。 -
可以改進該方法的錯誤訊息中的語法：「源和目的地，都應該是 non-null」 。可以是 「源和目的地應該是 non-null」 或 「源和目的地都應該是 non-null」 。
-
該方法也執行非常混亂的 JavaDoc「@param length if length if」 – 我不知道這是什麼意思。
但是我們來談談技術方面。
-
recursive方法有一個很好的錯誤：您正在透過==比較T例項：if (current == destination) {但是，這是預設比較指標。它只在這裡工作，因為常量字串
"A"，"B"等由 Java 實現合併。除非你的實際需要比較，否則請比較current.equals(destination)。 -
recursive將忽略迴圈的註釋是錯誤的 – 它將僅構造最多訪問每個節點的路徑。這是處理迴圈的唯一正確方法，否則在迴圈圖中將有無數個路徑。 -
來自
validate的錯誤訊息沒有任何意義。if (source == null) { throw new NullPointerException("The source: " + source + " cannot be null.");所以我們得到 「源：null 不能為 null」 作為錯誤訊息。這是沒有幫助的，我建議改為：
if (source == null) { throw new NullPointerException("The "source" parameter cannot be null."); -
在您的測試程式碼中，您會經歷過多的麻煩，產生預期的
paths。我非常喜歡Arrays.asList(…)：List<List<String>> paths = Arrays.asList( Arrays.asList("A", "B", "D"), Arrays.asList("A", "B", "C", "D"), Arrays.asList("A", "C", "D"), Arrays.asList("A", "C", "B", "D") );這段程式碼很簡潔，self-documenting 。您將路徑放入註釋除了指定它們作為程式碼，當評論說
ABCD高於ACBD路徑時出錯了;-)此外，您測試返回路徑的順序是否相同。應該將路徑的順序視為不相關的 (您實際上對路徑集合感興趣)，並且未指定，因為
HashMap的用法不保證鍵的儲存順序。的確，你正在迭代keySet()，這將決定路徑的順序！更好的平等考驗可能是：assertEquals(new HashSet<List<String>>(paths), new HashSet<List<String>>(result));
次佳解決方法
只是一些小事情：
-
評論在這裡不正確，應該是
ACBD：//ABCD
List<String> path4 = new ArrayList<String>();
path4.add("A"); path4.add("C"); path4.add("B"); path4.add("D");
您可以使用 Guava 的
newArrayList(或編寫類似的方法) 來從測試程式碼中刪除一些重複：List<String> path4 = newArrayList("A", "C", "B", "D"); -
這裡第一個電話是不必要的：
findAllPaths.getAllPaths("A", "D");assertEquals(paths, findAllPaths.getAllPaths("A", "D"));
-
為了這：
if (graph.containsKey(node)) return false;
根據 Code Conventions for the Java Programming Language，
if 語句總是使用大括號 {} 。
省略它們是 error-prone 。我發現 one-liner 難以閱讀，因為如果您逐行掃描程式碼，很容易錯過，在行尾有一個
return語句。 -
我會重新命名
-
validate至validateNotSame， -
paths至expectedPaths，
為了更好的清晰度。
-
-
GraphFindAllPaths可以簡單地是Graph。 -
從清潔程式碼，第 25 頁：類和物件應該有名詞或名詞短語名稱，如
Customer，WikiPage，Account和AddressParser。 […] 類名不應該是動詞。考慮AllPathFinder代替FindAllPaths。 -
您可能希望在此建立防禦性副本：
public FindAllPaths(GraphFindAllPaths<T> graph) {
if (graph == null) {
throw new NullPointerException("The input graph cannot be null.");
}
this.graph = graph;
}
它將禁止惡意客戶端修改類的內部資料，並可能節省您幾個小時的除錯。 (有效 Java，第 2 版，第 39 項：需要時製作防禦副本)
-
Iterable功能和removeEdge方法不使用也不進行測試。您可能可以刪除它們。 -
測試方法通常在
Test檔案 (例如 FindAllPathsTest) 中，並由 JUnit 執行。它們通常位於一個獨立的原始檔夾中，無法使用生產程式碼打包junit.jar(和其他測試依賴項) 。 Maven’s directory structure 是一個 well-known 專案結構，考慮使用它 (以及 Maven，Gradle 或任何其他構建工具) 。
第三種解決方法
這真的是一個有趣的問題。首先我想提到，IMHO 沒有多項式解決這個任務，因為它不是一個最佳化問題。所需的結果不是最大/最小的東西，而是列舉所有可能的路徑。我認為所有可能的路徑可能導致 n！完整圖中的不同路徑，其中 n 是節點數。所以找到一個解決方案取決於輸入的大小。如果一個大的圖形是在輸入，那麼使用這個演演算法將需要很多的時間和 memory ，可能不會完成。我不知道這個解決方案的確切用法，但我想這是一種 Map/導航應用程式。如果你不介意我會標出一些有用的點，並分享我的注意事項：
-
我看不到你在哪裡使用雙重值，這是為每一個邊所持有的。我想它將用於計算路徑的成本並返回按此標準排序的路徑。如果這樣，請考慮一個接一個地發現一小段路徑，每次使用一些流行的演演算法進行 shortest path problem
-
如果輸入上有一個稀疏圖，那麼使用每個節點的 Map 將導致很多重的物件，只保留幾個值。這將不必要地增加記憶體消耗。我不知道用例，將使用什麼型別的節點 (T)，但是我建議使用從 int 到 T 的單個對映，並使用整數作為節點號。然後可以使用 double [] [] 矩陣來儲存邊值，並使用整數作為矩陣中的索引。一個例子：
-
0 – > “A”
-
1 – > “B”
-
2 – > “C”
-
然後邊”A” –4.2 – > “C” 將如下所示：matrix [0] [2] = 4.2 。再次，這將導致矩陣的許多未使用的單元格。即使一個更好的解決方案是擁有一個單一的陣列/列表來儲存每個節點的陣列/鄰居列表。其實你正在迭代鄰居，所以你不需要一個 HashMap，只需持有一個 key-value 對的列表就足夠了。我的意思是：List<List<Double>> nodes 表示圖，而 node.get(i) 是另一個列表， nodeNumber，edgeCost) 。使用前面的例子：
List<Double> aNeighbours = nodes.get(0);
aNeighbours.set(2, 4.2);
如果你使用 ArrayList 考慮提供小的初始容量，因為預設是 16 我想。
我希望你找到一個解決這個問題的工作方法:) 。
參考文獻
注：本文內容整合自 Google/Baidu/Bing 輔助翻譯的英文資料結果。如果您對結果不滿意，可以加入我們改善翻譯效果：薇曉朵技術論壇。