2015年国家电网考试备考计算机之数据结构与算法(12)

　　对于无向图，一条边对应都是两个顶点，所以，在循环中，一次就针对i和j分布进行插入。

　　本算法的时间复杂度，对于n个顶点e条边来说，很容易得出是O(n+e)。

　　1.3 十字链表

　　对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才知道，反之，逆邻接表解决了入度却不了解出度情况。下面介绍的这种有向图的存储方法：十字链表，就是把邻接表和逆邻接表结合起来的。

　　重新定义顶点表结点结构，如下所示。