如何在使用递归时增加 3 个不同路径的数字？

Question

我有一个程序可以打印图形的所有可达路径。它包含 2 类 GraphPath1 和 Search 。程序如下：

Class GraphPath1:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;


public class GraphPath1 {
    List<String> src=new ArrayList<String>();  // source node
    List<String> dest=new ArrayList<String>(); // destination node 

private Map<String, LinkedHashSet<String>> map = new HashMap();

public void addEdge(String node1, String node2){
    LinkedHashSet<String> adjacent = map.get(node1);
    if(adjacent==null) {
        adjacent = new LinkedHashSet();
        map.put(node1, adjacent);
        src.add(node1);
    }
    adjacent.add(node2);
    dest.add(node2);
}



public LinkedList<String> adjacentNodes(String last) {
    LinkedHashSet<String> adjacent = map.get(last);
    if(adjacent==null) {
        return new LinkedList();
    }
    return new LinkedList<String>(adjacent);
}

}

Class 搜索：

import java.util.ArrayList;
import dfs.GraphPath1;
import java.util.LinkedList;
import java.util.List;

import dfs.LoanSystem;


public class Search {
private static final String START = "1";
private static final String END = "7";
public static void main(String[] args) {


    // this graph is directional
    GraphPath1 graph = new GraphPath1();

    graph.addEdge("1", "2");
    graph.addEdge("1", "3");
    graph.addEdge("2", "5");
    graph.addEdge("3", "4");
    graph.addEdge("4", "5");
    graph.addEdge("4", "6");
    graph.addEdge("5", "7");
    graph.addEdge("6", "7");
    //graph.addEdge("7", "1");

    /*
    List<String> s = graph.src;
    List<String> d = graph.dest;
    System.out.print(s);
    System.out.print(d);*/

    LinkedList<String> visited = new LinkedList();
    visited.add(START);
    new Search().DFS(graph, visited);

}


private void DFS(GraphPath1 graph, LinkedList<String> visited) {
LinkedList<String> nodes = graph.adjacentNodes(visited.getLast());
// examine adjacent nodes
for (String node : nodes) {
    if (visited.contains(node)) {
        continue;
    }
    if (node.equals(END)) {
        visited.add(node);
        printPath(visited);
        visited.removeLast();
        break;
    }
}



// in DFS, recursion needs to come after visiting adjacent nodes
for (String node : nodes) {
    if (visited.contains(node) || node.equals(END)) {
        continue;
    }

    visited.addLast(node);
    DFS(graph, visited);
    visited.removeLast();
}

}
/*
public List<Edge> getEdgeList (LinkedList<String> visited){
    List<Edge> edges = new ArrayList<Edge>();
    for(int i=0;i<=visited.size();i++)
        edges.add(new Edge(visited.get(i), visited.get(i+1)));

    return edges;
}
*/

private void printPath(LinkedList<String> visited) {

    ArrayList<String> sequence = new ArrayList<String>();
    {
    for (String node : visited) {
        sequence.add(node);

    }

}
    ArrayList<String> sequences = new ArrayList<String>();
    sequences.addAll(sequence);
    System.out.println(sequences);

}
}

这个程序的输出是：

1,2,5,7
1,3,4,5,7
1,3,4,6,7

现在我需要为这 3 条路径打印 3 条不同的消息。例如：

This is Path 1:
1,2,5,7
This is Path 2:
1,3,4,5,7
This is Path 3:
1,3,4,6,7

但我不知道该怎么做。谁能告诉我如何为 3 条不同的路径增加我在消息中使用的数字（即这是路径 1:）？

Answer 1

这并不难做到。您只需要一个计数器变量来跟踪您当前正在打印的路径。在您的情况下，您可以在调用 DFS() 函数之前将计数器设置为 0。然后在每次打印之前递增它，然后打印你的行说明它是哪条路径。之后你调用 printPath()。这可能看起来像这样：

private int pathCount = 0;

// more of you code ...

