1.BFS

優(yōu)先訪問最先發(fā)現(xiàn)的節(jié)點(diǎn)，可以根據(jù)FIFO隊列的特點(diǎn)，選用隊列實(shí)現(xiàn)
可以實(shí)現(xiàn)連通域分解和最短路徑等問題。
等同于樹結(jié)構(gòu)中的層次遍歷

//whole graph
template <typename Tv, typename Te>
void Graph<Tv,Te>::bfs(int s){
    reset();
    int clock=0;
    int v=s;
    do 
        if(status(v)==UNDISCOVERED){
            BFS(v,clock);
        }
    while(s!=(v=(++v%n)));
}
//single connection component
template <typename Tv, typename Te>
void Graph<Tv,Te>::BFS( int v, int& clock){
    std::queue<int > Q;
    status(v)=DISCOVERED;
    Q.push(v);
    while(!Q.empty()){
        int v=Q.front();
        Q.pop();
        dTime(v)=++clock;

        for(int u=firstNbr(v) ;-1<u ; u = nextNbr(v , u) ){
            if(status(u)==UNDISCOVERED){
                status(u)=DISCOVERED;
                Q.push(u);
                type(v,u)=TREE;
                parent(u)=v;
            }
            else{
                type(v,u)=CROSS;
            }

        }
    status(v)=VISITED;
    }
}

2.DFS

優(yōu)先選取最后一個被訪問到的頂點(diǎn)的鄰居
于是，以頂點(diǎn)s為基點(diǎn)的DFS搜索，將首先訪問頂點(diǎn)s;再從s所有尚未訪問到的鄰居中任取 其一，并以之為基點(diǎn)，遞歸地執(zhí)行DFS搜索。故各頂點(diǎn)被訪問到的次序，類似于樹的先序遍歷 ;而各頂點(diǎn)被訪問完畢的次序，則類似于樹的后序遍歷

//DFS
template <typename Tv, typename Te>
void Graph<Tv,Te>::dfs(int s){
    reset();
    int clock=0;
    int v=s;
do
{
    if(UNDISCOVERED==status(v)){
        DFS(v,clock);
    }
} while (s!=(v=++v%this->n));

}

template <typename Tv, typename Te>
void Graph<Tv, Te>::DFS(int v, int&clock){
    dTime(v)=++clock;
    status(v)=DISCOVERED;
    for(int u=firstNbr(v);u>-1;u=nextNbr(v,u)){
        if( status(u)==UNDISCOVERED){
            type(v,u)=TREE;
            parent(u)=v;
            DFS(u,clock);
        }
        else if(u==DISCOVERED){
            type(v,u)=BACKWARD;
        }
        else {
            type(v,u)=(dTime(v)<dTime(u))?FORWARD:CROSS;
        }
    }
     status(v)=VISITED;
     fTime(v)=++clock;
}

算法的實(shí)質(zhì)功能，由子算法DFS()遞歸地完成。每一遞歸實(shí)例中，都先將當(dāng)前節(jié)點(diǎn)v標(biāo)記為 DISCOVERED(已發(fā)現(xiàn))狀態(tài)，再逐一核對其各鄰居u的狀態(tài)并做相應(yīng)處理。待其所有鄰居均已處 理完畢之后，將頂點(diǎn)v置為VISITED(訪問完畢)狀態(tài)，便可回溯。

若頂點(diǎn)u尚處于UNDISCOVERED(未發(fā)現(xiàn))狀態(tài)，則將邊(v, u)歸類為樹邊(tree edge)，并將v記作u的父節(jié)點(diǎn)。此后，便可將u作為當(dāng)前頂點(diǎn)，繼續(xù)遞歸地遍歷。 若頂點(diǎn)u處于DISCOVERED狀態(tài)，則意味著在此處發(fā)現(xiàn)一個有向環(huán)路。此時，在DFS遍歷樹中u必為v的祖先，故應(yīng)將邊(v, u)歸類為后向邊(back edge)。 這里為每個頂點(diǎn)v都記錄了被發(fā)現(xiàn)的和訪問完成的時刻，對應(yīng)的時間區(qū)間[dTime(v), fTime(v)]均稱作v的活躍期(active duration)。實(shí)際上，任意頂點(diǎn)v和u之間是否存在祖先-后代的“血緣”關(guān)系，完全取決于二者的活躍期是否相互包含。

