图在C中的实现

Question

我想知道实现图形数据结构的最佳和最快的方法以及相关的算法。

1. Adjacency-List是由本书推荐的。

。

但是当我想要找到两个顶点v1和v2之间的边时，我无法理解一个大图。

我必须遍历这个数组，它将是O(n)。

我的理解是正确的还是有更好的方法来完成这件事。

Answer 1

首先，它不是O(n)。保持列表的排序，它将是O(logN)。邻接表不一定由链表实现。通常有一个数组。

另一种非常流行的方法是邻接矩阵nxn，其中ai是1(或边的权重)，如果i和j是连通的，否则是0。对于边多的稠密图，这种方法是最优的。对于稀疏图，邻接列表更好。

Answer 2

您可以使用邻接矩阵代替列表。它会让你很快找到边缘，但它会占用一个大图的大量内存。

Answer 3

有许多实现图的方法。你应该选择一个最适合你的算法。一些想法：

( a)全局节点和边缘列表。

( b)全局节点列表，每个节点边缘列表.

( c)邻接矩阵(Ai =w(如果存在Vi边连接)，则为0)

d)边缘矩阵。(如果Ei连接节点Vj，则Ai=1)