我有一个程序可以打印图形的所有可达路径。它包含 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:)?
最佳答案
这并不难做到。您所需要的只是一个计数器变量来跟踪您当前正在打印的路径。在您的情况下,您可以在调用 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 设为静态函数 (
由于我们现在使用实例变量来跟踪路径计数,因此每次搜索都有一个 Search 类实例就是我们想要的。private static void DFS(...)
),则可以直接从主函数调用它,而无需创建Search 类的实例和 new Search().DFS(graph,visited);
可以转换为 DFS(graph,visited);
.
编辑:重新设计代码片段以在函数中使用实例变量而不是本地变量,这不起作用,因为函数是递归的。感谢 Andreas 指出了这一点。
关于java - 如何在使用递归时增加 3 个不同路径的数字?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37760500/