對于有向圖，頂點(diǎn)u還可能處于VISITED狀態(tài)。此時，只要比對v與u的活躍期，即可判定在 DFS樹中v是否為u的祖先。若是，則邊(v, u)應(yīng)歸類為前向邊(forward edge);否則，二者必然來自相互獨(dú)立的兩個分支，邊(v, u)應(yīng)歸類為跨邊(cross edge)。

DFS(s)返回后，所有訪問過的頂點(diǎn)通過parent[]指針依次聯(lián)接，從整體上給出了頂點(diǎn)s所屬連通或可達(dá)分量的一棵遍歷樹，稱作深度優(yōu)先搜索樹或DFS樹(DFS tree)。與BFS搜索一樣， 此時若還有其它的連通或可達(dá)分量，則可以其中任何頂點(diǎn)為基點(diǎn)，再次啟動DFS搜索。
最終，經(jīng)各次DFS搜索生成的一系列DFS樹，構(gòu)成了DFS森林(DFS forest)

應(yīng)用：拓?fù)渑判?/h4>

有向無環(huán)圖一定有拓?fù)渑判?br> 1.入度為零法
考察圖G，尋找入度為0的頂點(diǎn)，去掉后刪除相關(guān)邊，再找下一個入度為零點(diǎn)。直到僅剩一個頂點(diǎn)。
2.VISITED順序的倒序即是一個拓?fù)渑判?br> 同理，有限偏序集中也必然存在極小元素(同樣，未必唯一)。該元素作為頂點(diǎn)，出度必然 為零。 而在對有向無環(huán)圖的DFS搜索中，首先因訪問完成而轉(zhuǎn) 換至VISITED狀態(tài)的頂點(diǎn)m，也必然具有這一性質(zhì);反之亦然。

進(jìn)一步地，根據(jù)DFS搜索的特性，頂點(diǎn)m(及其關(guān)聯(lián)邊)對此后的搜索過程將不起任何作用。 于是，下一轉(zhuǎn)換至VISITED狀態(tài)的頂點(diǎn)可等效地理解為是，從圖中剔除頂點(diǎn)m(及其關(guān)聯(lián)邊)之 后的出度為零者??在拓?fù)渑判蛑?，該頂點(diǎn)應(yīng)為頂點(diǎn)m的前驅(qū)。由此可見，DFS搜索過程中各頂 點(diǎn)被標(biāo)記為VISITED的次序，恰好(按逆序)給出了原圖的一個拓?fù)渑判颉?/p>

此外，DFS搜索善于檢測環(huán)路的特性，恰好可以用來判別輸入是否為有向無環(huán)圖。具體地， 搜索過程中一旦發(fā)現(xiàn)后向邊，即可終止算法并報告“因非DAG而無法拓?fù)渑判颉薄?/p>

template <typename Tv, typename Te>
std::stack<Tv>* Graph<Tv,Te>::tSort(int s){
    reset();
    int clock=0;
    int v=s;
    std::stack<Tv> S=new std::stack<Tv>;
    do
    {
        if(status(v)==UNDISCOVERED){
            //topoogy sort and break&clear the stack
            if(!Tsort(v,clock,S)){
                while(!S.empty()){
                    S.pop();
                }
                break;
            }
        }
    }while(s!=(v=++v%this->n));

    return S;
}

template <typename Tv ,typename Te>
bool Graph<Tv,Te>::Tsort(int v,int &clock, std::stack<Tv> &S){
    status(v)=DISCOVERED;
    dTime(v)=++clock;
    for(int u=firstNbr(v);u>-1;u=nextNbr(v)){
        if(status(u)==UNDISCOVERED){
            type(v,u)=TREE;parent(u)=v;
            //continue search deeper
            if(!Tsort(u,clock,S)){
                return false;
            }
        else if(status(u)==DISCOVERED){
            type(v,u)=BACKWARD;
            return false;
        }
        else {
            type(v,u)=(dTime(v)<dTime(u))?FORWARD:CROSS;
        }
        }
    }
    status(v)=VISITED;
    S.push(vertex(v));
    return true;
}

分解雙連通域

