邻接表

邻接表表示法（链式）
顶点：按编号顺序将顶点数据存储在一维数组中
关联同一顶点的边（以顶点为尾的弧）：用线性链表存储

无向图
特点：①邻接表不唯一
②若无向图中有n个顶点e条边，则其邻接表需要n个头结点和2e个表结点，适宜存储稀疏图
③无向图中顶点vi的度为第i个单链表中的结点数

有向图
特点：①顶点vi的出度为第i个单链表中的结点个数
②顶点vi的入度为整个单链表中邻接点域值是i-1的结点个数

图的邻接表存储表示：
（1）表头
typedef struct VNode{
VexTexType data; //顶点信息
ArcNode firstatc; //指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum]; //AdjList表示邻接表类型
（2）弧（边）的结点结构
#define MVNum 100 //最大顶点数
typedef struct ArcNode{ //边结点
int adjvex; //该边所指向的顶点的位置
struct ArcNode nextarc; //指向下一条边的指针
OtherInfo info; //和边相关的信息
}ArcNode;
（3）图的结构定义
typedef struct{
AdjList vertices; //vertex的复试
int vexnum,arcnum; //图的当前顶点数和弧数
}ALGraph;

采用邻接表表示法创建无向网
算法思想：
（1）输入总顶点数和总边数
（2）建立顶点表
依次输入点的信息存入顶点表中
使每个表头结点的指针域初始化为NULL
（3）创建邻接表
依次输入每条边依附的两个顶点
确定两个顶点的序号i和j，建立边结点
将此结点分别插入到vi和vj对应的两个边链表的头部
算法：
Status CreateUDG(ALGraph &G){ //采用邻接表表示法，创建无向图G
cin>>G,vexnum>>G.arcnum; //输入总顶点数，总边数
for(i=0;icin>>G.vertices[i].data; //输入顶点值
G.vertices[i].firstarc = NULL; //初始化表头结点的指针域
}
for(k=0;kcin>>v1>>v2; //输入一条边依附的两个顶点
i=LocateVex(G,v1);
j=LocateVex(G,v2);
p1=new ArcNode; //生成一个新的边结点p1
p1->adjvex=j; //邻接点序号为j
p1->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p1; //将新结点p2插入到顶点vj的边表头部
}
return OK;
}

邻接表特点：
①方便找任一顶点的所有“邻接点”
②节约稀疏图的空间
③方便计算无向图的任一顶点的度；对有向图只能计算“出度”，需要构造“逆邻接表”（存指向自己的边）来方便计算“入度”
④不方便检查任意一对顶点间是否存在边

邻接矩阵与邻接表表示法的关系：
联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数
区别：①对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）
②邻接矩阵的空间复杂度为O(n2)，而邻接表的空间复杂度为O(n+e)
用途：邻接矩阵多用于稠密图，而邻接表多用于稀疏图