图的DFS模板-邻接表存储

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

// 图的深度优先遍历

// n-图的点数 m-图的边数
int n,m;

// 邻接表存储图-顶点表head[id]和边表Node分别存储顶点id和与id连接的所有边
struct Node {
    int id;
    Node* next;
    Node(int _id):id(_id),next(NULL) {} // 构造函数方便初始化
} *head[N];

// 添加有向边a->b 实际上就是往a的边表里加入顶点b
void add(int a,int b) {
    auto p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

// st[id]表示顶点id是否已经访问过了
bool st[N];

// 从编号u的顶点开始dfs
void dfs(int u) {
    st[u] = true;
    printf("%d ",u);
    for(auto p = head[u];p;p = p->next) {
        int j = p->id;
        if(!st[j]) dfs(j);
    }
}

int main()
{
    cin >> n >> m;

    while(m --) {
        int a,b;
        cin >> a >> b;
        add(a,b);
    }

    // 为了非连通图这种情况,需要对每个点都要dfs
    for(int i = 1;i <= n;i ++) 
        if(!st[i]) dfs(i);
    return 0;
}

图的BFS模板-邻接表存储

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

// 图的宽度优先遍历

// n-图的点数 m-图的边数
int n,m;

// 邻接表存储图-顶点表head[id]和边表Node分别存储顶点id和与id连接的所有边
struct Node {
    int id;
    Node* next;
    Node(int _id):id(_id),next(NULL) {} // 构造函数方便初始化
} *head[N];

// 添加有向边a->b 实际上就是往a的边表里加入顶点b
void add(int a,int b) {
    auto p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

// st[id]表示顶点id是否已经访问过了
bool st[N];

// 从编号为u的顶点开始bfs
void bfs(int u) {
    // 队列里存储顶点编号
    queue<int> q;
    // 1. 先将顶点u入队并标记u已被访问
    q.push(u);
    st[u] = true;

    // 2.每次队列非空就取出排在队头的顶点
    while(q.size()) {
        auto t = q.front();
        q.pop();

        printf("%d ",t);

        // 3.将与队头顶点相连的顶点都入队,并标记已被访问
        // 所有顶点都被标记访问且队列空时停止bfs
        for(auto p = head[t];p;p = p -> next) {
            int j = p->id;
            if(!st[j]) {
                q.push(j);
                st[j] = true;
            }
        }
    }
}

int main()
{
    cin >> n >> m;

    while(m --) {
        int a,b;
        cin >> a >> b;
        add(a,b);
    }

    // 为了非连通图这种情况,需要对每个点都要bfs
    // 注意求最短路时这个可以不考虑,因为当点不连通时一定不可能是最短路
    for(int i = 1;i <= n;i ++) 
        if(!st[i]) bfs(i);
    return 0;
}