若節(jié)點(diǎn)C的移除導(dǎo)致其某一棵(比如以D為根的)真子樹與其真祖先(比如A)之間無法連通，則C必為關(guān)節(jié)點(diǎn)。反之，若C的所有真子樹都能(如以E為根的子 樹那樣)與C的某一真祖先連通，則C就不可能是關(guān)節(jié)點(diǎn)。

image.png

當(dāng)然，在原無向圖的DFS樹中，C的真子樹只可能通過后向邊與C的真祖先連通。因此，只要 在DFS搜索過程記錄并更新各頂點(diǎn)v所能(經(jīng)由后向邊)連通的最高祖先(highest connected ancestor, HCA)hca[v]，即可及時認(rèn)定關(guān)節(jié)點(diǎn)，并報告對應(yīng)的雙連通域。

//bcc
template <typename Tv,typename Te>
void Graph<Tv, Te>::bcc(int s){
    reset();
    int v=s;
    int clock=0;
    std::stack<int> S;
    do{
        if(status(v)==UNDISCOVERED){
            BCC(v,clock,S);
            S.pop();
        }
    }while(s!=(v=++v%this->n));
}
#define hca(x) (fTime(x))
template <typename Tv,typename Te>
void Graph<Tv,Te>::BCC(int v, int &clock, std::stack<int> &S){
    hca(v)=dTime(v)=++clock; 
    status(v)=DISCOVERED;
    S.push(v);
    for(int u=firstNbr(v);u>-1;u=nextNbr(v)){
        if(status(u)==UNDISCOVERED){
            parent(u)=v;
            type(v,u)=TREE;
            BCC(u,clock,S);
            //ancester  u connected to ancester of v through backward
            if(hca(u)<dTime(v)){
                hca(v)=(hca(v)<hca(u))?hca(v):hca(u);//the highest connected component
            }
            else{//v is the articulation point
                while(v!=S.top()){
                    S.pop();
                }//only keep v
            }
        }
        else if(status(u)==DISCOVERED){
            type(v,u)=BACKWARD;
            hca(v)=(dTime(u)<hca(v))?dTime(u):hca(v);
        }
    }
}

3.優(yōu)先級搜索

圖搜索雖然各具特點(diǎn)，但其基本框架依然類似?？傮w而言，都是迭代逐一發(fā)現(xiàn)新頂點(diǎn)，納入遍歷樹中處理。各算法再送能上的差異，主要在每一步迭代新頂點(diǎn)但選擇上。BFS優(yōu)先選取更早發(fā)現(xiàn)但頂點(diǎn)，DFS則優(yōu)先選取最后發(fā)現(xiàn)但頂點(diǎn)。

每種搜索策略都等效于，賦予頂點(diǎn)不同的優(yōu)先級，算法調(diào)整中選取優(yōu)先級最高的。

按照這種理解，包括BFS和DFS在內(nèi)的 幾乎所有圖搜索，都可納入統(tǒng)一的框架。鑒于優(yōu)先級在其中所扮演的關(guān)鍵角色，故亦稱作優(yōu)先級 搜索(priority-first search, PFS)，或最佳優(yōu)先搜索(best-first search, BFS)。

落實(shí)以上理解，可為頂點(diǎn)提供了priority()接口，以支持對頂點(diǎn)優(yōu)先級數(shù)(priority number)的讀取和修改。在實(shí)際應(yīng)用中，引導(dǎo)優(yōu)化方向的指標(biāo)往往對應(yīng)于某種有限的資源或成本(如光纖長度、通訊帶寬等)，故不妨約定優(yōu)先級數(shù)越大(小)頂點(diǎn)的優(yōu)先級越低(高)。相應(yīng)地，在算法的初始化階段（reset())，通常都將頂點(diǎn)的優(yōu) 先級數(shù)統(tǒng)一置為最大(比如INT_MAX)或等價地，優(yōu)先級最低。
按照上述思路，優(yōu)先級搜索算法的框架可具體實(shí)現(xiàn)如代碼

//遍歷所有頂點(diǎn)，如果沒有訪問過就依次進(jìn)行PFS，得到多棵不相干的遍歷樹
//主要是為了搜索所有頂點(diǎn)，防止遺漏連通域
template <typename Tv,typename Te> template <typename PU>
void Graph<Tv,Te>::pfs(int s, PU prioUpdater){
    reset(); int v=s;
    do{
        if(status(v)==UNDISCOVERED){
            PFS(v,prioUpdater);
        }
    }while(s!=(v=v++%n));
}

