java - 当你有小段时，如何显示每条可能采取的路径？

Question

我正在尝试制作一个程序来显示当您有段时可以采用的所有不同路径。片段、开始和命运是输入，它会像这样工作:

分割:

• A->B
• A->C
• A->D
• B->D
• B->A
• C->E
• C->F
• C->D
• D->G
• D->F
• D->E
• F->E
• F->A
• F->B
• G->A
• G->B
• G->E

现在，我想要知道所有可用的路径，例如从 A 到 E。

最后，它应该显示如下内容:

• A->C->E
• A->C->F->E
• A->D->G->E
• A->D->E

它不应该显示会重复位置(形成循环)的路径，例如:

A->C->F->A->D->E

我正在使用 arrayLists，并且我有一个名为 segment 的类，它具有一个段的 Start 和 End 作为属性。

import java.util.ArrayList;

public class mane {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        listatrips a = new listatrips("A", "B");
        listatrips b = new listatrips("A", "C");
        listatrips c = new listatrips("A", "D");
        listatrips d = new listatrips("B", "D");
        listatrips e = new listatrips("B", "A");
        listatrips f = new listatrips("C", "E");
        listatrips h = new listatrips("C", "F");
        listatrips i = new listatrips("C", "D");
        listatrips j = new listatrips("D", "E");
        listatrips l = new listatrips("D", "F");
        listatrips m = new listatrips("D", "G");
        listatrips n = new listatrips("F", "E");
        listatrips o = new listatrips("F", "A");
        listatrips p = new listatrips("F", "B");
        listatrips q = new listatrips("G", "B");
        listatrips r = new listatrips("G", "A");
        listatrips s = new listatrips("G", "E");

        // A->E

        ArrayList<listatrips> ola = new ArrayList<listatrips>();
        ArrayList<String> ahah = new ArrayList<String>();
        ArrayList<String> bl = new ArrayList<String>();
        ArrayList<listatrips> ola2 = new ArrayList<listatrips>();
        ArrayList<String> eheh = new ArrayList<String>();
        ola2 = ola;

        ola.add(a);
        ola.add(b);
        ola.add(c);
        ola.add(d);
        ola.add(e);
        ola.add(f);
        ola.add(h);
        ola.add(i);
        ola.add(j);
        ola.add(l);
        ola.add(m);
        ola.add(n);
        ola.add(o);
        ola.add(p);
        ola.add(q);
        ola.add(r);
        ola.add(s);
        ola.size();

        int count = 0;

        eheh.add("A");
        boolean g = false;
        while (!g) {
            count = count + 1;
            for (int t = 0; t < ahah.size(); t++) {
                bl.add(ahah.get(t));
            }
            ahah.clear();
            for (int t1 = 0; t1 < eheh.size(); t1++) {
                ahah.add(eheh.get(t1));
            }
            eheh.clear();
            for (int z = 0; z < ola2.size(); z++) {

                for (int v = 0; v < ahah.size(); v++) {

                    if (ola2.get(z).inicio == ahah.get(v)) {

                        if (!bl.contains(ola2.get(z).fim) & !ahah.contains(ola2.get(z).fim)) {

                            eheh.add(ola2.get(z).fim);
                        }
                        if (ola.get(z).fim == "E") {
                            

                            
                        }
                    }

                }
            }

        }

    }

}

我想知道A-E:

我首先检查从 A 开始的每个片段，然后将这些片段的结尾添加到列表“eheh”中。当“while”中的代码第二次开始时，“ahah”中的A进入“bl”(黑名单)，因此不会再次检查。 B、C、D 从“eheh”到“ahah”列表，接下来要检查的是那些。它将搜索从这 3 个点开始的段，依此类推。我没有得到任何输出，我可以到达 E，但我不知道如何跟踪我走过的所有路径。

我该如何解决这个问题？

Answer 1

假设您不想包含有循环的路径，以下算法应该可以解决您的问题。

1. 构建输入图在处理图问题时，使用图邻接表表示法是一种很好的做法。在这种情况下，邻接集就足够了。

2. 预处理图形以删除所有自圆路径(指向自身的路径)

3. 对至少有 1 个邻居的每个节点执行深度优先搜索每次搜索都会添加从一个特定节点开始的所有可能路径，在所有节点上执行此 dfs 后给出所有可能路径。 dfs 本身使用回溯。终止条件是您击中了一个没有邻居的节点(例如您示例中的 E)或者您击中了一个循环。

import java.util.*;

class Segment {
    String from, to;
    Segment(String from, String to) {
        this.from = from;
        this.to = to;
    }
}

public class PossiblePaths {
    public static List<List<String>> getAllPossiblePaths(Segment[] segments) {
        List<List<String>> paths = new ArrayList<>();

        //construct graph
        Map<String, Set<String>> graph = new HashMap<>();
        for(Segment segment : segments) {
            if(!graph.containsKey(segment.from)) {
                graph.put(segment.from, new HashSet<>());
            }
            Set<String> tos = graph.get(segment.from);
            tos.add(segment.to);
        }

        //preprocess to remove self circle
        for(String node : graph.keySet()) {
            Set<String> neighbors = graph.get(node);
            if(neighbors.contains(node)) {
                neighbors.remove(node);
            }
        }
        //dfs on each node in this graph to find all paths that do not have cycle in it
        for(String node : graph.keySet()) {
            if(graph.get(node).size() > 0) {
                List<String> path = new ArrayList<>(); path.add(node);
                Set<String> visited = new HashSet<>(); visited.add(node);
                dfs(graph, paths, path, node, visited);
            }
        }
        return paths;
    }
    private static void dfs(Map<String, Set<String>> graph, List<List<String>> paths, List<String> path, String node, Set<String> visited) {
        if(path.size() > 1) {
            paths.add(new ArrayList<>(path));
        }
        Set<String> neighbors = graph.get(node);
        if(neighbors != null) {
            for(String neighbor : neighbors) {
                if(!visited.contains(neighbor)) {
                    path.add(neighbor);
                    visited.add(neighbor);
                    dfs(graph, paths, path, neighbor, visited);
                    path.remove(path.size() - 1);
                    visited.remove(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        Segment segment1 = new Segment("A", "B");
        Segment segment2 = new Segment("A", "C");
        Segment segment3 = new Segment("A", "D");
        Segment segment4 = new Segment("B", "D");
        Segment segment5 = new Segment("B", "A");
        Segment segment6 = new Segment("C", "E");
        Segment segment7 = new Segment("C", "F");
        Segment segment8 = new Segment("C", "D");
        Segment segment9 = new Segment("D", "G");
        Segment segment10 = new Segment("D", "F");
        Segment segment11 = new Segment("D", "E");
        Segment segment12 = new Segment("F", "E");
        Segment segment13 = new Segment("F", "A");
        Segment segment14 = new Segment("F", "B");
        Segment segment15 = new Segment("G", "A");
        Segment segment16 = new Segment("G", "B");
        Segment segment17 = new Segment("G", "E");

        Segment[] segments = {segment1, segment2, segment3, segment4, segment5, segment6, segment7, segment8, segment9,
                                segment10, segment11, segment12, segment13, segment14, segment15, segment16, segment17};

        List<List<String>> paths = getAllPossiblePaths(segments);
        for(int i = 0; i < paths.size(); i++) {
            System.out.println(paths.get(i));
        }
    }
}