本文共 3349 字，大约阅读时间需要 11 分钟。
邻接表构造与遍历
在编程中，邻接表是一种常用的数据结构，用于表示图的边。它通过将每个节点的邻接信息存储在表中，使得节点的访问和遍历更加高效。以下将详细介绍如何使用邻接表构造图，并进行遍历操作。
邻接表可以使用数组或向量来模拟。在本文中，我们将分别使用数组和向量两种方式来实现。
假设我们有 N 个节点，我们可以使用一个数组 s 来表示邻接表。每个节点 i 的邻接信息存储在 s[i] 中，具体包括以下结构：
struct st { int to; // 结点编号 int w; // 权值 struct st *nx; // 指向下一个结点};ll *link; // 类型声明s[N]; // 邻接表的表头 初始化时，我们需要为每个节点分配空间，并将其下一个结点指针初始化为 NULL：
for (int i = 1; i <= n; i++) { s[i].next = NULL;} 然后，通过 add 函数添加边。add 函数会为指定的两个节点创建相应的邻接结点：
void add(int from, int to, int w) { link p; p = new ll; p->to = to; p->w = w; p->nx = s[from].next; s[from].next = p;} 这里需要注意，由于 s 是一个数组，我们需要预先分配足够的空间来存储所有节点的邻接信息。
除了数组，向量在现代编程中更为常用，特别是考虑到其动态分配特性。在向量中，我们可以使用结构体 st 来存储每个邻接信息：
#includeusing namespace std;struct st { int to; int w;};vector s[N];
向量的初始化与数组类似，只需为每个节点清空邻接表：
for (int i = 1; i <= n; i++) { s[i].clear();} 添加边的逻辑与数组版本一致，只是通过向量的 push_back 方法实现：
void add(int from, int to, int w) { st t; t.to = to; t.w = w; s[from].push_back(t);} 这种方式更加灵活，尤其是当节点数量不确定时。
邻接表的遍历可以通过深度优先搜索（DFS）或广度优先搜索（BFS）来实现。以下分别介绍这两种遍历方法。
DFS通过递归的方式逐层访问节点，直到所有节点都被访问。实现时，可以使用递归函数，并使用一个标记数组 book 来记录已访问的节点：
void dfs(int x) { book[x] = 1; cout << x << " "; link p; p = s[x].next; while (p) { if (book[p->to] == 0) { book[p->to] = 1; dfs(p->to); } p = p->nx; }} 这种方法适用于稀疏图，递归深度较大的情况下可能会导致栈溢出。
BFS通过队列来逐层访问节点，实现时可以使用队列数据结构。以下是 bfs 函数的实现：
void bfs(int x) { link p; int q[N]; int r = 0, f = 0; book[x] = 1; q[r++] = x; while (r != f) { int t = q[f++]; p = s[t].next; while (p) { if (book[p->to] == 0) { book[p->to] = 1; q[r++] = p->to; } p = p->nx; } }} 这种方法在稠密图中表现更好，避免了递归深度的问题。
以下是完整的代码示例，展示了如何构造并遍历邻接表：
#include#include using namespace std;struct st { int to; int w;};vector s[N];void dfs(int x) { book[x] = 1; cout << x << " "; vector ::iterator it; it = s[x].begin(); while (it != s[x].end()) { if (book[it->to] == 0) { book[it->to] = 1; dfs(it->to); } it++; }}void bfs(int x) { int q[n]; int r = 0, f = 0; book[x] = 1; q[r++] = x; while (r != f) { int t = q[f++]; vector current = s[t]; for (int i = 0; i < current.size(); i++) { if (book[current[i].to] == 0) { book[current[i].to] = 1; cout << current[i].to << " "; } q[r++] = current[i].to; } }}void add(int from, int to, int w) { st t; t.to = to; t.w = w; s[from].push_back(t);}int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { s[i].clear(); } for (int i = 1; i <= n - 1; i++) { int x, y, w; scanf("%d %d %d", &x, &y, &w); add(x, y, w); add(y, x, w); } cout << "邻接表" << endl; for (int i = 1; i <= n; i++) { cout << "[" << i << "] "; for (auto p : s[i]) { cout << p.to << " "; } cout << endl; }}
通过上述方法，我们可以轻松构造并遍历邻接表。无论是使用数组还是向量，核心逻辑保持一致，主要区别在于数据结构的选择和使用方式。理解邻接表的构造与遍历是掌握图算法的基础，后续的高级算法如最短路径、连通性检查等都会基于此进行扩展。
转载地址：http://trel.baihongyu.com/