初级数据结构——邻接表

目录

前言

一、定义与结构

二、特点与性质

三、构建方式

四、操作与应用

五、代码模版

六、经典例题

[1.------LCP 07. 传递信息(https://leetcode.cn/problems/chuan-di-xin-xi/description/)](#1.——LCP 07. 传递信息)

代码题解

[2.------547. 省份数量(https://leetcode.cn/problems/number-of-provinces/)](#2.——547. 省份数量)

代码题解

[3.------785. 判断二分图(https://leetcode.cn/problems/is-graph-bipartite/)](#3.——785. 判断二分图)

代码题解

七、总结

结语

前言

上一期我们已经一起学习了邻接矩阵这个数据结构，这一期我们一起学习它的兄弟初级数据结构------邻接表。邻接表是数据结构中用于表示图的一种重要方法，特别适用于稀疏图。以下是对初级数据结构邻接表的详细分析：

一、定义与结构

邻接表是一种数组与链表相结合的存储方式。它由一个一维数组（顶点表）和多个链表（边表或邻接链表）组成。

顶点表：一个一维数组，用于存储图中的顶点信息。数组中的每个元素对应图中的一个顶点，同时包含一个指向该顶点邻接链表的指针（或引用）。

边表（邻接链表）：对于顶点表中的每个顶点，都有一个链表与之对应。链表中存储的是与该顶点相邻的所有顶点。在无向图中，每条边在邻接表中出现两次（两个顶点各指向对方一次）；在有向图中，则只出现一次，表示有向边的方向。

二、特点与性质

空间利用率高：邻接表只需要存储实际存在的边和顶点，因此相对于邻接矩阵（需要存储所有可能的边，即使它们不存在）来说，空间利用率更高。

遍历速度快：在邻接表中，遍历与某顶点相邻的全部顶点时，时间复杂度与顶点的度成正比。对于稀疏图而言，这比邻接矩阵表示法的时间复杂度要低。

灵活性：在邻接表中，可以方便地添加或删除边，同时能够快速地访问某个顶点的所有邻接点。

访问性较差：要确定两个顶点之间是否存在边，需要遍历其中一个顶点的邻接链表，这比邻接矩阵的O(1)时间复杂度要慢。

三、构建方式

初始化顶点表：根据图的顶点数，分配顶点表的空间，并初始化每个顶点的邻接链表为空。

读入边信息：根据图的边信息（对于无向图，每条边读入两次；对于有向图，每条边读入一次），为每个顶点建立相应的邻接链表。

构建邻接链表：对于每条边，创建一个边表结点，并将其插入到对应顶点的邻接链表中。

四、操作与应用

图的遍历：邻接表广泛应用于图的遍历算法中，如深度优先搜索（DFS）和广度优先搜索（BFS）。

最短路径问题：如Dijkstra算法、Bellman-Ford算法等，这些算法可以利用邻接表高效地找到图中任意两点之间的最短路径。

拓扑排序：在拓扑排序中，邻接表可以帮助确定图中顶点的线性顺序，使得对于每一条有向边(u, v)，顶点u在顶点v之前。

关键路径：在项目管理中，邻接表可以用于确定项目的关键路径，即项目中耗时最长的路径。

五、代码模版

cpp

复制代码

#include

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. 传递信息

代码题解

cpp

复制代码

class Solution {//这题就是比较典型的深度优先搜索

vector 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

int v=edges[u][i];

sum+=dfs(v,k-1);

}

return sum;

}

public:

int numWays(int n, vector>& relation, int k) {

N=n;

for(int i=0;i

edges[i].clear();

}

for(int i=0;i

int a=relation[i][0];

int b=relation[i][1];

edges[a].push_back(b);//建表过程

}

return dfs(0,k);

}

};

2.------547. 省份数量

代码题解

cpp

复制代码

class Solution {//这题其实就是让我们求连通分量的个数

vector 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

int v=edges[u][i];

dfs(v);

}

}

public:

int findCircleNum(vector>& isConnected) {

n=isConnected.size();

count=0;

memset(color,false,sizeof(color));

for(int i=0;i

edges[i].clear();

for(int j=0;j

if(isConnected[i][j]){

edges[i].push_back(j);

}

}

}

for(int i=0;i

if(color[i]==false){

dfs(i);

++count;//没访问过的定点就自增一

}

}

return count;

}

};

3.------785. 判断二分图

代码题解

cpp

复制代码

class Solution {//这题半段二分图一个很好的方法，判断改图是否有奇环，就是成环的节点个数为奇数

int color[101];//染色法，将该节点相邻节点全部染色，然后到他相邻的任意节点开始染色，如果发现它相邻的节点被染色过说明存在奇环

public:

bool isBipartite(vector>& graph) {

memset(color,-1,sizeof(color));//所有节点初始化为-1，一开始没有进行任何的染色

int n=graph.size();

while(1){

int u=-1;

for(int i=0;i

if(color[i]==-1){

u=i;

break;

}

}

if(u==-1)break;//所有的点都被染色了就跳出循环

color[u]=0;//将该点进行染色

queueq;

q.push(u);

while(!q.empty()){//广度优先搜索

u=q.front();

q.pop();

for(int i=0;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算法等，所以大家要理解好邻接矩阵和邻接表这两个数据结构，那么我们下期不见不散。

关注我让我们一起学习编程，希望大家能点赞关注支持一下，让我有持续更新的动力，谢谢大家