java - 如何确定图数据结构中某个节点是否有多个输入？

Question

我正在尝试创建一个简单的字符串调制网络。

这个想法是网络的输出是最后执行的模块的输出。
模块可以以任何方式排列，如果模块必须连接作为输入，则应对输入求和(字符串连接)。

为了实现它，我正在考虑将网络表示为图形数据结构。

现在困扰我的是如何确定该模块有两个连接作为输入(这样我就能够在将结果作为输入之前对两个输出求和)？

使用什么算法来遍历图？广度优先？

有更好的解决方案来表示网络吗？[高度赞赏伪代码]

Answer 1

如果您将图存储为邻接列表(“此节点指向这些节点”)，那么您可以简单地迭代邻接列表并将 A -> B 对交换为 B -> A，从而创建一个逆邻接表(“这些节点指向该节点”)。

更多信息请参见 this article .

编辑:

从你的图表中，邻接列表将是:

A -> [B, C]
B -> [D]
C -> [D]
D -> []

这可以表示为 Map<Node, Collection<Node>> 。编写一个接受一对并更新 map 的方法，将其命名为 connect 。要构建该结构，您可以使用 connect(A, B) 来调用它。 , connect(A, C) , connect(B, D) , connect(C, D) .

要反转它，请创建一个新的 Map 来保存反转的结构。迭代映射中的每个键，然后迭代列表中的每个值，并调用 connect在参数颠倒的倒置结构上。