鄰接矩陣：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();

（2）多載形式2

//拓撲排序（不僅提供拓撲排序是否成功，排序序列存盤在參考引數topsort[]中） 

template<class TypeOfVer, class TypeOfEdge>

bool adjmatrix_graph<TypeOfVer, TypeOfEdge>::TopSort(int &num, int topsort[]);

輸入說明 :

建圖的輸入資料格式參見建圖的演算法說明，（以有向圖為例，呼叫多載形式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

輸出范例 :

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

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;

}

• 我是覺得如果在這里用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;
}

第32次提交

• 這絕對是今天最高興的一天了，小問題，說明離解決問題不遠了，

• 買一個樣例就可以用好久，既能查看錯誤樣例，又能看自己哪里錯了

第33次提交

• 又是格式錯誤，好累啊

第34次提交

• 臥槽，真的，終于過了，那感覺真的太爽了，真的舒服啊~~~~~~~~

分析總結

為什么老是RE

• 關于記憶體真的有了很深刻的認識，把我折磨的夠嗆，主要有以下兩點
• 一、如果是函式中臨時使用的陣列或者記憶體，不需要長久保存的，沒有必要申請動態記憶體，直接常規的宣告一個臨時的陣列，函式呼叫結束直接自動釋放

• 呼叫的記憶體空間，一定要釋放，不然會導致，系統的執行時間增加，造成記憶體溢位
• 二、這可能很簡單，但是我反應了老半天才反應過來，if條件中的宣告陳述句，for中宣告陳述句，只是區域變數，在固定的作用域之內有用，除了作用于就沒有用了

題目已完，問題猶在

• 雖然解決了，但是還是有很多的問題，上面的代碼是經過修改的，自己的機器上可以跑，但是一上OJ準會運行超時，回傳RE，即使我釋放了記憶體，仍舊會出現相關的問題，
• 后來不再出現RE，是因為我不在通過main函式進行輸出，直接在遍歷的時候進行輸出的，減少了進一步訪問的時間，當然我也懷疑可能是我在外部函式進行訪問的時候出現了越界，
• 但是已經丟了很多的樣本，而且最終的結果也找不回來了，
  
• 就算退回到能退到最早的版本，居然離奇地順利通過了，
• 看來以后各種離奇地樣例代碼也要保存一下

如果不妥，留言或者加扣扣651378276 ，一起商量學習進步，一定知無不言，點個贊，留個言啥的，是最大的鼓勵了，