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

Question

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

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);
}

}

类别搜索:

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 类的实例和 new Search().DFS(graph,visited); 可以转换为 DFS(graph,visited);. 由于我们现在使用实例变量来跟踪路径计数，因此每次搜索都有一个 Search 类实例就是我们想要的。

编辑:重新设计代码片段以在函数中使用实例变量而不是本地变量，这不起作用，因为函数是递归的。感谢 Andreas 指出了这一点。