邻接矩阵：BFS实现拓扑排序（实现输入两种格式的图的输入函数）（为什么总是出现RE）（一道题试怎么让一个程序员枯萎的，又是怎么起死回生的）_拓扑排序为什么会卡死

问题描述 :

目的：使用C++模板设计并逐步完善图的邻接矩阵抽象数据类型（ADT）。

内容：（1）请参照图的邻接矩阵模板类原型，设计并逐步完善图的邻接矩阵ADT。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。）

（2）设计并实现一个算法，基于广度优先搜索的思想，对于给定的有向图（网），实现拓扑排序。如排序成功，返回true；否则返回false。无论排序是否成功，都请给出最终的排序结果。图的存储结构采用邻接矩阵。将其加入到ADT中。

注意：DG（有向图）, DN（有向网）, UDG（无向图）, UDN（无向网）

参考函数原型：

（1）重载形式1

//拓扑排序（仅提供拓扑排序是否成功） 

template<class TypeOfVer, class TypeOfEdge>

bool adjmatrix_graph<TypeOfVer, TypeOfEdge>::TopSort();
1
2
3
4
5

（2）重载形式2

//拓扑排序（不仅提供拓扑排序是否成功，排序序列存储在引用参数topsort[]中） 

template<class TypeOfVer, class TypeOfEdge>

bool adjmatrix_graph<TypeOfVer, TypeOfEdge>::TopSort(int &num, int topsort[]);
1
2
3
4
5

输入说明 :

建图的输入数据格式参见建图的算法说明。（以有向图为例，调用重载形式2的函数）

第一行：图的类型

第二行：结点数

第三行：结点集

第四行：边数

第五行：边集

输出说明 :

第一行：顶点集

空行

第二行：邻接表

空行

第三行：拓扑排序结果

第四行：true（排序成功）/false（排序失败）

输入范例 :

DG
8
A B C D E F G H
10
0 2
0 6
1 6
1 7
2 3
3 4
3 6
5 4
6 5
7 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14

输出范例 :

A B C D E F G H

0 0 1 0 0 0 1 0 
0 0 0 0 0 0 1 1 
0 0 0 1 0 0 0 0 
0 0 0 0 1 0 1 0 
0 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 1 0 0 

A->B->C->H->D->G->F->E
1
2
3
4
5
6
7
8
9
10
11
12

true

思路分析

基本知识

拓扑排序的方法：

1. 输入AOV网络，领n为顶点个数
2. 在AOV网络中选取一个没有直接前驱的顶点，并输出之
3. 从图中删去该顶点，同时删除去所有他发出的有向边
4. 重复2、3两步，直到
   • 全部顶点均以输出，拓扑结构有序序列形成
   • 图中还有没有输出的顶点，已经跳出循环处理，还有剩余的顶点

实现的关键

• 查找没有前驱的顶点==》》入度为零的顶点
• 删除顶点以及以它为尾的==》》弧头顶点的入度减一
• 实现删除对应的顶点==》》设计一个表示各个结点度的数组
• 总的想法：设计一个保存各个结点的度的数组，通过邻接矩阵生成数组，删除结点就修改对应的数组，输出就表示为-1，如果如果没有

实现伪码

/*
    描述：拓扑排序（不仅提供拓扑排序是否成功，排序序列存储在引用参数topsort[]中）
    参数：num是拓扑序列中的点的个数
          topsort是保存拓扑序列的数组
*/
bool TopSort(int &num, int topsort[]){

    //如果是无向图直接输出
    if(GraphKind == "UDG" || GraphKind == "UDN") return false;

    //生成表示各个结点度的数组，并初始化
    int degree[Vers]={0} ;

    //统计各个顶点的度
    for(int i = 0;i < Vers;i ++)
    {
        for(int j = 0;j < Vers;j ++)
        {
            if(edge[i][j] != noEdge){
                degree[j] ++;
            }
        }
    }

    //生成用于遍历数组的度
    SqQueue<int> temp;

    //遍历整个数组，找度为0的点入队
    for(int i = 0;i < Vers;i ++)
    {
        if(degree[i] == 0){
            temp.enQueue(i);
            degree[i] = -1;
        }
    }

    //开始遍历
    int mid,j = 0; //临时值，用来保存出队的点
    while(!temp.QueueisEmpty()){

        //出队
        temp.deQueue(mid);
        topsort[j] = mid;
        j ++;
        num ++;
        //遍历对应的矩阵列，将对应的度数都减去
        for(int i = 0; i < Vers; i ++) {
            if(edge[mid][i] != noEdge) {
                degree[i] --;
                if(degree[i] == 0) {
                    temp.enQueue(i);
                    degree[i] = -1;
                }
            }
        }
    }
    
    //遍历完比，就检查是否还有大于零的项
    if(num<Vers) {
        return false;
    }

    return true;

}
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

