数据结构有向图，允许快速节点删除？ [英] Data structure for directed graphs, allowing fast node deletion?

问题描述

我需要存储有向图（不一定无环），从而使节点删除是尽可能快。我不会介意为了知道哪些边有当一个节点被删除，去存储更多的数据。

I need to store a directed graph (not necessarily acyclic), so that node deletion is as fast as possible. I wouldn't mind storing additional data in order to know exactly which edges have to go when a node is deleted.

如果我存储边的列表（如双节点指标），那么当杀死一些节点n我要搜索整个列表中的边缘，其源或目标为n。这是太昂贵了我的申请。可以这样搜索是可以避免的存储一些额外的数据在节点？

If I store a list of edges (as pairs of node indexes), then when killing some node n I have to search the whole list for edges whose source or target is n. This is too costly for my application. Can this search be avoided by storing some additional data in the nodes?

一个想法是让每个节点存储自己的源和目标，作为两个单独的列表。当节点N被杀害，其名单都杀了。不过，如何将所有的目标/源链接到节点n知道要更新自己的列表（即，以消除他们的名单已不存在的节点）？这将需要一些昂贵的搜索...

One idea would be to have each node store its own sources and targets, as two separate lists. When node n is killed, its lists are killed too. But then, how would all the targets/sources linked to node n know to update their own lists (i.e., to eliminate the defunct node from their lists)? This would require some costly searching...

可不可以这样可以避免？

Can it be avoided?

THX。

推荐答案

您有两种选择没有得到太多花哨的邻接表和邻接矩阵。前者可能是最适合你在做什么。要删除一个节点，只是消除了列表节点的所有出边。对于入边，你可能会考虑保持一个哈希表中为每个列表O（1）查找。

You have two choices without getting too fancy are Adjacency List and Adjacency Matrix. The former is probably best for what you're doing. To remove a node, simply eliminate the list for that node for all of its out edges. For the in-edges, you might consider keeping a hash-table for each list for O(1) lookups.

这是一个很好的概述 http://www.algorithmist.com/index.php/Graph_data_structures

This is a good overview http://www.algorithmist.com/index.php/Graph_data_structures

这篇关于数据结构有向图，允许快速节点删除？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！