临沂网站建设图的表示方法简介

　　临沂网站建设图的表示方法简介

　　图有两种常用的表示法，第一种称作邻接矩阵。如果从顶点巧到顶点巧存在一条边,则邻接矩阵的第i行第j列的元素就标记为1，否则不作标记。设顶点的数目为则邻接矩阵是一个nxn矩阵,它的空间代价为。

　　图的第二种常用表示方法为邻接表。邻接表是一个以链表为元素的数组。这个数组包含n个元素，其中第i个元素存储的是指向顶点化的边表的指针。这个边表是由顶点切的邻接点构成的链表。邻接表的空间代价与图的边及顶点数目均有关。设边的数目为e，则邻接表的空间代价为。

　　图还有其他的存储方法，在此限于篇幅不再详细介绍。具体用哪种表示法的存储效率更高，取决于图中边的数目。邻接表仅存储实际出现在图中的那些边,但是需要指针等结构开销;邻接矩阵不需要结构开销，但是必须存储所有可能出现的边。整体而言，密集图使用邻接矩阵的存储效率比较高，而用邻接表表示稀琉图比较节省空间。

　　在对相关算法的时间代价的影响方面，邻接矩阵的时间代价更高。这主要是因为当访间某个顶点所有可能的相邻顶点时，使用邻接表更为快捷，而这种操作在图的算法中经常用到。