//對一個頂點(diǎn)進(jìn)行優(yōu)先級搜索
template <typename Tv,typename Te> template <typename PU>
void Graph<Tv,Te>::PFS(int s, PU prioUpdater){
    priority(s)=0; status(s)=VISITED;parent(s)=-1;//initialize
    while(true){
        for(int u=firstNbr(s);u>-1;u=nextNbr(s,u)){
            prioUpdater(this,s,u);//updata priorty and it's father
        }
        for(int shortest=INT_MAX, u=0;u>n;u++){
            if(status(u)==UNDISCOVERED){
                if(shortest>priority(u)){
                    shortest=priority(u);
                    s=u;//max priority point
                }
            }
        }
        if(VISITED==status(s)) break;
        status(s)=VISITED;
        type(parent(s),s)=TREE;
    }
}

如上所述，每次都是引入當(dāng)前優(yōu)先級最高(優(yōu) 先級數(shù)最小)的頂點(diǎn)s，然后按照不同的策略更新其鄰接頂點(diǎn)的優(yōu)先級數(shù)。
這里借助函數(shù)對象prioUpdater，使算法設(shè)計者得以根據(jù)不同的問題需求，簡明地描述和實(shí)現(xiàn)對應(yīng)的更新策略。具體地，只需重新定義prioUpdater對象即可，而不必重復(fù)實(shí)現(xiàn)公共部分。 比如，此前的BFS搜索和DFS搜索都可按照此模式統(tǒng)一實(shí)現(xiàn)

下面，以最小支撐樹和最短路徑這兩個經(jīng)典的圖算法為例，深入介紹這一框架的具體應(yīng)用。

應(yīng)用：

1.最小支撐樹

若圖G為一帶權(quán)網(wǎng)絡(luò)，則每一棵支撐樹的成本(cost)即為其所采用各邊權(quán)重的總和。在G 的所有支撐樹中，成本最低者稱作最小支撐樹(minimum spanning tree, MST)。
聚類分析、網(wǎng)絡(luò)架構(gòu)設(shè)計、VLSI布線設(shè)計等諸多實(shí)際應(yīng)用問題，都可轉(zhuǎn)化并描述為最小支 撐樹的構(gòu)造問題。在這些應(yīng)用中，邊的權(quán)重大多對應(yīng)于某種可量化的成本，因此作為對應(yīng)優(yōu)化問 題的基本模型，最小支撐樹的價值不言而喻。

消除歧義

盡管同一帶權(quán)網(wǎng)絡(luò)通常都有多棵支撐樹，但總數(shù)畢竟有限，故必有最低的總體成本。然而， 總體成本最低的支撐樹卻未必唯一。以包含三個頂點(diǎn)的完全圖為例，若三條邊的權(quán)重相等，則其 中任意兩條邊都構(gòu)成總體成本最低的一棵支撐樹。
故嚴(yán)格說來，此類支撐樹應(yīng)稱作極小支撐樹(minimal spanning tree)。當(dāng)然， 通過強(qiáng)制附加某種次序即可消除這種歧義性。

暴力算法

由最小支撐樹的定義，可直接導(dǎo)出蠻力算法大致如下:逐一考查G的所有支撐樹并統(tǒng)計其成 本，從而挑選出其中的最低者。然而根據(jù)Cayley公式，由n個互異頂點(diǎn)組成的完全圖共有nn-2棵 支撐樹，即便忽略掉構(gòu)造所有支撐樹所需的成本，僅為更新最低成本的記錄就需要O(nn-2)時間。事實(shí)上基于PFS搜索框架，并采用適當(dāng)?shù)捻旤c(diǎn)優(yōu)先級更新策略，即可得出如下高效的最小支 撐樹構(gòu)造算法。

Prim算法

圖G = (V; E)中，頂點(diǎn)集V的任一非平凡子集U及其補(bǔ)集V\U都構(gòu)成G的一個割(cut)，記作(U : V\U)。若邊uv滿足u屬于U且v不屬于U，則稱作該割的一條跨越邊(crossing edge)。

