java - 为 Ford-Fulkerson 算法创建图形对象的智能方法是什么？

Question

我正在尝试实现 Ford–Fulkerson algorithm在 Java 中，我一直遇到一些问题，我的代码变得令人讨厌且不必要地复杂。

我想要的是:

class Node:
    private int id
    private static int idAssigner // I may move this to another class
    // etc

class flowNetwork
    private Node source  // begin point
    private Node sink    // end point

现在我想像对(双向)树一样对节点进行分组。每个节点都有一个它连接到的所有节点的列表。

我的问题是:如何给这个连接一个值(最大流量，当前流量)？

我应该创建另一个类 Connection 有 Node A Node B 和 max flow/当前流量。如果我这样做，我应该如何连接节点？ (就像每个节点都应该有一个 Connection 那样不是多余的吗？我有点卡住了。编辑 或者我应该只使用 Connections 并实现某种搜索功能以适应链接元素。老实说，这是我能想到的全部。

附言

这门课主要是数学部分，所以我从来没有实现过图表，类(class)也没有涵盖这个，所以感谢你帮助新手 :)(如果这没有在 5 分钟内关闭的话) .

Answer 1

我认为，您可以在每个节点中使用链接节点的映射。以节点键和链接信息为值。

这不是一个快速的解决方案，但很简单。

更快的方法是拥有一个矩阵，其元素是一个链接对象，包含所有链接信息。行和列将是节点索引。