进阶数据结构——链式前向星

前言

链式前向星是一种进阶的数据结构，主要用于图的存储。
我希望大家先看这个视频（蓝色字体点进去）不然你很难理解的。
在这里插入图片描述

一、背景与定义

在图论中，图的存储方式主要有邻接矩阵和邻接表两种。邻接矩阵虽然建图简单方便，但占内存较大，节点数量稍微大点的题目就难以使用（适合稠密图）；而邻接表虽然节省空间，但其指针形式难写易错，且vector形式的读取速度较慢，易导致大数据下的超时（TLE）。针对上述问题，链式前向星作为一种折中的方式应运而生。

链式前向星本质上是一种静态链表，它将数据以链表形式连接在一起。具体来说，链式前向星存储的是以每个点为起点的所有边。

二、实现思路

头节点数组：建立head[maxn]数组，其中head[id]表示以id节点为起点的第一条边的编号，即查询以该节点为起点的所有边的开始边（链表头部）。head数组一般初始化为-1，表示无边可连。
边结构体：定义一个结构体Node来存储每条边的信息，包括终点to、连在同一起点上的下一条边的编号next以及边权值v（或flag，根据具体需求而定）。

struct Node {int to, next, v; // 或 int to, next, flag;
};

加边函数：通过加边函数将边添加到链表中。每次添加边时，都会更新head数组和Node结构体中的next指针。

void AddEdge(int a, int b, int c) {node[tot].next = head[a];node[tot].to = b;node[tot].v = c; // 或 node[tot].flag = c;head[a] = tot++;
}

三、特点与优势

节省空间：与邻接矩阵相比，链式前向星只存储存在的边，因此更加节省空间。
快速访问：通过头节点数组可以快速访问以某个点为起点的所有边。
避免排序：与需要排序的前向星相比，链式前向星可以避免排序操作，从而节省时间。

四、遍历与应用

在遍历以某个点为起点的所有边时，可以使用以下代码：

for (int i = head[u]; ~i; i = node[i].next) {// 访问以u为起点的边node[i]
}

链式前向星在图论算法中有广泛应用，如最短路算法、拓扑排序、强连通分量等。特别是在处理大规模稀疏图时，链式前向星能够显著提高算法的效率。

五、注意事项

初始化：在使用链式前向星之前，需要正确初始化头节点数组和边结构体数组。
边编号：在添加边时，需要确保每条边都有一个唯一的编号（通常通过全局变量tot来管理）。
遍历顺序：由于链式前向星是逆序存储边的（即后添加的边先被遍历），因此需要注意遍历顺序是否符合题目要求。如果需要按输入顺序遍历边，可以考虑使用其他数据结构或算法来实现。

六、代码模版（c++）

#include<iostream>
#include<vector>
using namespace std;template<typename T>
struct Edge {int to;T weight;int next;
};template<class T>
class Graph {
private:vector<Edge<T>>m_edges;vector<int>m_head;
public:Graph(int n);void addEdges(int from, int to, T weight);void printEdges();
};template<class T>
Graph<T>::Graph(int n){m_edges.clear();m_head.resize(n, -1);
}template<class T>
void Graph<T>::addEdges(int from, int to, T weight){m_edges.push_back(Edge<T>{to, weight, m_head[from]});m_head[from] = (int)m_edges.size() - 1;
}template<class T>
void Graph<T>::printEdges(){int n = m_head.size();for (int i = 0; i < n; i++) {cout << i << ":";for (int e = m_head[i]; e != -1; e = m_edges[e].next) {int v = m_edges[e].to;T w = m_edges[e].weight;cout << "(" << v << "," << w << ")";}cout << endl;}
}int main() {int n, m;cin >> n >> m;Graph<int>g(n);while (m--) {int u, v, w;cin >> u >> v >> w;g.addEdges(u, v, w);}g.printEdges();return 0;
}

七、经典例题

1.金苹果群岛的建设

#include<iostream>
#include<vector>
using namespace std;template<typename T>
struct Edge {int to;T weight;int next;
};template<class T>
class Graph {
private:vector<int>m_head;vector<Edge<T>>m_edges;int m_count;			//代表连通分量的个数vector<int>m_colors;	//代表该点是否与其他点连通，染色法void dfs(int u);		//代表与u这个点直接间接连通的点染色
public:Graph(int n);void addEdges(int from, int to, T weight);void printEdges();int countConnectedBlock();		//统计连通分量的的个数
};template<class T>
Graph<T>::Graph(int n) {m_edges.clear();m_head.resize(n, -1);
}template<class T>
void Graph<T>::addEdges(int from, int to, T weight) {m_edges.push_back(Edge<T>{to, weight, m_head[from]});m_head[from] = m_edges.size() - 1;
}template<class T>
void Graph<T>::printEdges() {for (int i = 0; i < m_head.size(); i++) {cout << i << ":";for (int e = m_head[i]; e != -1; e = m_edges[e].next) {cout << "(" << m_edges[e].to << "," << m_edges[e].weight << ")";}cout << endl;}
}template<class T>
int Graph<T>::countConnectedBlock() {int n = m_head.size();m_count = 0;m_colors.resize(n, -1);for (int i = 0; i < n; i++) {if (m_colors[i] == -1) {dfs(i);m_count++;}}return m_count;
}template<class T>
void Graph<T>::dfs(int u) {if (m_colors[u] != -1)return;m_colors[u] = m_count;for (int e = m_head[u]; e != -1; e = m_edges[e].next) {dfs(m_edges[e].to);}
}int main() {int n, m;cin >> n >> m;Graph<int> g(n);while (m--) {int u, v;cin >> u >> v;u--, v--;g.addEdges(u, v, 0);g.addEdges(v, u, 0);}cout << g.countConnectedBlock() - 1 << endl;	//这里要好好理解，假定n个连通分量代表一个定点若要将n个点//连通就是加上n-1条边return 0;
}