Prim算法的正確性基于以下事實(shí):最小支撐樹總是會采用聯(lián)接每一割的最短跨越邊。

由以上性質(zhì)，可基于貪心策略導(dǎo)出一個迭代式算法。每一步迭代之前，假設(shè)已經(jīng)得到最小支 撐樹T的一棵子樹Tk = (Vk; Ek)，其中Vk包含k個頂點(diǎn)，Ek包含k - 1條邊。于是，若將Vk及其補(bǔ) 集視作原圖的一個割，則在找到該割的最短跨越邊ek之后，即可 將Tk擴(kuò)展為一棵更大的子樹Tk+1 = (Vk+1; Ek+1)，其中Vk+1 = Vk 并 {uk}，Ek+1 = Ek 并 {ek}。 最初的T1不含邊而僅含單個頂點(diǎn)，故可從原圖的頂點(diǎn)中任意選取。

//prim MST
template <class Tv ,class Te>
struct PrimPu{
    virtual void operator()(Graph<Tv,Te> &g,int uk,int v){
            if(UNDISCOVERED==g.status(v)){
                if(g.priority(v)>g.weight(uk,v)){
                    g.priority(v)=g.weight(uk,v);
                    g.parent(v)=uk;
                }
            }
    }
};

替換掉PFS框架里的PrioUpdater即可實(shí)現(xiàn)最小支撐樹。
以上Prim算法的時間復(fù)雜度為O(n2)，作為PFS搜索的特例，Prim算法的效率 也可借助優(yōu)先級隊列進(jìn)一步提高

2.最短路徑

給定帶權(quán)網(wǎng)絡(luò)G = (V, E)，以及源點(diǎn)(source)s，對于所有的其它頂點(diǎn)v， s到v的最短通路有多長?該通路由哪些邊構(gòu)成?

首先我們要分析最短路徑樹等特征

• 單調(diào)性：最短路徑的任意前綴路徑必須是最短路徑
• 歧義：最短路徑不唯一，等權(quán)邊會導(dǎo)致結(jié)果不唯一，負(fù)權(quán)邊導(dǎo)致定義失效
• 無環(huán)路

Dijkstra算法

將頂點(diǎn)ui到起點(diǎn)s的距離記作:di = dist(s, ui)，1 <i < n。不妨設(shè)di按非降序排列，
即di <dj當(dāng)且僅當(dāng)i < j。于是與s自身相對應(yīng)地必有:u1 = s。

• 最短路徑子樹序列
  在從最短路徑樹T中刪除頂點(diǎn){ uk+1, uk+2, ..., un }及其關(guān)聯(lián)各邊之后，將殘存的子圖記 作Tk。于是Tn = T，T1僅含單個頂點(diǎn)s。實(shí)際上，Tk必為一棵樹。為驗(yàn)證這一點(diǎn)，只需歸納證明 Tk是連通的。為從Tk+1轉(zhuǎn)到Tk而刪除的頂點(diǎn)uk+1，在Tk+1中必是葉節(jié)點(diǎn)。而根據(jù)最短路徑的單調(diào)性， 作為Tk+1中距離最遠(yuǎn)的頂點(diǎn)，uk+1不可能擁有后代。
  于是，如上定義的子樹{ T1, T2, ..., Tn }，便構(gòu)成一個最短路徑子樹序列。
• 貪心迭代
  顛倒上述思路可知，只要能夠確定uk+1，便可反過來將Tk擴(kuò)展為Tk+1。如此，便可按照到s距離的非降次序，逐一確定各個頂點(diǎn){ u1, u2, ..., un }，同時得到各棵最短路徑子樹，并得到 最終的最短路徑樹T = Tn。現(xiàn)在，問題的關(guān)鍵就在于:

如何才能高效地找到uk+1?

實(shí)際上，由最短路徑子樹序列的上述性質(zhì)，每一個頂點(diǎn)uk+1都是在Tk之外，距離s最近者。 若將此距離作為各頂點(diǎn)的優(yōu)先級數(shù)，則與最小支撐樹的Prim算法類似，每次將uk+1加入Tk并將其 拓展至Tk+1后，需要且只需要更新那些仍在Tk+1之外，且與Tk+1關(guān)聯(lián)的頂點(diǎn)的優(yōu)先級數(shù)。

