【图论】图的存储与搜索

一、图的存储方式

首先，树是一种特殊的图，因此树的存储类似，这里只记录图的存储。

其次，无向图又是一种特殊的有向图。

无向图中的 a—b 相当于有向图中的 a->b b->a，因此这里只记录有向图的存储。

1、邻接矩阵

简单来说就是开个二维数组g[N][N]。

• 无权图中，g就是个bool值，ab之间有边，则g[a][b] = true， 否则为false。
• 有权图中，g为两条边之间的权重。

出现重边时，邻接矩阵只保留一条边（一般是保留最短的那条）。

空间复杂度O(n^2)，经验来看1e5会爆，只适合存储稠密图，稀疏图用邻接表。

2、邻接表

（1）链式前向星

• h[N]：头结点
• e[N]：头结点可以到达哪些点
• ne[N]：起到指针的作用 表示e[i]的下一个结点是什么位置
• idx：当前存储到了什么位置

链式前向星板子

int h[N], e[N], ne[N], w[N], idx;
// 首先一定要初始化h
memset(h, -1, sizeof h);
void add(int a, int b, int w)
{
    // 加入 a -> b 这条边，权重是w
    e[idx] = b, w[idx] = w, ne[idx] = h[a], h[a] = idx ++ ;
}

（2）vector存二维数组

vector g[N] 的方式来存储。

vector存二维数组板子

vector<int> g[N];
void add(int a, int b)
{
    // 加入 a -> b 这条边
    g[a].pushforward(b);
}

如果需要增加权重，可以考虑把vector换成vector>

---

二、图的搜索与遍历

1、深度优先搜索（DFS）

尽可能往深搜，直到前面没有能继续搜索的点了才会回溯，回溯时也是一边回溯一边看目前回溯到的点有没有能接着往深搜的，直到遍历完整个图。

空间复杂度O(n)，相较于BFS有绝对优势。

深度优先搜索BFS板子

void dfs(int u)
{
    st[u] = true;
    if ( 遍历完毕 )
    {
        cout << 打印所需结果;
        return;
    }
    for ( 遍历整个图 )
    {
        if (!st[i]) // 当前结点未被遍历过
        {
            st[i] = true;
            dfs(i); // 遍历下一层
            // 是否恢复现场依情况而定 如果遍历整个图就不需要恢复现场
            st[i] = false; // 恢复当前结点的遍历情况
        }
    }
}

2、宽度优先搜索（BFS）

按层搜索，每一轮搜索到的点和起始点的距离都是一样的。（比如说第一次搜索到的点距离起始点的长度都是1，第二次搜索到的点距离起始点的长度都是2，以此类推）

正是因为这个特性，BFS可以解决一部分权重为1的最短路问题。

空间复杂度O(2^n)。

宽度优先搜索BFS板子

void bfs()
{
    queue<int> q;
    q.push( 第一个数 );
    while (q.size()) // q不空时
    {
        // 取出队头并删去
        int t = q.front();
        q.pop();
        for ( 遍历与t相邻的点 )
        {
            if (!st[i])
            {
                st[i] = true;
                q.push(i); // 该点没遍历过就把它加到队列中
            }
        }
    }
}

BFS应用实例 — 拓补序列

拓补序列：对于所有有向边 x->y，序列中总存在x在y前面，该序列为拓补序列

换句话说序列中所有边都是从前指向后。

如果一个图存在环，就一定不存在拓补序列。

一个有向无环图一定存在拓补序列，有向无换图又被称作拓补图。

任何一个入度为0的点都可以作为拓补序列的起点

任何一个出度为0的点都可以作为拓补序列的终点

拓补序列板子

void Topsort()
{
    queue<int> q;
    for ( 找到所有入度为0的点i ) q.push(i); // 把入度为0的点存进q
    while (q.size())
    {
        int t = q.front(); // 指向队头
        for ( 枚举t的所有出边 t->j )
        {
            // 删掉t->j这条边 也就是让j的入度-1
            d[j] -- ;
            if (d[j] == 0) q.push(j);
        }
    }
}

---