当你有小段的时候，如何展示每一条可能走的路？
当你有小段的时候，如何展示每一条可能走的路？
提问于 2019-03-30 19:36:42
我试着制作一个程序来显示当你有段的时候你可以选择的所有不同的路径。片段、开始和命运都是投入，它的工作方式如下：
部分：
- 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
它不应该显示重复位置的路径(make循环)，比如：
A->C->F->A->D->E
我使用的是arrayLists，我有一个名为段的类，它的属性是段的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”列表，是接下来要检查的。它将搜索从这三个点开始的片段，等等。我没有得到任何输出，我可以到E，但我不知道如何跟踪所有的路径，我采取了。
我该如何解决这个问题？
回答 1
Stack Overflow用户
发布于 2019-04-02 17:59:25
假设您不想包含有循环的路径，下面的算法应该可以解决您的问题。
- 在处理图问题时构造一个输入图，使用图邻接表表示是一种很好的做法。在这种情况下，邻接集就足够了.
- 预处理该图形以删除所有自圈路径(指向自身的路径)
- 对至少有一个邻居的每个节点执行深度优先搜索--每个搜索从一个特定节点开始添加所有可能的路径，在对所有节点执行此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));
}
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/55435039
复制相关文章
相似问题
腾讯云开发者
