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

本文将讨论对于图的邻接表的建立（通过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;
}