為此，每次由Tk擴(kuò)展至Tk+1時，可將Vk之外各頂點(diǎn)u到s的距離看作u的優(yōu)先級數(shù)，如此，每一最短跨越邊ek所對應(yīng)的頂點(diǎn)uk，都會因擁有 最小的優(yōu)先級數(shù)(或等價地，最高的優(yōu)先級)而被選中

template <class Tv, class Te>
struct DijkstraPU{
    virtual void operator()(Graph<Tv,Te> &g, int uk, int v){
        if(g.status(v)==UNDISCOVERED){
            if(g.priority(v)>g.priority(uk)+g.weight(uk,v)){
                g.priority(v)=g.priority(uk)+g.weight(uk,v);
                g.parent(v)=uk;
            }
        }
    }
};

每次更新新頂點(diǎn)v的權(quán)重priority（v）等于上一個頂點(diǎn)uk的權(quán)重priority（uk）加上邊uk-v的權(quán)重。事實(shí)上，每個頂點(diǎn)的權(quán)重等于該頂點(diǎn)到初始節(jié)點(diǎn)的邊權(quán)重和

圖模版

#include <stack>
#include "vector.h"
#include <queue>
typedef enum{UNDISCOVERED,DISCOVERED,VISITED} VStatus;
typedef enum{UNDETERMINED,TREE,CROSS,FORWARD,BACKWARD} EType;

template <class Tv,class Te>
class Graph{
    private:
        /**
         * reset
         */
        void reset(){
            for(int i=0;i<n;i++){
                status(i)=UNDISCOVERED;
                dTime(i)=fTime(i)=-1;
                parent(i)=-1;
                priority(i)=__INT_MAX__;
                for (int j=0;j<n;j++){
                    if(exists(i,j)) type(i,j)==UNDETERMINED;
                }

            }
        }
        /**
         * BFS
         */
        void BFS(int ,int &);

        /**
         * DFS
         */
        void DFS(int ,int &);

        /**
         * BCC based on DFS
         */
        void BCC(int ,int &, std::stack<int>& );

        /**
         * Tsort based on DFS
         */
        bool Tsort(int ,int &, std::stack<Tv>&);

        /**
         * PSU
         */
        template <class PU>
        void PFS(int ,PU);

    public:
        int n;//vertex number
        /**
         * insert
         */
        virtual int insert(Tv const&)=0;
        /**
         * remove vertex n
         */
        virtual Tv remove(int )=0;

        /**
         * get vertex n data
         */
        virtual Tv& vertex(int)=0;

        /**
         * get inDegree of vertex n
         */
        virtual int inDegree(int )=0;

        /**
         * get outDegree of vertex n
         */
        virtual int outDegree(int)=0;

        /**
         * vertex v's first neibhor
         */
        virtual int firstNbr(int )=0;

        virtual int nextNbr(int i,int j)=0;

        /**
         * get vertex status 
         */
        virtual VStatus& status(int )=0;

        /**
         * dTime of vertex
         */
        virtual int& dTime(int)=0;

        /**
         * ftime
         */
        virtual int&fTime(int)=0;

        /**
         * parent vertex of traverse tree
         */
        virtual int& parent(int)=0;

        /**
         * priority of vertex
         */
        virtual int& priority(int)=0;

        //edge treat undigraph as reverse digraph
        int e;//number of edge;
        
        /**
         * e(i,j) exists
         */
        virtual bool exists(int ,int )=0; 

        /**
         * insert edge with weight w between u,and v
         */
        virtual void insert(Te const& e,int ,int ,int)=0;

        /**
         * remove edge e between u,v return info
         */
        virtual Te remove(int ,int)=0;

        /**
         * type of e(u,v)
         */
        virtual EType& type(int ,int )=0;

        /**
         * get number of e(u,v)
         */
        virtual Te& edge(int ,int )=0;

        /**
         * get weight of e(u,v)
         */
        virtual int &weight(int,int )=0;

        //algorithms
        /**
         * bradth first search
         */
        void bfs(int);

        /**
         * dfs
         */
        void dfs(int);

        /**
         * bcc double conncetion based on dfs
         */
        void bcc(int);

        /**
         * topologic sort based on dfs
         */
        std::stack<Tv>* tSort(int);

