C有向图实现选择
欢迎mon amie，
在我的一些作业中，我觉得有必要使用Graph ADT。 但是，我希望拥有它，我怎么说，通用。 也就是说，我想在其中存储任何我喜欢的东西。
我面临的问题与复杂性有关。 我应该用什么数据结构来表示这组节点？ 我忘了说我已经决定使用邻接表技术 。
一般来说，教科书提到了一个链表，但是，据我的理解，无论何时链接表有用，我们需要执行搜索， 树就会更好 。
但是，再次，我们需要的是将一个节点与其相邻节点列表相关联， 那么散列表又如何呢？
你能帮我决定哪些数据结构（链表，树，哈希表）应该存储节点吗？
...图ADT。 但是，我希望拥有它，我怎么说，通用。 也就是说，我想在其中存储任何我喜欢的东西。
这基本上是ADT（抽象数据类型）的要点。
关于使用哪种数据结构，您可以使用。 对于节点集合， Hash table将是一个不错的选择（如果你有一个好的C实现）。 您将有分期的O（1）访问任何节点。 LinkedList将在最坏情况下O（n）时间找到一个节点， Balanced Tree将是O（logn），并且不会给你任何优于散列表的优点，除非由于某种原因你会将节点集合排序为LOT （在这种情况下，使用树的中序遍历进行排序并且在O（n）时间中）
关于每个节点的邻接表，它取决于你想要对图做什么。 如果只实现DFS和BFS，则需要遍历特定节点的所有邻居，因此LinkedList是最简单的方法，并且已足够。
但是，如果您需要检查是否存在特定的边，那么O（n）时间将会是最坏的情况，因为您需要遍历整个列表（邻接矩阵实现将使此操作为O（1））
相邻节点的LinkedList可能就足够了，这取决于你要做什么。
如果您需要知道哪些节点彼此相邻，则可以使用邻接矩阵。 换句话说，对于n节点的图，如果i和j在图中彼此相邻，那么您有一个nxn矩阵，其输入为(i,j)为1 。
上一篇: C Directed Graph Implementation Choice
下一篇: Problems trying to build PocketSphinx for Android using NDK