C定向图实现选择

Question

欢迎mon amie,

在我的一些作业中,我觉得需要使用Graph ADT.但是,我想拥有它,我怎么说,通用.也就是说,无论我喜欢什么,我都希望能存储它.

我面临的问题与复杂性有关.我应该使用什么数据结构来表示节点集？我忘了说我已经决定使用Adjacency list技术.

一般来说,教科书提到了一个链表,但是,根据我的理解,只要链表有用并且我们需要执行搜索,树就更好了.

但话又说回来,我们需要的是将一个节点与其相邻节点列表相关联,那么哈希表呢？

你能帮我决定在哪些数据结构(链表,树,哈希表)中存储节点？

Answer 1

...图形 ADT。不过，我想拥有它，怎么说呢，通用的。也就是说，我想把我喜欢的东西都存储在里面。

这基本上就是 ADT（抽象数据类型）的要点。

至于使用哪种数据结构，可以使用其中之一。对于节点集，aHash table将是一个不错的选择（如果您有一个良好的 C 实现）。您将对任何节点具有摊销 O(1) 访问权限。ALinkedList将花费最坏情况 O(n) 时间来找到节点，aBalanced Tree将是 O(logn) 并且不会给你带来任何优于哈希表的优势，除非由于某种原因你会对节点集进行大量排序（其中使用树的中序遍历的情况是排序的并且在 O(n) 时间内）

关于每个节点的邻接列表，这取决于您想要对图做什么。如果您仅实现 DFS 和 BFS，则需要迭代特定节点的所有邻居，因此LinkedList这是最简单的方法，并且足够了。

但是，如果您需要检查特定边是否存在，最坏情况下将花费 O(n) 时间，因为您需要迭代整个列表（邻接矩阵实现将使此操作变得 O(1)）

相邻节点的一个LinkedList就足够了，这取决于您要做什么。