有向图的数据结构,允许快速删除节点？

Question

我需要存储有向图(不一定是非循环的),以便尽可能快地删除节点.我不介意存储额外的数据,以便确切地知道删除节点时必须经过哪些边缘.

如果我存储边缘列表(作为节点索引对),那么当杀死某个节点时,我必须在整个列表中搜索源或目标为n的边.这对我的申请来说太贵了.通过在节点中存储一些额外的数据可以避免这种搜索吗？

一个想法是让每个节点存储自己的源和目标,作为两个单独的列表.当节点n被杀死时,它的列表也被杀死.但是,与节点n相关联的所有目标/来源如何知道更新自己的列表(即,从列表中消除已解散的节点)？这需要一些昂贵的搜索......

可以避免吗？

谢谢.

Answer 1

您有两个选择，但不会太花哨：邻接列表和邻接矩阵。前者可能最适合您正在做的事情。要删除节点，只需删除该节点的列表中的所有出边即可。对于入边，您可以考虑为每个列表保留一个哈希表以进行 O(1) 查找。