java - JGraphT:如何尽可能有效地表示一组顶点和边

Question

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

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

Delivery 1 从亚特兰大发往孟买。

Delivery 2 从亚特兰大发往伦敦。

Delivery 3 从伦敦发往孟买。

在我的可视化图形表示中，我想删除显式的亚特兰大到孟买边缘，并简单地从其他边缘推断出该边缘并将其简单地表示为:

亚特兰大 -> 伦敦 -> 孟买

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

我可能可以确定给定对的最终源和汇(即亚特兰大是源，孟买是汇)，但不想下降如果可能的话，手动去除边缘的路径。

当前代表:

所需的代表:

我创建了一个类，让我接近实现下面提到的替代深度优先解决方案@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);
    }
  }
}

Answer 1

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

1. 构造一个包含所有弧的有向图。向图中添加一个附加节点，该节点具有到所有其他节点的传出弧。
2. 执行 Breadth First Search (BFS)从节点's'开始。
3. 最后，删除节点以及不属于 BFS 树的所有边。您还可以使用Depth First Search而不是 BFS，并删除所有后边缘、前边缘和交叉边缘。

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