java - 如何进行拓扑排序；创建入度

Question

我正在为学校作业构建一个图形结构。它目前表示为邻接列表：我正在使用哈希图，其中键是图的节点（顶点），值是边列表（包含源节点和目标节点指针以及“权重”的对象) 与关键节点关联。

我的下一个任务是编写拓扑排序，但我被困住了。我认为最好的开始方法是给我的每个节点对象一个整数字段来表示入度（导致节点的边的数量），但我想不出一种方法来将它分配给我的所有节点鉴于我已经拥有的。

有什么建议么？

Answer 1

我建议您也创建 Node.js 的概念。这意味着除了您是 Edge 对象之外，您还将拥有 Node 对象，更好的建模总是可以帮助您更快地解决问题。在这种情况下，使用 Node 定义的 HashMap 有一个键 Integer 会有所帮助，因为您可以在 Node 实例中存储其他信息。

但是，如果您想/需要保留当前结构，为了知道有多少条边通向给定节点，您必须遍历 HashMap entrySet 的各种值（根据您所说的将是边缘）并查看哪些边缘具有您要查找的节点具有目标节点，但此信息必须存储在辅助结构中（例如有另一个地图）