图：存储（邻接表法）

Julia999

邻接表法是啥?emm,好吧，我应该是离散课划水了吧，但是离散课有讲嘛？
为啥存储邻接矩阵法不就好了，干嘛还多搞一个，增加学习负担？？emmm，我也是这么觉得来着，但是邻接矩阵法存储稀疏图会有许多的空间浪费，于是,,,,就有了,,,邻接表法。。。。


邻接表法：为每一个定点建立一个单链表存放与他相邻的边
定点表：
采用顺序存储，每个数组元素存放顶点的数据和指向边表的头指针
边表（出边表）
采用链式存储，单链表中存放与一个顶点相邻的所有边，一个链表结点表示一条从该顶点到链表结点顶点的边

#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 vetices;  //顶点表
    int vexnum,arcnum;  //顶点的数量，边的数量
}ALGraph;

若G为无向图，存储空间为O(|V|+2|E|)
若G为有向图，存储空间为O(|V|+|E|)
邻接表更加适用于稀疏图（因为只有顶点和边存在的情况下，才会生成空间去存储）
若G为无向图，则节点的度为该节点边表的长度
若G为有向图，则节点的初度为该节点边表的长度，计算入度则要遍历整个邻接表
邻接表是不唯一的，边表节点的顺序根据算法输入的不同可能不同


                   邻接矩阵         VS          邻接表
适用性：      稠密图                            稀疏图
存储方式：   顺序存储                         顺序存储+链式存储
判断两顶点是否有边：邻接矩阵比邻接表更适合
找出某顶点相邻的边：邻接表比邻接矩阵效率高