private void DFS(GraphPath1 graph, LinkedList<String> visited) {
    LinkedList<String> nodes = graph.adjacentNodes(visited.getLast());
    // examine adjacent nodes
    for (String node : nodes) {
        if (visited.contains(node)) {
            continue;
        }
        if (node.equals(END)) {
            visited.add(node);
            pathNumber++;
            System.out.println("This is path " + pathNumber + ":");
            printPath(visited);
            visited.removeLast();
            break;
        }
    }

    // the rest of the algorithm ...
}

还有一点：如果你让DFS成为一个静态函数(private static void DFS(...))，你可以直接从主函数中调用它，而不必创建Search的实例class 和 new Search().DFS(graph, visited); 可以变成 DFS(graph, visited);. 由于我们现在使用实例变量来跟踪路径计数，因此每次搜索一个搜索实例 class 就是我们想要的。

编辑：重写代码片段以在函数中使用实例变量而不是局部变量，因为函数是递归的，所以这不起作用。感谢 Andreas 指出这一点。

Answer 2

首先，您有原始类型。不要!!!!
例如。将 adjacent = new LinkedHashSet(); 更改为 adjacent = new LinkedHashSet<>();
如果你用的好IDE，应该早就告诉你了

通常，您希望搜索到 return 结果，而不是打印它，否则您无法编写任何 needs/uses 结果的代码.

这意味着您需要一个结果收集器，并将其作为参数传递给递归方法。搜索完成后打印结果。

还有：

DFS可以制作成static.
可以统一处理END和递归调用
ArrayDeque 更适合 visited。
在执行递归方法时，将其隔离在入口方法后面通常是个好主意，因此调用者不必知道递归所需的额外参数（例如 visited ).
START 和 END 应作为 DFS 的参数，因此如果需要，您可以在同一个图形上执行多个搜索。
你的printPath方法好像有点过分了

public final class Search {
    public static void main(String[] args) {
        GraphPath1 graph = new GraphPath1();
        graph.addEdge("1", "2");
        graph.addEdge("1", "3");
        graph.addEdge("2", "5");
        graph.addEdge("3", "4");
        graph.addEdge("4", "5");
        graph.addEdge("4", "6");
        graph.addEdge("5", "7");
        graph.addEdge("6", "7");
        graph.addEdge("7", "1");

        searchAndPrint(graph, "1", "1");
        searchAndPrint(graph, "3", "2");
        searchAndPrint(graph, "1", "7");
    }

    private static void searchAndPrint(GraphPath1 graph, String start, String end) {
        List<List<String>> result = DFS(graph, start, end);
        for (int i = 0; i < result.size(); i++)
            System.out.printf("This is Path %d: %s%n", i + 1, result.get(i));
    }

    private static List<List<String>> DFS(GraphPath1 graph, String start, String end) {
        if (start.equals(end))
            return Collections.singletonList(Collections.singletonList(start));
        List<List<String>> result = new ArrayList<>();
        Deque<String> visited = new ArrayDeque<>();
        visited.add(start);
        DFS(graph, end, visited, result);
        return result;
    }

    private static void DFS(GraphPath1 graph, String end, Deque<String> visited, List<List<String>> result) {
        for (String node : graph.adjacentNodes(visited.getLast()))
            if (! visited.contains(node)) {
                visited.addLast(node);
                if (node.equals(end))
                    result.add(new ArrayList<>(visited)); // add copy to result
                else
                    DFS(graph, end, visited, result);
                visited.removeLast();
            }
    }
}

输出

This is Path 1: [1]

This is Path 1: [3, 4, 5, 7, 1, 2]
This is Path 2: [3, 4, 6, 7, 1, 2]

This is Path 1: [1, 2, 5, 7]
This is Path 2: [1, 3, 4, 5, 7]
This is Path 3: [1, 3, 4, 6, 7]

如何在使用递归时增加 3 个不同路径的数字？

How to increment a number for 3 different paths while using recursion?

java

recursion

graph

path

increment