C语言中的图数据结构实现

Question

我已经学习了图形数据结构的基础知识。现在我想实现所有可以在图形上执行的结构/算法/操作。

请分享一些有用的链接，让我可以开始使用C语言进行图形实现。

- AGeek

Answer 1

邻接表和邻接矩阵是实现图形的两种最经典的选择。我不确定在C语言中是否有很多每种方法的在线示例，但此处提供了邻接矩阵表示法的一个示例。

- Alex Martelli

---

谢谢Alex...这个例子看起来很不错...我会试着去理解它...但是有一篇关于邻接表的文章实现不完整 http://www.cs.bu.edu/teaching/c/graph/linked/........ 但是我发现很难入手...你能帮忙吗...我已经理解了数据结构，但是现在如果我们想要插入一个顶点或边等等... - AGeek

@AGeek，在邻接矩阵中：插入边（在现有顶点I和J之间）→只需设置matrix[I][J]=1；插入新顶点N+1 → 分配新的N+1乘N+1矩阵，并将旧矩阵复制到其中，用0填充新行和列。在邻接表中：插入边（在现有顶点I和J之间）→将J附加到I的邻接表中；插入新顶点→将其附加到现有顶点列表中。 - Alex Martelli

Answer 2

这本书，算法设计手册[PDF]中有C代码实现图形。

如果想要更全面的关于图形和相关算法（DFS、Bellman-Ford等）的教材，算法导论（非常好）中有伪代码实现可以供您使用。

标准的邻接表或矩阵表示在两本书中都有描述，正如Alex所提到的。

- bw_0x7c6