邻接表 - Adjacency List

adjvex 邻接点域：存放与Vi邻接的顶点在表头数组的位置
nextarc 链域：指示下一条边或弧
顶点：

• 按标号顺序将顶点顺序储存在一维数组中；

关联同一顶点的边（以顶点为尾的弧）：

• 用线性链表储存

无向图

特点：

• 邻接表不唯一
• 若无向图中有n个顶点、e条边，则其邻接表则需要n个头结点和2e个表节点。适合储存稀疏图 O(n+2e)
• 无向图中顶点v1的度为第i个单链表中的结点数

有向图

-邻接表
-逆邻接表

邻接表储存表示

顶点的节点结构：data | firstarc**

typedef struct VNode{
    VerTexType data;    //顶点信息
    ArcNode *firstarc;    //指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum];    //AdjList表示邻接表类型

说明： 例如，AdjList v; 相当于 VNode v[MVNum];

弧（边）的节点结构 adjvex | nextarc | info

#define MVNum 100    //最大顶点数
typedef struct ArcNode{    //边节点
    int adjvex;    //该边所指向的顶点的位置
    struct ArcNode *nextarc;    //指向下一条边的指针
    OtherInfo info;    //和边相关的信息
}ArcNode;

图的结构定义

typedef struct{
    AdjList vertices;    //vertices--vertex的复数
    int vexnum,arcnum;    //图的当前顶点数和弧数
}ALGraph;

邻接表操作举例说明

算法6.2 邻接表表示法创建无向网

【算法思想】

1. 输入总顶点数和总边数
2. 建立顶点表

依次输入点的信息存入顶点表中
使每个表头结点的中指针域初始化为NULL

1. 创建邻接表

依次输入每条边依附的两个顶点
确定两个顶点的序号i和j，建立边结点
将此边结点分别插入到vi和vj对应的两个边链表的头部

Status CreateUDG(ALGraph &G){
    cin>>G.vexnum>>G.arcnum;    //总顶点数，边数
    for(i = 0;i<G.vexnum;i++){    //输入各点，构造表头结点表
        cin>>G.vertices[i].data;    //输入顶点值
        G.vertices[i].firstarc = NULL;    //初始化表头结点的指针域
    }
    for(k = 0;k<G.arcnum;k++){
        cin>>v1>>v2;    //输入一条边依附的两个顶点
        i = LocateVex(G,v1);
        j = LocateVex(G,v2);
        p1 = nex ArcNode;    //生成一个新的边结点 *p1
        p1 -> adjvex = j;    //邻接点序号为j
        p1 ->nextarc = G.vertices[i].firstarc;
        G.vertices[i].firstarc = p1;    //将新结点*p1插入顶点vi的边表头部
        p2 = nex ArcNode;    //生成另一个对称的新的边结点*p2
        p2 -> adjvex = i;    //邻接点序号为i
        p2 ->nextarc = G.vertices[j].firstarc;
        G.vertices[j].firstarc = p2;    //将新结点*p2插入顶点vj的边表头
    }
    return OK;
}