拓扑排序和BFS的区别_拓扑排序 bfs

拓扑排序和BFS

1. 拓扑排序
2. 拓扑序列和BFS的区别：

只有在有向图才有拓扑序，无向图中是没有拓扑序列的。在图中，只要有环，就不存在拓扑序。可证明，一个有向无环图一定存在一个拓扑序列，也称有向无环图为拓扑图。
拓扑序列是图的有向图中的一个宽度优先遍历的应用。
在题目中遇到dfs+bfs的遍历可以用dfs+bfs来写如：P5318 【深基18.例3】查找文献。
下面这个可以ac，但是发现如果将用bfs的遍历换成用拓扑排序就不能实现。

#include <vector>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
const int N=100010;
int n,m;
int ans;
int in[N];
vector <int >v[N];
int print[N],visit[N];
void dfs(int x)
{
    visit[x]=1;
    printf("%d ",x);

    for(int i=0; i<v[x].size(); i++)
    {
        int xx=v[x][i];
        if(visit[xx]==0)
            dfs(xx);}
    }
void bfs(int x)
{
    memset(visit,0,sizeof(visit));
    queue<int > q;
    q.push(x);
    visit[x]=1;
    while(!q.empty())
    {
        int xx=q.front();
        printf("%d ",xx);q.pop();
        for(int i=0; i<v[xx].size(); i++)
        {
            int yy=v[xx][i];
            if(visit[yy]==0)
            {
                q.push(yy);
                visit[yy]=1;
                }
        }
    }
}

int main()
{
   scanf("%d%d",&n,&m);
    while(m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        in[y]++;

    }
    for(int i=1; i<=n; i++)
    {

        sort(v[i].begin(),v[i].end());

    }
     dfs(1);
    printf("\n");
    bfs(1);}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

看上面这个图好像是感觉用拓扑排序也能过实现，因为题目是说从1开始，我们直接将入度为0的入队，然后将队列顶点的出边给删掉，也就是 1->2，1->3,1->4这三条边可以被删除，然后2 ，3，4也都可以入队，依次再删除它的出边，5,6，7入队，再将8入队，这样看似好像没问题，但实际上用拓扑排序就会被其他数据给卡掉。例如我将bfs的部分改用拓扑排序就只能过第一个点。

void tuopu(int x)
{
    memset(visit,0,sizeof(visit));
    queue<int > q;
    q.push(x);
    visit[x]=1;
    while(!q.empty())
    {
        int xx=q.front();
        printf("%d ",xx);
        q.pop();
        for(int i=0; i<v[xx].size(); i++)
        {
            int yy=v[xx][i];
            in[yy]--;
            if(in[yy]==0&&visit[yy]==0)
            {
                q.push(yy);
                visit[yy]=1;

            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

这样就只能过样例，但不能AC。我感觉很疑惑，但最后我发现：
BFS和拓扑序列的区别：
BFS:只需要与其它点与之相邻（并且没有访问过）就能够入队，而拓扑排序却需要与之相邻的点入度为0（并且没有访问过）才可以入队。
例如：这种情况，就不会被影响。BFS和拓扑排序的队列的数据都是一样的。

可以看到创建邻接表后进行排序，对BFS和拓扑序列的队列数据没有影响都是一样的。因为在这里vector中排序后从小到大对BFS入队这里没有问题，根据图的拓扑序列也是没有问题，首先将1号顶点入队，1号顶点有两条出边，将这两条出边删除后，因为是排序过后所以先将2号顶点入队再将3号顶点入队。这里就和BFS一致了。
但是将图中2号顶点和3号顶点的位置变换后就会发生错误：

可以看到图，首先将1号顶点入队，将1号顶点的两条出边删除后，3号顶点的入度首先变成0，但是2号顶点的入度还是1，所以在这里就先将3号顶点入队了，之后再将2号顶点入队。但BFS队列还是根据升序1 ，2, 3这样入队的。所以在这里就出现了偏差，也就是为什么用BFS可以过，但用拓扑序列却不行的原因。