初级数据结构——邻接表
目录
- 前言
- 一、定义与结构
- 二、特点与性质
- 三、构建方式
- 四、操作与应用
- 五、代码模版
- 六、经典例题
- [1.——LCP 07. 传递信息](https://leetcode.cn/problems/chuan-di-xin-xi/description/)
- 代码题解
- [2.——547. 省份数量](https://leetcode.cn/problems/number-of-provinces/)
- 代码题解
- [3.——785. 判断二分图](https://leetcode.cn/problems/is-graph-bipartite/)
- 代码题解
- 七、总结
- 结语
前言
上一期我们已经一起学习了邻接矩阵这个数据结构，这一期我们一起学习它的兄弟初级数据结构——邻接表。邻接表是数据结构中用于表示图的一种重要方法，特别适用于稀疏图。以下是对初级数据结构邻接表的详细分析：
一、定义与结构
邻接表是一种数组与链表相结合的存储方式。它由一个一维数组（顶点表）和多个链表（边表或邻接链表）组成。
顶点表：一个一维数组，用于存储图中的顶点信息。数组中的每个元素对应图中的一个顶点，同时包含一个指向该顶点邻接链表的指针（或引用）。
边表（邻接链表）：对于顶点表中的每个顶点，都有一个链表与之对应。链表中存储的是与该顶点相邻的所有顶点。在无向图中，每条边在邻接表中出现两次（两个顶点各指向对方一次）；在有向图中，则只出现一次，表示有向边的方向。
二、特点与性质
空间利用率高：邻接表只需要存储实际存在的边和顶点，因此相对于邻接矩阵（需要存储所有可能的边，即使它们不存在）来说，空间利用率更高。
遍历速度快：在邻接表中，遍历与某顶点相邻的全部顶点时，时间复杂度与顶点的度成正比。对于稀疏图而言，这比邻接矩阵表示法的时间复杂度要低。
灵活性：在邻接表中，可以方便地添加或删除边，同时能够快速地访问某个顶点的所有邻接点。
访问性较差：要确定两个顶点之间是否存在边，需要遍历其中一个顶点的邻接链表，这比邻接矩阵的O(1)时间复杂度要慢。
三、构建方式
初始化顶点表：根据图的顶点数，分配顶点表的空间，并初始化每个顶点的邻接链表为空。
读入边信息：根据图的边信息（对于无向图，每条边读入两次；对于有向图，每条边读入一次），为每个顶点建立相应的邻接链表。
构建邻接链表：对于每条边，创建一个边表结点，并将其插入到对应顶点的邻接链表中。
四、操作与应用
图的遍历：邻接表广泛应用于图的遍历算法中，如深度优先搜索（DFS）和广度优先搜索（BFS）。
最短路径问题：如Dijkstra算法、Bellman-Ford算法等，这些算法可以利用邻接表高效地找到图中任意两点之间的最短路径。
拓扑排序：在拓扑排序中，邻接表可以帮助确定图中顶点的线性顺序，使得对于每一条有向边(u, v)，顶点u在顶点v之前。
关键路径：在项目管理中，邻接表可以用于确定项目的关键路径，即项目中耗时最长的路径。
五、代码模版
#include<iostream>
using namespace std;
class Graph {
struct EdgeNode//代表每个节点的结构体
{
int vertex;//定点编号
int weight;//另一个点到这个点的权值，就是距离
EdgeNode* next;
};
struct VertexNode {//代表每个链表的结构体
int vertex;//定点编号
EdgeNode* firstEdge;//每个链表的头结点
};
int vertices;//顶点个数，也是链表个数
VertexNode* nodes;
public:
Graph(int vertices);
~Graph();
void addEdge(int u, int v, int w);
void printGraph();
};
Graph::Graph(int vertices) {
this->vertices = vertices;
this->nodes = new VertexNode[vertices];
for (int i = 0; i < vertices; i++) {
nodes[i].vertex = i;
nodes[i].firstEdge = NULL;//初始化每个链表头结点都为空，也就是每个节点都不相连
}
}
Graph::~Graph() {
for (int i = 0; i < vertices; i++) {
EdgeNode* curr = nodes[i].firstEdge;
while (curr) {
EdgeNode* t = curr;
curr = curr->next;
delete t;
}
}
delete[]nodes;
}
void Graph::addEdge(int u, int v, int w) {
EdgeNode* newNode = new EdgeNode;
newNode->vertex = v;
newNode->weight = w;
newNode->next = nodes[u].firstEdge;//将这个节点，用头插法插入链表中
nodes[u].firstEdge = newNode;
}
void Graph::printGraph() {
for (int i = 0; i < vertices; i++) {
EdgeNode* curr = nodes[i].firstEdge;
cout << "Vertex" << i << " ";
while (curr) {
cout << curr->vertex << "(" << curr->weight << ")";
curr = curr->next;
}
cout << endl;
}
}
int main() {
Graph graph(5);
graph.addEdge(0, 1, 4);
graph.addEdge(0, 2, 2);
graph.addEdge(1, 2, 3);
graph.addEdge(2, 3, 4);
graph.addEdge(3, 4, 2);
graph.printGraph();
return 0;
}
六、经典例题
1.——LCP 07. 传递信息
代码题解
class Solution {//这题就是比较典型的深度优先搜索
vector<int> edges[10];
int N;
int dfs(int u,int k){
if(!k)return (u==N-1)?1:0;//k为零的时候就只用判断起始顶点，它也作为递归出口
int sum=0;
for(int i=0;i<edges[u].size();i++){
int v=edges[u][i];
sum+=dfs(v,k-1);
}
return sum;
}
public:
int numWays(int n, vector<vector<int>>& relation, int k) {
N=n;
for(int i=0;i<N;i++){
edges[i].clear();
}
for(int i=0;i<relation.size();i++){
int a=relation[i][0];
int b=relation[i][1];
edges[a].push_back(b);//建表过程
}
return dfs(0,k);
}
};
2.——547. 省份数量
代码题解
class Solution {//这题其实就是让我们求连通分量的个数
vector<int> edges[201];
bool color[201];
int count;
int n;
void dfs(int u){//深度优先搜索把这个定点所在的联通分量的所有顶点都访问过
if(color[u])return;//递归出口，访问过就退出
color[u]=true;//对该节点标记为访问过了
for(int i=0;i<edges[u].size();i++){
int v=edges[u][i];
dfs(v);
}
}
public:
int findCircleNum(vector<vector<int>>& isConnected) {
n=isConnected.size();
count=0;
memset(color,false,sizeof(color));
for(int i=0;i<n;i++){
edges[i].clear();
for(int j=0;j<isConnected.size();j++){
if(isConnected[i][j]){
edges[i].push_back(j);
}
}
}
for(int i=0;i<n;i++){
if(color[i]==false){
dfs(i);
++count;//没访问过的定点就自增一
}
}
return count;
}
};
3.——785. 判断二分图
代码题解
class Solution {//这题半段二分图一个很好的方法，判断改图是否有奇环，就是成环的节点个数为奇数
int color[101];//染色法，将该节点相邻节点全部染色，然后到他相邻的任意节点开始染色，如果发现它相邻的节点被染色过说明存在奇环
public:
bool isBipartite(vector<vector<int>>& graph) {
memset(color,-1,sizeof(color));//所有节点初始化为-1，一开始没有进行任何的染色
int n=graph.size();
while(1){
int u=-1;
for(int i=0;i<n;i++){
if(color[i]==-1){
u=i;
break;
}
}
if(u==-1)break;//所有的点都被染色了就跳出循环
color[u]=0;//将该点进行染色
queue<int>q;
q.push(u);
while(!q.empty()){//广度优先搜索
u=q.front();
q.pop();
for(int i=0;i<graph[u].size();i++){
int v=graph[u][i];
if(color[v]!=-1){//说明被染色过了就不是二分图
if(color[v]==color[u])return false;
}else{
color[v]=1-color[u];//没染过色就标记为染过了
q.push(v);
}
}
}
}
return true;
}
};
七、总结
综上所述，邻接表是图论中一种非常重要的存储结构，它结合了数组和链表的优点，能够高效地表示和处理稀疏图。
结语
下期我们一起来学习最后一个初级数据结构——哈希表，大家坚持住，学完它我们对初级数据结构的学习就告一段落了，然后就是学习比较有难度的算法了，如Dijkstra算法、Bellman-Ford算法等，所以大家要理解好邻接矩阵和邻接表这两个数据结构，那么我们下期不见不散。
关注我让我们一起学习编程，希望大家能点赞关注支持一下，让我有持续更新的动力，谢谢大家
