数据结构之图(三)——邻接表

邻接表表示法(链式)

• 顶点： 按编号顺序将顶点数据存储在一维数组中。
• 关联同一顶点的边： 用线性链表存储。
• 如果有边\弧的信息，还可以在表结点中增加一项，
  

无向图的邻接表

• 例子：
  

• 特点：

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

有向图的邻接表

• 例子：
  

• 邻接表特点：

  • 顶点 $v_i$的出度为第i个单链表中的结点个数。
  • 顶点$v_i$的入度为整个单链表中邻接点域值是i-1的结点个数。
  • 找出度易，找入度难

• 逆邻接表：
  

• 逆邻接表特点：

  • 顶点 $v_i$的入度为第i个单链表中的结点个数。
  • 顶点$v_i$的出度为整个单链表中邻接点域值是i-1的结点个数。
  • 找入度易，找出度难

• 当邻接表的存储结构形成后，图便唯一确定。

建立邻接表的算法

• 图的邻接存储表示
  
• 顶点的存储结构
  
  相应的类型定义如下，

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

• 弧(边)的结点结构
  
  相应的类型定义如下，

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

• 图的结构定义

typedef struct
{
	AdjList vertices;      //存放各个顶点的数组
	int vexnum, arcnum;    //图的当前顶点数和弧数
}ALGraph;

• 邻接表操作举例说明：
  

ALGraph G;                    //定义了邻接表表示的图G
G.vexnum = 5; G.arcnum = 5;   //图G中包含5个顶点，5条边
G.vertices[1].data = 'b';     //图G中的第2个顶点是b
p = G.vertices[1].firstarc;   //指针p指向顶点b的第一条边结点
p->adjvex = 4;                //指针p所指边结点是到下标为4的结点的边

• 采用邻接表表示法创建无向网

  • 算法思想：
    1.输入总顶点数和总边数。
    2.建立顶点表：依次输入点的信息存入顶点表中，使每个表头结点的指针域初始化为NULL。
    3.创建邻接表：
    依次输入每条边依附的两个顶点
    确定两个顶点的序号i和j，建立边结点
    将此边结点分别插入到$v_i$和$v_j$对应的两个边链表的头部

  • 算法描述：

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 = new ArcNode;                      //生成一个新的边结点*p1
		p1->adjvex = j;                        //邻接点序号为j
		p1->nextarc = G.vertices[i].firstarc;  
		G.vertices[i].firstarc = p1;           //将新结点*p1插入顶点vi的边表头部(头插法)
		p2 = new ArcNode;                      //生成一个新的边结点*p2
		p2->adjvex = i;                        //邻接点序号为i
		p2->nextarc = G.vertices[j].firstarc;
		G.vertices[j].firstarc = p2;           //将新结点*p2插入顶点vj的边表头部(头插法)
	}
	return OK;
}

邻接表表示法的优缺点

• 优点：
  • 方便找任一顶点的所有“邻接点”
  • 节约稀疏图的空间：需要N个头指针+2E个结点(每个结点至少2个域)
  • 对无向图而言，方便计算任一顶点的度
• 缺点：
  • 对有向图而言，只能计算“出度”，需要构造“逆邻接表”来方便计算“入度”。

邻接矩阵与邻接表表示法的关系

• 联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。
  

• 区别：

  • 对于任一确定的无向图，邻接矩阵是唯一的(行列号与顶点编号一致)，但邻接表不唯一(链接次序与顶点编号无关)。
  • 邻接矩阵的空间复杂度为$O(n^2)$，而邻接表的空间复杂度为$O(n+e)$。

• 用途：邻接矩阵多用于稠密图；而邻接表多用于稀疏图。