C定向图实现选择
欢迎mon amie ，
在我的一些作业中，我觉得需要使用Graph ADT。 但是，我想拥有它，怎么说， generics 。 也就是说，无论我喜欢什么，我都希望存储在其中。
我面临的问题与复杂性有关。 我应该使用什么数据结构来表示节点集？ 我忘了说我已经决定使用Adjacency list技术 。
一般来说，教科书提到了一个链表，但据我所知，只要链表很有用并且我们需要进行搜索， 树就更好了 。
但话说回来，我们需要的是将一个节点与其相邻节点列表相关联， 那么哈希表怎么样呢？
你能帮我决定在哪些数据结构（链表，树，哈希表）中存储节点？
…图ADT。 但是，我想拥有它，怎么说，generics。 也就是说，无论我喜欢什么，我都希望存储在其中。
这基本上是ADT（抽象数据类型）的要点。
关于使用哪种数据结构，您可以使用其中任何一种。 对于节点集， Hash table是一个不错的选择（如果你有一个很好的C实现）。 您将对任何节点分摊O（1）访问权限。 LinkedList将在最坏情况下花费O（n）时间来查找节点， Balanced Tree将是O（logn）并且不会给你任何优于哈希表的优势，除非由于某种原因你将对节点集进行排序很多（在这种情况下，使用树的inorder遍历进行排序并在O（n）时间内）
关于每个节点的邻接列表，它取决于您要对图表执行的操作。 如果你只实现DFS和BFS，你需要迭代特定节点的所有邻居，所以LinkedList是最简单的方法就足够了。
但是，如果你需要检查是否存在特定的边缘，那么最糟糕的情况是O（n）时间，因为你需要迭代整个列表（一个邻接矩阵实现会使这个操作O（1））
相邻节点的LinkedList就足够了，这取决于你要做什么。
如果您需要知道哪些节点彼此相邻，则可以使用邻接矩阵 。 换句话说，对于n节点的图形，您有一个nxn矩阵，如果i和j在图中彼此相邻，则(i,j)的条目为1 。