我需要存储有向图（不一定是非循环的），以便节点删除尽可能快。我不介意存储额外的数据，以便准确地知道删除节点时必须删除哪些边。
如果我存储一个边列表（作为节点索引对），那么当杀死某个节点 n 时，我必须在整个列表中搜索源或目标为 n 的边。这对于我的应用来说成本太高了。是否可以通过在节点中存储一些附加数据来避免这种搜索？
一种想法是让每个节点将其自己的源和目标存储为两个单独的列表。当节点 n 被杀死时，它的列表也被杀死。但是，链接到节点 n 的所有目标/源如何知道更新它们自己的列表（即，从它们的列表中消除失效的节点）？这将需要一些昂贵的搜索......
可以避免吗？
Thx.
您有两个选择，但不会太花哨：邻接列表和邻接矩阵。前者可能最适合您正在做的事情。要删除节点，只需删除该节点的列表的所有出边即可。对于入边，您可以考虑为每个列表保留一个哈希表以进行 O(1) 查找。
这是一个很好的概述http://www.algorithmist.com/index.php/Graph_data_structs http://www.algorithmist.com/index.php/Graph_data_structures
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
