一、引言
在信息学奥赛 CSP - J 的备考过程中，到了第5个月的冲刺阶段，图论算法是一个重要的部分。而邻接表作为存储图的一种有效方式，我们需要深入理解和掌握。
二、邻接表的基本概念
- 结构体数组 + 动态数组存储图的原理
- 结构体数组：我们可以定义一个结构体来表示图中的节点。这个结构体中通常包含节点自身的标识（比如节点编号），以及指向与该节点相邻节点的指针或者索引数组等信息。例如，在C++中：
struct Node { int id; // 节点编号 vector<int> neighbors; // 存储相邻节点的编号，这里使用动态数组vector }; - 动态数组：使用动态数组（如C++中的vector）的好处是它可以根据实际需要灵活调整大小。当我们添加边时，可以方便地将相邻节点的编号添加到对应的节点的neighbors数组中。
- 初始化的重要性
- 在开始构建邻接表之前，必须对结构体数组和相关变量进行正确的初始化。例如，如果我们要创建一个有n个节点的图，我们需要初始化结构体数组的大小为n，并且将每个节点的neighbors数组初始化为空。
- 在C++中，可以这样初始化：
const int n = 100; // 假设图最多有100个节点 Node graph[n]; for (int i = 0; i < n; ++i) { graph[i].id = i; graph[i].neighbors.clear(); } - 如果不进行初始化，可能会导致未定义行为，比如访问到随机的内存地址，从而使程序出错。
三、边的添加方法
- 无向图边的添加
- 对于无向图，当我们要添加一条边连接节点u和节点v时，我们需要在节点u的neighbors数组中添加节点v的编号，同时在节点v的neighbors数组中添加节点u的编号。
- 例如：
void addEdge(int u, int v) { graph[u].neighbors.push_back(v); graph[v].neighbors.push_back(u); }
- 有向图边的添加
- 对于有向图，当添加一条从节点u指向节点v的边时，只需要在节点u的neighbors数组中添加节点v的编号即可。
- 例如：
void addDirectedEdge(int u, int v) { graph[u].neighbors.push_back(v); }
四、边的遍历方法
- 深度优先搜索（DFS）遍历基于邻接表的图
- 首先从起始节点开始，标记该节点为已访问。然后遍历该节点的所有相邻节点，对于每个未访问的相邻节点，递归地进行DFS操作。
- 以下是一个简单的C++实现示例：
bool visited[n]; void dfs(int node) { visited[node]=true; for (int i = 0; i < graph[node].neighbors.size(); ++i) { int neighbor = graph[node].neighbors[i]; if (!visited[neighbor]) { dfs(neighbor); } } }
- 广度优先搜索（BFS）遍历基于邻接表的图
- 使用队来实现。首先将起始节点入队，标记为已访问。然后不断从队中取出节点，遍历其相邻节点，将未访问的相邻节点入队并标记为已访问。
- 例如：
queue<int> q; void bfs(int start) { q.push(start); visited[start]=true; while (!q.empty()) { int node = q.front(); q.pop(); for (int i = 0; i < graph[node].neighbors.size(); ++i) { int neighbor = graph[node].neighbors[i]; if (!visited[neighbor]) { q.push(neighbor); visited[neighbor]=true; } } } }
五、总结
在图论算法的备考冲刺阶段，邻接表的实现是关键内容。我们不仅要理解其存储图的原理，包括结构体数组和动态数组的使用，更要熟练掌握边的添加与遍历方法，并且深刻认识到初始化的重要性。通过大量的练习来巩固这些知识点，才能在考试中更好地应对图论相关的题目。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
