$\Huge\color{orchid}{点击此处获取更多干货}$

DFS和BFS的原理

DFS（深度优先搜索）是从一个节点开始，以深度为准则，一直沿着可以走的边（终点未被访问过）走下去，直到不能再走，就沿着来时的路一直回溯上去，直到发现了另外一条能走的边，一直循环往复这个过程，直到每个节点都被访问过。总结就是“递归下去，回溯上来”，非常适用递归算法

BFS（广度优先搜索）是以广度为准则，从一个节点开始，取得其后继的所有未访问节点，加入一个访问队列，然后挨个取出队列并访问这些节点，一样是把这些节点的后继加入到这个访问队列中，一直到访问队列空了为止。比较适用迭代算法

在不同存储方式上的实现

邻接矩阵：

void MGraph::dfs(size_t node) {
    //访问节点

    vis[node] = true;//标记
    for (int i = 0; i < numVex; i++) {
        //邻接矩阵中的值大于0就说明两个节点之间有边
        if (mat[node][i] > 0 && !vis[i]) {
            dfs(i);//递归
        }
    }
    //视情况而定要不要回溯
}

void MGraph::bfs(size_t node)
{
    queue<size_t> q;
    q.push(node);
    while (!q.empty()) {
        size_t cur = q.front();
        q.pop();
        //访问节点

        vis[cur] = true;
        //检查所有后继，没访问就加入
        for (int i = 0; i < numVex; i++) {
            if (mat[cur][i] > 0 && !vis[cur]) {
                q.push(i);
            }
        }
    }
}

邻接表：

void ALGraph::dfs(size_t cur) {
    //访问节点

    vis[cur] = true;
    for (auto& edge : adjList[cur]) {
        size_t nx = edge.nxt;
        if (!vis[nx]) {
            dfs(nx);
        }
    }
}

void ALGraph::bfs(size_t node) {
    queue<size_t> q;
    q.push(node);
    while (!q.empty()) {
        size_t cur = q.front();
        q.pop();
        //访问节点

        vis[cur] = true;
        for (auto& edge : adjList[cur]) {
            size_t nx = edge.nxt;
            if (!vis[nx]) {
                q.push(nx);
            }
        }
    }
}

链式前向星：

void LinkGraph::dfs(size_t cur) {
    //访问节点

    vis[cur] = true;
    //前向访问所有后继边
    for(size_t i = last[cur];i != 0; i = prev[i]) {
        size_t nx = fin[i];
        if (!vis[nx]) {
            dfs(nx);
        }
    }
}

void LinkGraph::bfs(size_t node) {
    queue<size_t> q;
    q.push(node);
    while (!q.empty()) {
        size_t cur = q.front();
        q.pop();
        //访问节点

        vis[cur] = true;
        for (size_t i = last[cur]; i != 0; i = prev[i]) {
            size_t nx = fin[i];
            if (!vis[nx]) {
                q.push(nx);
            }
        }
    }
}