c++邻接表实现BFS和DFS

邻接表是一种常用的图存储结构，可以用来实现图的遍历算法。下面是C++实现邻接表的BFS和DFS遍历算法的示例代码：

#include <iostream>
#include <queue>
using namespace std;

const int MAXN = 100;
bool vis[MAXN]; // 记录节点是否被访问过

// 邻接表结构体
struct Edge {
    int to; // 边的终点
    int next; // 指向下一个邻接点的指针
} edges[MAXN * MAXN];
int head[MAXN], cnt; // head[i]表示以i为起点的第一条边的编号，cnt为边数

// 添加一条从u到v的边
void addEdge(int u, int v) {
    edges[++cnt].to = v;
    edges[cnt].next = head[u];
    head[u] = cnt;
}

// BFS遍历
void bfs(int u) {
    queue<int> q;
    q.push(u);
    vis[u] = true;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        cout << x << " ";
        for (int i = head[x]; i; i = edges[i].next) {
            int y = edges[i].to;
            if (!vis[y]) {
                q.push(y);
                vis[y] = true;
            }
        }
    }
}

// DFS遍历
void dfs(int u) {
    vis[u] = true;
    cout << u << " ";
    for (int i = head[u]; i; i = edges[i].next) {
        int v = edges[i].to;
        if (!vis[v]) {
            dfs(v);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m; // n个节点，m条边
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u); // 无向图需要添加反向边
    }
    cout << "BFS遍历结果：";
    bfs(1);
    cout << endl;
    memset(vis, false, sizeof(vis));
    cout << "DFS遍历结果：";
    dfs(1);
    cout << endl;
    return 0;
}

其中，`vis`数组用于记录每个节点是否被访问过，`head`数组用于记录以每个节点为起点的第一条边的编号，`cnt`表示边数。在添加边时，需要同时添加反向边，因为本例中是无向图。BFS遍历使用了队列，DFS遍历使用了递归。