数据结构-邻接链表

介绍

邻接矩阵是运用较多的一种储存图的方法，但如果一张网图边数较少，就会出现二维矩阵中大部分数据为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;//继续遍历}}}}
}