        /**
         * prim
         */
        void prim(int);

        /**
         * dijkstra
         */
        void dijkstra(int);
        
        /**
         * pfs
         */
        template <class PU>
        void pfs(int ,PU);

};
//GraphMatrix
/**
 * @bref Vertex
 */
template <typename Tv>
struct Vertex{
    Tv data;
    int inDegree;
    int outDegree;
    VStatus status;

    int dTime;
    int fTime;
    
    int parent;
    int priority;

    /**
     * constructor
     */
    Vertex(Tv const& d=(Tv)0):data(d),inDegree(0),outDegree(0),status(UNDISCOVERED),dTime(-1),fTime(-1),parent(-1),priority(__INT_MAX__){};
};

/**
 * @bref Edge
 */
template<typename Te>
struct Edge{
    Te data;
    int weight;
    EType type;
    /**
     * constructor
     */
    Edge(Te const&d,int w):data(d),weight(w),type(UNDETERMINED){};
};

//GraphMatrix
/**
 * GraphMatrix
 */
template<typename Tv,typename Te>
class GraphMatrix:public Graph<Tv,Te>{
    private:
        Vector< Vertex<Tv> > V;//store the vertex
        Vector< Vector< Edge<Te>* > >E;//store the edgematrix double vector
    
    public :
    GraphMatrix(){
        this->n=0;
        this->e=0;
        }
    ~GraphMatrix(){
        for (int j=0;j<this->n;j++){
            for(int k=0;k<this->n;k++){
                delete E[j][k];
            }
        }
    }

    //vertex
    virtual Tv& vertex(int i){
        return V[i].data;
    }

    virtual int inDegree(int i){
        return V[i].inDegree;
    }

    virtual int outDegree(int i){
        return V[i].outDegree;
    }

    virtual int firstNbr(int i){
        return nextNbr(i,this->n);
    }

    virtual int nextNbr(int i,int j){
        while((-1<j)&&(!exists(i,--j)));
        return j;
    }

    virtual VStatus& status(int i){
        return V[i].status;
    }

    virtual int&dTime(int i){
        return V[i].dTime;
    }

    virtual int &fTime(int i){
        return V[i].fTime;
    }

    virtual int &parent(int i){
        return V[i].parent;
    }

    virtual int &priority(int i){
        return V[i].priority;
    }

    //dynamic operator of vertex
    virtual int insert(Tv const& vertex){
        for(int j=0;j<this->n;j++){
            E[j].insert(nullptr);//each edge set a default no connect edge to newVertex
        }
        this->n++;
        //new edge
        E.insert(Vector< Edge<Te>* > (this->n,(Edge<Te>) nullptr));
        return V.insert(Vertex<Tv> (vertex));
    }

    virtual Tv remove(int i){
        for(int j=0;j<this->n;j++){
                if(exists(i,j)){
                    delete E[i][j];
                    V[j].inDegree--;
                }
        }
        E.remove(i);
        this->n--;
        Tv vBackup=V[i].data;
        V.remove(i);

        for(int j=0;j<this->n;j++){
            if(Edge<Te> *e=E[j].remove(i)){delete e;V[j].outDegree--;}
        }
        return vBackup;
    }


    //confirm e[i][j] exist
    virtual bool exists(int i,int j){
        return (0<=i)&&(i<this->n)&&(j>=0)&&(j<this->n)&&(E[i][j]!=nullptr);
    }

    //edge operator
    virtual EType& type(int i,int j){
        return E[i][j].type;
    } 

    virtual Te& edge(int i,int j){
        return E[i][j]->data;
    }

    virtual int& weight(int i, int j){
        return E[i][j]->weight;
    }

    //dynamic operator of edge
    virtual void insert(Te const& edge, int w, int i, int j){
        if(exists(i,j)) return ;
        E[i][j]=new Edge<Te>(edge,w);
        this->e++;
        V[i].outDegree++;
        V[j].inDegree++;
    }

    virtual Te remove(int i, int j){
        if(!exists(i,j)) exit(-1);
        Te eBackup=edge(i,j);
        delete E[i][j];
        E[i][j]=nullptr;
        this->e--;
        V[i].outDegree--;
        V[j].inDegree--;
        return eBackup;
    }





};