• 我是觉得如果在这里用ADT的话，会增加很多次不必要的循环，应当不在可以渐变的地方进行简化，每用一次ADT中的封装的方法，都会增加完整的一次遍历时间，造成更多的时间，最终导致超出运行时间

事故现场

第一次提交

• 运行时长超过上限，而且出现了很多的错误

第二次提交

• 删除了一些注释，不重要的句子，确实有点改进

第三、四次提交

• 没有任何的改进，在继续删除
• 是因为没有将申请的内存进行释放，degree是对应保存各个顶点的度的数组，没有清空
  

第7，8，9，10，11次提交

• 只是局部的有问题，我已经优化过了，去除了不必要的循环，同时释放了所有的申请的内存。
• 直接看样例
  
• 没有回路是不需要输出的，否则会发生越界访问
• 修改如下

第12次提交

• 这次有点崩溃了，直接看样例吧
  
• 即使为false，也是有局部输出的，害，又白浪费一个样例

第13次提交

第31次提交

• 我觉得吧，我还是看样例吧

• 这就有点懵了

• 要能够容纳两种格式的输入，关于main函数就得废老劲了。为了节省时间，直接放出来测试函数

int main() {

    //设定图的类型
    string gk;
    getline(cin,gk);

    //设定结点的个数
    int vertexNum = 0;
    cin>>vertexNum;

    //获取对应的结点值
    string vertex[vertexNum];
    for(int i = 0;i < vertexNum;i ++)
    {
        cin>>vertex[i];
    }

    //获取终结标志
    int noEdgeFlag=0;
    if(gk == "DN" || gk == "UDN") {
        cin>>noEdgeFlag;
    }

    //获取边的数量
    int edgeNum;
    cin>>edgeNum;

    //获取边的位置
    int *edge[edgeNum];
    for(int i = 0; i< edgeNum;i ++){
        edge[i] = new  int[2];
    }
    for(int i = 0;i < edgeNum;i ++)
    {
        cin>>edge[i][0];
        cin>>edge[i][1];
    }

    int weight[edgeNum];
    if(gk == "DN" || gk == "UDN") {
        //获取权值数组
        for(int i = 0; i < edgeNum; i ++) {
            cin>>weight[i];
        }
    }

    int num = 0;
    int sortNum[vertexNum];
    bool flag = true;

    if(gk == "DG" || gk == "UDG") {
        //无向图的创建
        adjmatrix_graph<string,int> test1(gk,vertexNum,edgeNum,vertex,edge);
        test1.print_vertex();
        cout<<endl;
        test1.PrintMatrix();
        cout<<endl;
        flag = test1.TopSort(num,sortNum);
        if(flag) {
            cout<<"true";
        } else {
            cout<<"false";
        }
    } else {
        //创建有向权值图
        adjmatrix_graph<string,int> test2(gk,vertexNum,edgeNum,noEdgeFlag,vertex,edge,weight);
        test2.print_vertex();
        cout<<endl;
        test2.PrintMatrix();
        cout<<endl;
        flag = test2.TopSort(num,sortNum);
        if(flag) {
            cout<<"true";
        } else {
            cout<<"false";
        }
    }
    return 0;
}
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79

第32次提交

• 这绝对是今天最高兴的一天了，小问题，说明离解决问题不远了。

• 买一个样例就可以用好久，既能查看错误样例，又能看自己哪里错了

第33次提交

• 又是格式错误，好累啊

第34次提交

• 卧槽，真的，终于过了，那感觉真的太爽了，真的舒服啊~~~~~~~~

分析总结

为什么老是RE

• 关于内存真的有了很深刻的认识，把我折磨的够呛，主要有以下两点
• 一、如果是函数中临时使用的数组或者内存，不需要长久保存的，没有必要申请动态内存，直接常规的声明一个临时的数组，函数调用结束直接自动释放

• 调用的内存空间，一定要释放，不然会导致，系统的执行时间增加，造成内存溢出
• 二、这可能很简单，但是我反应了老半天才反应过来。if条件中的声明语句，for中声明语句，只是局部变量，在固定的作用域之内有用，除了作用于就没有用了

题目已完，问题犹在

• 虽然解决了，但是还是有很多的问题，上面的代码是经过修改的，自己的机器上可以跑，但是一上OJ准会运行超时，返回RE。即使我释放了内存，仍旧会出现相关的问题。
• 后来不再出现RE，是因为我不在通过main函数进行输出，直接在遍历的时候进行输出的，减少了进一步访问的时间。当然我也怀疑可能是我在外部函数进行访问的时候出现了越界。
• 但是已经丢了很多的样本，而且最终的结果也找不回来了。
  
• 就算退回到能退到最早的版本，居然离奇地顺利通过了。
• 看来以后各种离奇地样例代码也要保存一下

如果不妥，留言或者加扣扣651378276 ，一起商量学习进步，一定知无不言。点个赞，留个言啥的，是最大的鼓励了。