数据结构:图的表示

任何一本讲到图算法的算法书,都会讲到图的表示方法有两种

1 邻接矩阵 ,对于N个点的图,需要N×N的矩阵表示点与点之间是否有边的存在。这种表示法的缺点是浪费空间,尤其是对于N×N的矩阵是稀疏矩阵,即边的数目远远小于N×N的时候,浪费了巨大的存储空间

24774106_1362195546qm7q

2 邻接链表,对于任何一个node A,外挂一个邻接链表,如果存在 A->X这样的边,就将X链入链表。 这种表示方法的优点是节省空间,缺点是所有链表都存在的缺点,地址空间的不连续造成缓存命中降低,性能有不如临界矩阵这样的数组。

24774106_1362197565517r

一直以来,我也是觉得,鱼和熊掌不可兼得,这是无可奈何的事情。直到我看到了一份比较完美的code。他有动态分配的数组来存放邻接节点。一起欣赏下这份代码吧。年前我第一次看到这份代码的时候,激动的我晚上半天睡不着觉。平时自己写的代码,一板一眼,虽说功能无误,总少了那么几分灵气。看了C算法,也算对图的表示方法知道一些,却写不出这么优美的代码。

我以前觉得,自己大量练习联系写代码是学习编程的最好的方法,是最开但是看了这份代码后,觉得,学习前辈高人优秀的代码,是提高自己的一条捷径,对我们这些普通的coder而言,我们看代码的时间是超过写代码的时间的。阅读前辈优秀代码,会更快的提升自己的编程能力。对于初学者尤其是这样,这也是进入一个优秀的开发team的重要性,能更快的成长。

欣赏代码Yale大学前辈的代码吧。

这是一份PineWiki网站里面提供的一份图的表示的代码,实现的很优美吧?动态分配数组,长度可以扩展,既不浪费空间,有不会带来性能损失。

除此外,graph_foreach这种思想也很不错啊。最近学习了一段时间的Lisp,这种传递函数作用到每一个元素上的方法,相当于Lisp中的mapcar,让人不仅拍案叫绝,很容易就能扩展出很好的功能。(当然也不是完全没瑕疵,比如realloc没有判断失败的情景,白璧微瑕)

既然是图的表示,我们当然很希望能够看到可视化的图。我看Land of Lisp一书中,学到了Linux下的neato 命令。 Linux下有工具帮助生成图的图片,可以满足我们可视化的需求。

先看下测试代码。

我们这个测试程序基本测试了graph的API,同时利用graph_foreach函数的高效扩展性,输出了dot文件格式的文件我们看下执行结果。

在我的Ubuntu下面用XDot可以看到test.dot已经是个图形文件了。图形如下:

24774106_136214724653lb

当然了,我们也可以用 dot命令绘制出PNG格式的图片来:

我们可以看到在当前目录下产生了一个文件名为graph_test.png的PNG格式的图片。打开看下和上面的图是一致的。我就不贴图了。

对dot感兴趣的筒子,可以继续阅读『dot 学习笔记』二. 记录 Shell 的变迁

参考文献:

1  Land of Lisp

2 PineWiki

3 算法:C语言实现。

1 9 收藏 评论

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部