【C++算法基础】#4图是如何存储的:vertor建图方法、BFS、DFS

发布于 2023-06-06  643 次阅读


在计算机中,图的存储方式有很多种,最常用的是邻接矩阵和邻接表。邻接矩阵的适用范围一般很小,我们不考虑这种写法。

本文将讨论对于图的邻接表的建立(通过vector),以及BFS、DFS对图进行遍历。

课程大纲:https://www.eriktse.com/algorithm/1215.html

🎈 作者:Eriktse
🎈 简介:211计算机在读,CCPC全国赛金牌,ICPC区域赛银牌退役选手🏆力争以通俗易懂的方式讲解编程和算法!❤️欢迎关注我,一起交流C++/Python算法。(优质好文持续更新中……)🚀
🎈欢迎加群一起玩耍~QQ群:600240150

邻接表

在学习邻接表之前,需要先了解“出度”及其相关的一些概念(比较简单),可以看下百度百科:https://baike.baidu.com/item/%E5%87%BA%E5%BA%A6

邻接表,就是将一个点的所有出点(邻接点)保存在一个数组中,拓展的过程,也就是遍历这个数组的过程。这个数组我们称为邻接表

下面这个图解释的比较清楚(该图为有向图):

vector建图

上述的“数组”显然是可变长度的,用经典的C数组难以实现,我们可以用*STL中的vector来实现。

不了解vector的同学可以看这篇文章《[C++STL教程]1.vector容器是什么?实用教程来啦!

我们将每个点的所有出点存入对应的vector变长数组中,命名为g[](Graph的意思)。

在拓展的时候,只需要遍历对应的g[]数组即可。

DFS

DFS是深度优先搜索,只需要记住一句话即可:“一条路走到黑”。

其算法精髓就是先往深处走,走完了再回头看。

对应的数据结构是栈,每次从栈顶取出一个点,然后将所有出点推入栈中,完成一次拓展。

BFS

BFS是宽度优先搜索,每次将所有出点放入候选队列,然后小心地试探

其算法精髓就是小步走,尽量不往深处走。

对应的数据结构是队列,每次从队头取出一个点,然后将所有出点推入队列中,完成一次拓展。

以上两种搜索方式,一般都需要在搜索过程中保证“不走重复的点”,否则很容易产生环从而无限循环。所以会使用一个bool vis[]来标记某个点是否走过,如果走过就不走了。但是在树上一般不需要标记,因为树一定没有环。

一般来说,dfs用于求树上问题较多,bfs用于求权值相等的最短路(最少操作次数等)。

本文仅简单讲解图的建立和遍历,下一篇文章讲解搜索。

例题

ETOJ 1021: 树的遍历

链接:http://cdn.oj.eriktse.com/problem.php?id=1021

用两种方法进行遍历即可,这里DFS可以用递归形式,也可以用非递归形式(栈)。注意当层数过深时(比如大于60000层,一般就要考虑用非递归形式)。

递归形式:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 60;

int fa[N];

vector<int> g[N];

void dfs(int x)
{
    cout << x << ' ';
    for(auto &y : g[x])
    {
        if(y == fa[x])continue;
        dfs(y);
    }
}

void bfs(int rt)
{
    queue<int> q;
    q.push(rt);
    while(q.size())
    {
        int x = q.front();q.pop();
        cout << x << ' ';
        for(auto &y : g[x])
        {
            q.push(y);
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;cin >> n;
    for(int i = 2;i <= n; ++ i)
    {
        cin >> fa[i];
        g[fa[i]].push_back(i);
    }

    for(int i = 1;i <= n; ++ i)sort(g[i].begin(), g[i].end());

    dfs(1);
    cout << '\n';
    bfs(1);
    cout << '\n';

    return 0;
}

非递归形式:

需要注意本题需要按照出点编号升序进行拓展,所以栈里面需要倒序推入。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 60;

int fa[N];

vector<int> g[N];

void dfs(int rt)
{
    stack<int> stk;
    stk.push(rt);
    while(stk.size())
    {
        int x = stk.top();stk.pop();
        cout << x << ' ';
        vector<int> vec;
        for(auto &y : g[x])
        {
            vec.emplace_back(y);
        }
        for(int i = (int)vec.size() - 1;i >= 0; -- i)stk.push(vec[i]);
    }
}

void bfs(int rt)
{
    queue<int> q;
    q.push(rt);
    while(q.size())
    {
        int x = q.front();q.pop();
        cout << x << ' ';
        for(auto &y : g[x])
        {
            q.push(y);
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;cin >> n;
    for(int i = 2;i <= n; ++ i)
    {
        cin >> fa[i];
        g[fa[i]].push_back(i);
    }

    for(int i = 1;i <= n; ++ i)sort(g[i].begin(), g[i].end());

    dfs(1);
    cout << '\n';
    bfs(1);
    cout << '\n';

    return 0;
}