6-3图-邻接表

邻接表

回顾：
邻接矩阵：数组实现的顺序存储，空间复杂度高，不适合存储稀疏图

一.基本概念
邻接表：顺序+链式存储

第一行：A指向123三个顶点，对应BCD三个顶点（123顺序可交换，故邻接表的表示形式不唯一）
第二行：B指向AEF三个顶点
…
在这里插入图片描述

1.边/弧

typedef struct ArcNode {
	int adjvex;//指向的结点（边）
	struct ArcNode *next;//指向结点的指针
	//InfoType info;  //边权值
}ArcNode;

2.顶点
在这里插入图片描述

typedef char VertexType；
typedef struct VNode {
	VertexType data;//当前结点的数据
	ArcNode *first;//指向的第一个结点
}VNode,AdjList[MaxVertexNum];
//用AdjList[MaxVertexNum]存储各个顶点的信息，包括data和*first

3.用邻接表存储的图

typedef struct {
	AdjList vertices;//定义顶点数组
	int vexnum, arcnum;//结点数和边数
}ALGraph;

【练习】
设计一个算法将无向图的邻接矩阵转为对应的邻接表的算法

思路：双层for循环按行遍历邻接矩阵，依次处理每个结点。对于每个结点的处理，找到1后记录所连的边（分别处理两次），采用头插法插入到邻接表中

代码实现（仅供参考）

#include <corecrt_malloc.h>
//邻接矩阵
#define MaxVertexNum 100
typedef struct {
	int Vex[MaxVertexNum];
	int Edge[MaxVertexNum][MaxVertexNum];
	int vexnum, arcnum;
}MGraph;

//邻接表
typedef struct ArcNode {//邻接表ArcNode
	int adjvex;
	struct ArcNode* next;
}ArcNode;

typedef struct {//data和first的数组表AdjList
	char data;
	ArcNode* first;
}VNode,AdjList[MaxVertexNum];

typedef struct {//暂不需要，可不写
	AdjList vertices;
	int vexnum, arcnum;
}ALGraph;

void change(MGraph g1[], AdjList g2[]) {
//g1为邻接矩阵MGraph，g2为邻接表数组AdjList
	int i, j;//用于双层for循环
	ArcNode* p;//指向待插入结点
	int n = g1->vexnum;//n表示总结点数，用于for循环遍历邻接矩阵
	for (i = 0; i < n; i++)//将邻接矩阵的first指针域置空
		g2[i]->first = 0;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			if (g1->Edge[i][j] == 1) {//找到1
				p = (ArcNode*)malloc(sizeof(ArcNode));//建立新结点，p指向
				p->adjvex = j;//p赋值为要指向的边（如1→5，p指向新结点5）
				//头插法建立
				p->next = g2[i]->first;
				g2[i]->first = p;
				
				//处理反向边（如1←5），同上
				p = (ArcNode*)malloc(sizeof(ArcNode));
				p->adjvex = i;
				p->next = g2[j]->first;
				g2[j]->first = p;
			}
}

二.性质
（1）无向图
邻接表第一行A到B一条边
邻接表第二行B到A一条边
相同边重复计算两次
故：边结点的数量是2|E|
整体空间复杂度O(|V|+2|E|)

概念：
顶点结点：由顶点域和指向第一条邻接边的指针域构成
边结点：由邻接点域和指向下一跳邻接边的指针域构成

（1.1）度
看邻接表第一行：A的度为A相连的BCD，度为3
在这里插入图片描述
（2）有向图
无重复计算
边结点的数量是|E|
整体空间复杂度O(|V|+|E|)
（2.1）度
E的出度=2（E到1、E到2）
A的入度=2（C到0，D到0）
度=入度+出度
E的度=2
A的度=3

（3）综合对比

【逆邻接表】

邻接表一行表示该顶点的指出
逆邻接表一行表示该顶点的指入
在这里插入图片描述