时间戳

首页 > 解决方案 > 当您有小段时，如何显示每条可能采取的路径？

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

问题描述

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

细分市场：

现在，我想知道一个人可以采取的所有可用路径，例如从 A 到 E。

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

它不应该显示会重复位置（制作循环）的路径，例如：

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

我正在使用arrayLists，并且我有一个名为段的类，它具有段的开始和结束作为属性。

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") {
                            

                            
                        }
                    }

                }
            }

        }

    }

}

我想知道AE：

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

我该如何解决这个问题？

标签： javaalgorithmgraph-theory

解决方案

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

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

推荐阅读