数据结构-邻接链表

介绍

邻接矩阵是运用较多的一种储存图的方法，但如果一张网图边数较少，就会出现二维矩阵中大部分数据为0的情况，浪费储存空间

为了避免空间浪费，也可以采用数组与链表结合的方式来存储图

假设有这样一张图

我们可以先用一个数组来存储顶点；

在每个顶点后面，可以采用链式结构，来记录每个顶点与那些顶点相连，就好比一个车头后面跟着几节代表信息的车厢

如v1这个顶点，就可以采用如图的结构记录连接信息

   这种存储了一个网图信息的链表集合就称为邻接链表

创建

结构体定义如下

#define MAX 100
//“车厢”部分
typedef struct edge{
	int adjvex;//邻接点域，用于储存该顶点对应下标
	int info;//储存权值
	struct edge* next;//链域，指向下一个邻接点
}edge;
//“车头”部分
typedef struct vex{
	char v;//储存顶点
	edge* first;//边表头指针
}vex,adjlist[MAX];
//储存邻接链表构成的网图信息
typedef struct{
	adjlist al;//顶点
	int numE,numN;//顶点数，边数
}graphAL;

邻接链表的创建

void creat(graphAL* g,int n,int e){//传入邻接链表，顶点数与边数
	g->numE=e;
	g->numN=n;
	for (int i=0;i<n;i++){
		cin>>g->al[i].v;//传入顶点
		g->al[i].first=NULL;//每一个顶点的边表初始化为空
	}
	for (int i=0;i<e;i++){//建立边表
		int v1,v2;
		cin>>v1>>v2;
		//头插法进行插入
		edge* temp1=(edge*)malloc(sizeof(edge));
		temp1->adjvex=v2;
		temp1->next=g->al[v1].first;
		g->al[v1].first=temp1;
		//无向网图需要两个顶点都记录连接信息
		edge* temp2=(edge*)malloc(sizeof(edge));
		temp2->adjvex=v1;
		temp2->next=g->al[v2].first;
		g->al[v2].first=temp2;
	}
}

遍历

与邻接矩阵相似，遍历方式也是主要有BFS与DFS两种

DFS遍历法

void dfs(graphAL g,int i){
	edge* temp3=g.al[i].first;//记录头结点
	book[i]=false;//标记已经遍历过的节点
	while(temp3){
		if (book[temp3->adjvex]) dfs(g,temp3->adjvex);
		temp3=temp3->next;//继续遍历
	}
}

需要用到标记数组

bool book[MAX];
for (int i=0;i<g.numN;i++){
	book[i]=true;
}
for (int i=0;i<g.numN;i++){
	if (book[i]) dfs(g,l);
}

BFS遍历法

void bfs(graphAL g){
	for (int i=0;i<g.numN;i++){
		book[i]=true;
	}
	deque <int>q;
	for (int i=0;i<g.numN;i++){
		if (book[i]){
			book[i]=false;
			q.push_back(i);//将顶点入队
			while(!q.empty()){
				int t=q.front();
				q.pop_front();//将队首出队
				edge* temp4=g.al[t].first;
				while(temp4){//将与队首相连的入队
					if (book[temp4->adjvex]){
						book[temp4->adjvex]=false;
						q.push_back(temp4->adjvex);//将此顶点入队
					}
					temp4=temp4->next;//继续遍历
				}
			}
		}
	}
}