图的广度优先遍历 + 拓扑排序(笔记)

广度优先遍历：

模板题

广度优先遍历的大体思路就是：每次扩展当前一步能到达的未标记的点加入队列中并标记，每次也从队列中拿出一个点进行扩展。

该题是让求最权值都相等的短路我们就可以利用广度优先搜索来求。

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const ll maxn = 1e6 + 5;
//book用来标记哪些点走过了
int idx,h[maxn],e[maxn],nex[maxn],book[maxn];
int n,m,a,b;
//插入函数
void add(int a,int b)
{
    e[idx] = b;
    nex[idx] = h[a];
    h[a] = idx++;
}
int bfs()
{
    queue<int> qu;
    //加入节点1
    qu.push(1);
    int temp;
    //标记节点1
    book[1] = 1;
    while(qu.size())
    {
    	//取出第队首节点
        temp= qu.front();
        //走到n了就停
        if(temp == n)
            break;
        //扩展下一个节点
        for(int i = h[temp]; i != 0; i = nex[i])
        {
            if(!book[e[i]])
            {
                //距离加一
                book[e[i]] = book[temp] + 1;
                qu.push(e[i]);
            }
        }
        qu.pop();
    }
    return book[n] - 1;
}
int main()
{
    idx = 1;
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        cin >> a >> b;
        add(a,b);
    }
    cout << bfs() << endl;
    return 0;
}

拓扑排序：

题目

先来说什么是拓扑序，假设有一个图G有n个节点，把这个节点按照一定的顺序进行排列，最终使图内任意一条边在这个序列中起点在终点之前。

举个例子：
在这个图中1 2 4 3就是一个拓扑序而1 4 2 3就不是，因为4放在了2的前面而2是通向4的。

在来说一下什么是入度什么是出度入度就是指某一个点被指向的次数，比如上面图的节点3，入度就是2，而出度相反是指出的次数，比如节点2，出度就是1.

接下来就是思路了

思路

1.对于序列的第一个节点一定是没有入度的点，因为没有任何边指向它，所以我们可以把所有没有入度的点加入序列的前面。

2.加入之后，我们再想那么下面应该放什么呢，可以发现接下来的点应该是在刚才加入的节点之后，所以他们应该只能被前面的节点所指，那就好办了，我们可以把刚才那些节点所指向点的入度减一，如果减之后入度为零就加入序列。

3.这样的话我们就又确定了一波节点，我们可以再用这些点重复2的操作如此一来拓扑排序就完成了，我们发现这个过程可以使用一个队列来进行，而最终的结果恰巧也就是排好的这个序列(比较不严谨的说法)。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll maxn = 1e5 + 5;
//e为终点，qu是队列，eg是出度
ll cnt,ne[maxn],endd[maxn],h[maxn],eg[maxn],qu[maxn];
ll a,b,n,m;
void add(ll a, ll b)
{
    endd[cnt] = b;
    ne[cnt] = h[a];
    h[a] = cnt++;
}
int bfs()
{
    int he = 0,ed = -1,next;
    //找出无出度的边
    for(int i = 1; i <= n; i++)
        if(!eg[i])
        //加入队列
            qu[++ed] = i;
    //bfs扩展
    while(he <= ed)
    {
        next = qu[he++];
        for(int i = h[next]; i != 0; i = ne[i])
        {
            //指向的出度减少
            eg[endd[i]]--;
            //出度为零加入队列
            if(!eg[endd[i]])
                qu[++ed] = endd[i];
        }
    }
    //全部遍历就存在拓扑序返回1
    if(he == n)
        return 1;
    else
    {
        cout << ed << endl;
        return 0;
    }
}
int main()
{
    cin >> n >> m;
    cnt = 1;
    for(int i = 0; i < m; i++)
    {
        cin >> a >> b;
        add(a,b);
        //记录出度
        eg[b]++;
    }
    if(bfs())
    {
        //数组qu模拟队列剩下的就是拓扑序列了
        for(int i = 0; i < n; i++)
            cout << qu[i] << " ";
        cout << endl;
    }
    else
        cout << -1 << endl;
    return 0;
}