最新图的存储结构邻接矩阵幻灯片.ppt

《最新图的存储结构邻接矩阵幻灯片.ppt》由会员分享，可在线阅读，更多相关《最新图的存储结构邻接矩阵幻灯片.ppt（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图的存储结构邻接矩阵图的存储结构邻接矩阵图的存储结构 图的存储结构相比较线性表与树来说就复杂很多。 我们回顾下，对于线性表来说，是一对一的关系，所以用数组或者链表均可简单存放。树结构是一对多的关系，所以我们要将数组和链表的特性结合在一起才能更好的存放。 那么我们的图，是多对多的情况，另外图上的任何一个顶点都可以被看作是第一个顶点，任一顶点的邻接点之间也不存在次序关系。 我们仔细观察以下几张图，然后深刻领悟一下：邻接矩阵（有向图） 无向图的边构成了一个对称矩阵，貌似浪费了一半的空间，那如果是有向图来存放，会不会把资源都利用得很好呢？V0V1V2V3顶点数组：顶点数组：V0V1V2V3V0V1V2

2、V3V00001V11010V21100V30000邻接矩阵（有向图） 可见顶点数组vertex4=V0,V1,V2,V3，弧数组arc44也是一个矩阵，但因为是有向图，所以这个矩阵并不对称，例如由V1到V0有弧，得到arc10=1，而V0到V1没有弧，因此arc01=0。 另外有向图是有讲究的，要考虑入度和出度，顶点V1的入度为1，正好是第V1列的各数之和，顶点V1的出度为2，正好是第V1行的各数之和。邻接矩阵（网） 在图的术语中，我们提到了网这个概念，事实上也就是每条边上带有权的图就叫网。这里“”表示一个计算机允许的、大于所有边上权值的值。V0V1V2V3顶点数组：顶点数组：V0V1V2V3V0V1V2V3V0018V1802V240V3082418代码实现 作为一个课后作业给大家自己锻炼下，小甲鱼提供的参考答案仅供参考借鉴！