【数据结构】图的存储-邻接矩阵法、邻接表法、十字链表与邻接多重表（下）

2. 邻接表（顺序+链式存储）

说明：*first指向第一条边，但是把哪一条看成第一条边，并不唯一。

#define MaxVertexNum 100  // 顶点数目的最大值
// 边/弧
typedef struct ArcNode{
    int adjvex;  // 边/弧指向哪个结点
    struct ArcNode *next;  // 指向下一条弧的指针
    // InfoType info;  // 边权值
}ArcNode;

// 顶点
typedef struct VNode{
    VertexType data;  // 顶点信息
    ArcNode *first; // 第一条边/弧
}VNode,AdjList[MaxVertexNum];

// 用邻接表存储的图
typedef struct{
    AdjList vertices;
    int vexnum,arcnum;
}ALGraph;

类比树的孩子兄弟表示法：顺序存储各个结点，每个结点中保存孩子链表头指针。

1. 性能分析

对于无向图，如图蓝色区域，从A到B和从B到A实际是同一条，这就造成了边结点的数量是2|E|，整体空间复杂度为O(|V|+2|E|)。

对于有向图，边结点的数量是|E|，整体空间复杂度为O(|V|+|E|)。

2. 思考

如何求顶点的度、入度、出度？如何找到与一个顶点相连的边/弧？

答：

• 对于无向图，如果要找A结点的度，那么顺着A结点向后遍历即可，例如找到了1，2,，3，三个结点，边也就找到了。
• 对于有向图，如果要找A结点的出度，那么顺着A结点向后遍历即可，例如找到了1，一个结点，弧也就找到了。但是对于入度会比较麻烦，需要对所有的结点进行遍历。

3. 十字链表

十字链表只用于存储有向图。

说明：以A结点为例，顺着绿色往后找，能找到所有从A发出的边。顺着橙色往后找，能找到所有指向A的边。

性能分析

空间复杂度：O(|V|+|E|)

如何找到指定顶点的所有出边?——顺着绿色线路找。

如何找到指定顶点的所有入边?―—顺着橙色线路找。

4. 邻接多重表

邻接多重表只适用于存储无向图。

说明：以A结点为例，A的编号为0，顺着箭头往后找，找到了蓝色标注的结点，由于A的编号为0，于是我们再顺着橙色的箭头往后找，找到了红色标注的结点。其余类似。

性能分析

由于每条边只对应一份数据，空间复杂度为O(|V|+|E|)。

删除边、删除结点等操作很方便。

5. 小结