图的存储结构 比较 邻接矩阵、邻接表、十字链表和邻接多重表

邻接矩阵：可以存储无向图，也可存储有向图。构造一个具有n个顶点和e条边的无向图的时间复杂度O（n*n+e*n），其中对灵接矩阵的初始化消耗了O（n*n）的时间。

 

邻接表：图的一种链式存储结构。可以存储无向图和有向图，有向图可以建立“逆邻接表”。构造邻接表或者“逆邻接表”时间复杂度O（n+e），n个顶点+e条边。邻接表相对于邻接矩阵如果是边稀疏图的话比较节约空间。但是邻接表要确定Vi和Vj是否有边的时候没有邻接矩阵方便。

 

十字链表：有向图的另一种链式存储。在十字链表中容易找到Vi的尾的弧，也容易找到以Vi为头的弧，因而容易求得顶点的出度和入度。

 

邻接多重表：无向图的另一种链式存储。方便于边的搜索和边的删除。