0

除了我正在使用的这个 JGraphT (Java) 库之外，我还是图论的新手，以便为我试图解决的物流问题实施解决方案。因此，我对解决这个问题的最佳方法有点迷茫，我必须在给定传入数据的情况下表示货物从 A 点到 C 点的路径。

给定一个传送段或有序对的列表，我如何以尽可能少的边以编程方式表示它？

Delivery 1从亚特兰大到孟买。

Delivery 2从亚特兰大到伦敦。

Delivery 3从伦敦到孟买。

在我的可视化图形表示中，我想删除显式Atlanta to Mumbai边缘并简单地从其他边缘推断出来，并将其简单地表示为：

Atlanta -> London -> Mumbai

我觉得可能有一个现有的路径算法可以用来解决这个相当简单的用例，但鉴于我对主题的相对较新，我正在努力找出哪一个。如果我的要求是删除过多的顶点而不是边，那么这里似乎ShortestPathAlgorithm很有用。

我可能会确定我给定的对的最终source和sink（即亚特兰大是源，孟买是接收器），但如果可能的话，我不想走手动移除边缘的路径。

当前代表：

当前代表

期望的代表：

在此处输入图像描述

我创建了一个类来让我接近实现替代深度优先解决方案@JorisKinable 下面提到，但仍然不明白为什么“亚特兰大、孟买和伦敦”按此顺序列出。如果没有对边缘施加权重，是什么导致孟买在这种情况下排在伦敦之前？

public final class Demo {

  public static void main(String[] args) throws Exception {

    // Create the graph object
    Graph<String, DefaultEdge> graph = new DefaultDirectedGraph<>(DefaultEdge.class);

    String atlanta = "Atlanta";
    String london = "London";
    String mumbai = "Mumbai";

    graph.addVertex(atlanta);
    graph.addVertex(london);
    graph.addVertex(mumbai);

    graph.addEdge(atlanta, london);
    graph.addEdge(london, mumbai);
    graph.addEdge(atlanta, mumbai);

    ComponentNameProvider<String> vertexIdProvider = name -> name;
    ComponentNameProvider<String> vertexLabelProvider = name -> name;

    String start = graph.vertexSet().stream().filter(r -> r.equals("Atlanta")).findAny().get();
    System.out.println("-- traverseGraph output");
    traverseGraph(graph, start);

    GraphExporter<String, DefaultEdge> exporter = new DOTExporter<>(vertexIdProvider, vertexLabelProvider, null);
    Writer writer = new StringWriter();
    exporter.exportGraph(graph, writer);
    System.out.println(writer.toString());
  }

  private static void traverseGraph(Graph<String, DefaultEdge> graph, String start) {
    Iterator<String> iterator = new DepthFirstIterator<>(graph, start);
    while (iterator.hasNext()) {
      String string = iterator.next();
      System.out.println(string);
    }
  }
}
4

1 回答 1

1

目前，这个问题的表述不够精确，无法给出准确的答案。但是，您似乎可以通过以下步骤解决您的问题：

  1. 构造一个包含所有弧的有向图。向图中添加一个额外的节点“s”，该节点具有到所有其他节点的出弧。
  2. 从节点 's' 开始执行广度优先搜索(BFS)。
  3. 最后，删除节点 's' 以及所有不属于 BFS 树的边。您也可以使用深度优先搜索而不是 BFS，并删除所有后边、前边和交叉边。

所有这些都可以在 JGraphT 中轻松完成，但这是一个单独的问题。

于 2019-07-24T17:20:15.933 回答