c - 在 c 中实现图的数据结构的想法

Question

我想在 C 中实现一个图。我对如何存储每个节点感到困惑。我首先考虑使用链表，但是如何存储连接到一个节点的下一个节点。

任何想法我应该使用什么数据结构以及我应该如何使用它？

Answer 1

有一些众所周知的方法可以做到这一点。

一种是使用大小为 [n][n] 的二维数组，其中 n 是节点数。如果存在从 a 到 b 的链接，则设置 graph[a][b]= 1。这种方法通常速度很快，但会占用大量内存，尤其是在没有那么多链接和节点的情况下。

另一种方法是创建所有节点的列表（或数组），并将每个节点的内容设置为指向动态数组或链接到的节点列表。

Answer 2

如果您的图形稀疏，则有用的数据结构是邻接列表（链表的链表），即顶点之间的连接（边）很少。

如果您的图很密集，则使用邻接矩阵(nxn) 二维数组，即您的顶点之间有很多边。