2.图的遍历（简单版）

#include<iostream>
#include<vector>
using namespace std;template<typename T>
struct Edge {int to;T weight;int next;
};template<class T>
class Graph {
private:vector<int>m_head;vector<Edge<T>>m_edges;vector<bool> m_visited;		//用来判断定点是否被访问void dfs(int u, int& ans);
public:Graph(int n);void addEdges(int from, int to, T weight);void printEdges();int calculateColor(int u);
};template<class T>
Graph<T>::Graph(int n) {m_edges.clear();m_head.resize(n, -1);
}template<class T>
void Graph<T>::addEdges(int from, int to, T weight) {m_edges.push_back(Edge<T>{to, weight, m_head[from]});m_head[from] = m_edges.size() - 1;
}template<class T>
void Graph<T>::printEdges() {for (int i = 0; i < m_head.size(); i++) {cout << i << ":";for (int e = m_head[i]; e != -1; e = m_edges[e].next) {cout << "(" << m_edges[e].to << "," << m_edges[e].weight << ")";}cout << endl;}
}template<class T>
int Graph<T>::calculateColor(int u) {int n = m_head.size();m_visited.resize(n);for (int i = 0; i < n; i++) {m_visited[i] = false;}int ans = u;dfs(u,ans);return ans;
}template<class T>
void Graph<T>::dfs(int u,int& ans) {if (m_visited[u])return;m_visited[u] = true;if (u > ans)ans = u;for (int e = m_head[u]; e != -1; e = m_edges[e].next) {int v = m_edges[e].to;dfs(v, ans);}
}int main() {int n, m;cin >> n >> m;Graph<int> g(n);while (m--) {int u, v;cin >> u >> v;u--, v--;g.addEdges(u, v, 0);}for (int i = 0; i < n; i++) {cout << g.calculateColor(i) + 1 << " ";}cout << endl;return 0;
}

3.图的遍历

#include<iostream>
#include<vector>
using namespace std;template<typename T>
struct Edge {int to;T weight;int next;
};template<class T>
class Graph {
private:vector<int>m_head;vector<Edge<T>>m_edges;vector<int> m_color;		//用来判断定点是否被访问void dfs(int u, int color);
public:Graph(int n);void addEdges(int from, int to, T weight);void printEdges();void calculateColor();int getColor(int u);
};template<class T>
Graph<T>::Graph(int n) {m_edges.clear();m_head.resize(n, -1);
}template<class T>
void Graph<T>::addEdges(int from, int to, T weight) {m_edges.push_back(Edge<T>{to, weight, m_head[from]});m_head[from] = m_edges.size() - 1;
}template<class T>
void Graph<T>::printEdges() {for (int i = 0; i < m_head.size(); i++) {cout << i << ":";for (int e = m_head[i]; e != -1; e = m_edges[e].next) {cout << "(" << m_edges[e].to << "," << m_edges[e].weight << ")";}cout << endl;}
}template<class T>
void Graph<T>::calculateColor() {int n = m_head.size();m_color.resize(n, -1);for (int i = n - 1; i >= 0; i--) {		//从序号大的定点开始染色，与大的顶点连通的点它们到达的最大点就是这个点dfs(i, i);}
}template<class T>
int Graph<T>::getColor(int u) {return m_color[u];
}template<class T>
void Graph<T>::dfs(int u,int color) {if (m_color[u] != -1)return;m_color[u] = color;for (int e = m_head[u]; e != -1; e = m_edges[e].next) {int v = m_edges[e].to;dfs(v, color);		//全都是连通最大定点的染色值}
}int main() {int n, m;cin >> n >> m;Graph<int> g(n);while (m--) {int u, v;cin >> u >> v;u--, v--;g.addEdges(v, u, 0);	//这里是v到u构建一张返图，比如1->2->3,变成3->2->1}g.calculateColor();for (int i = 0; i < n; i++) {cout << g.getColor(i) + 1 << " ";}cout << endl;return 0;
}