1.BFS
優(yōu)先訪問最先發(fā)現(xiàn)的節(jié)點示惊，可以根據(jù)FIFO隊列的特點，選用隊列實現(xiàn)
可以實現(xiàn)連通域分解和最短路徑等問題埃元。
等同于樹結構中的層次遍歷
//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)先選取最后一個被訪問到的頂點的鄰居
于是涝涤，以頂點s為基點的DFS搜索，將首先訪問頂點s;再從s所有尚未訪問到的鄰居中任取 其一岛杀，并以之為基點，遞歸地執(zhí)行DFS搜索崭孤。故各頂點被訪問到的次序类嗤，類似于樹的先序遍歷 ;而各頂點被訪問完畢的次序，則類似于樹的后序遍歷
//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;
}
算法的實質功能辨宠，由子算法DFS()遞歸地完成遗锣。每一遞歸實例中，都先將當前節(jié)點v標記為 DISCOVERED(已發(fā)現(xiàn))狀態(tài)嗤形，再逐一核對其各鄰居u的狀態(tài)并做相應處理精偿。待其所有鄰居均已處 理完畢之后，將頂點v置為VISITED(訪問完畢)狀態(tài)赋兵，便可回溯笔咽。
若頂點u尚處于UNDISCOVERED(未發(fā)現(xiàn))狀態(tài)，則將邊(v, u)歸類為樹邊(tree edge)霹期，并將v記作u的父節(jié)點叶组。此后，便可將u作為當前頂點历造，繼續(xù)遞歸地遍歷甩十。 若頂點u處于DISCOVERED狀態(tài)，則意味著在此處發(fā)現(xiàn)一個有向環(huán)路吭产。此時侣监，在DFS遍歷樹中u必為v的祖先，故應將邊(v, u)歸類為后向邊(back edge)臣淤。 這里為每個頂點v都記錄了被發(fā)現(xiàn)的和訪問完成的時刻橄霉，對應的時間區(qū)間[dTime(v), fTime(v)]均稱作v的活躍期(active duration)。實際上荒典，任意頂點v和u之間是否存在祖先-后代的“血緣”關系酪劫，完全取決于二者的活躍期是否相互包含吞鸭。
對于有向圖，頂點u還可能處于VISITED狀態(tài)覆糟。此時刻剥，只要比對v與u的活躍期，即可判定在 DFS樹中v是否為u的祖先滩字。若是造虏，則邊(v, u)應歸類為前向邊(forward edge);否則，二者必然來自相互獨立的兩個分支麦箍，邊(v, u)應歸類為跨邊(cross edge)漓藕。
DFS(s)返回后，所有訪問過的頂點通過parent[]指針依次聯(lián)接挟裂，從整體上給出了頂點s所屬連通或可達分量的一棵遍歷樹享钞，稱作深度優(yōu)先搜索樹或DFS樹(DFS tree)。與BFS搜索一樣诀蓉， 此時若還有其它的連通或可達分量栗竖，則可以其中任何頂點為基點，再次啟動DFS搜索渠啤。
最終狐肢，經(jīng)各次DFS搜索生成的一系列DFS樹，構成了DFS森林(DFS forest)
應用：拓撲排序
有向無環(huán)圖一定有拓撲排序
1.入度為零法
考察圖G沥曹，尋找入度為0的頂點份名，去掉后刪除相關邊，再找下一個入度為零點妓美。直到僅剩一個頂點僵腺。
2.VISITED順序的倒序即是一個拓撲排序
同理，有限偏序集中也必然存在極小元素(同樣部脚，未必唯一)想邦。該元素作為頂點，出度必然 為零委刘。 而在對有向無環(huán)圖的DFS搜索中丧没，首先因訪問完成而轉 換至VISITED狀態(tài)的頂點m，也必然具有這一性質;反之亦然锡移。
進一步地呕童，根據(jù)DFS搜索的特性，頂點m(及其關聯(lián)邊)對此后的搜索過程將不起任何作用淆珊。 于是夺饲，下一轉換至VISITED狀態(tài)的頂點可等效地理解為是，從圖中剔除頂點m(及其關聯(lián)邊)之 后的出度為零者??在拓撲排序中，該頂點應為頂點m的前驅往声。由此可見擂找，DFS搜索過程中各頂 點被標記為VISITED的次序，恰好(按逆序)給出了原圖的一個拓撲排序浩销。
此外贯涎，DFS搜索善于檢測環(huán)路的特性，恰好可以用來判別輸入是否為有向無環(huán)圖慢洋。具體地塘雳， 搜索過程中一旦發(fā)現(xiàn)后向邊，即可終止算法并報告“因非DAG而無法拓撲排序”普筹。
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é)點C的移除導致其某一棵(比如以D為根的)真子樹與其真祖先(比如A)之間無法連通败明，則C必為關節(jié)點。反之太防，若C的所有真子樹都能(如以E為根的子 樹那樣)與C的某一真祖先連通妻顶，則C就不可能是關節(jié)點。
當然蜒车，在原無向圖的DFS樹中盈包，C的真子樹只可能通過后向邊與C的真祖先連通。因此醇王，只要 在DFS搜索過程記錄并更新各頂點v所能(經(jīng)由后向邊)連通的最高祖先(highest connected ancestor, HCA)hca[v]，即可及時認定關節(jié)點崭添，并報告對應的雙連通域寓娩。
//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)先級搜索
圖搜索雖然各具特點，但其基本框架依然類似呼渣〖椋總體而言，都是迭代逐一發(fā)現(xiàn)新頂點屁置，納入遍歷樹中處理焊夸。各算法再送能上的差異，主要在每一步迭代新頂點但選擇上蓝角。BFS優(yōu)先選取更早發(fā)現(xiàn)但頂點阱穗，DFS則優(yōu)先選取最后發(fā)現(xiàn)但頂點。
每種搜索策略都等效于使鹅，賦予頂點不同的優(yōu)先級揪阶，算法調整中選取優(yōu)先級最高的。
按照這種理解患朱，包括BFS和DFS在內的 幾乎所有圖搜索鲁僚，都可納入統(tǒng)一的框架。鑒于優(yōu)先級在其中所扮演的關鍵角色，故亦稱作優(yōu)先級 搜索(priority-first search, PFS)冰沙，或最佳優(yōu)先搜索(best-first search, BFS)侨艾。
落實以上理解，可為頂點提供了priority()接口拓挥，以支持對頂點優(yōu)先級數(shù)(priority number)的讀取和修改唠梨。在實際應用中，引導優(yōu)化方向的指標往往對應于某種有限的資源或成本(如光纖長度撞叽、通訊帶寬等)姻成，故不妨約定優(yōu)先級數(shù)越大(小)頂點的優(yōu)先級越低(高)。相應地愿棋，在算法的初始化階段（reset())科展，通常都將頂點的優(yōu) 先級數(shù)統(tǒng)一置為最大(比如INT_MAX)或等價地，優(yōu)先級最低糠雨。
按照上述思路才睹，優(yōu)先級搜索算法的框架可具體實現(xiàn)如代碼
//遍歷所有頂點，如果沒有訪問過就依次進行PFS甘邀，得到多棵不相干的遍歷樹
//主要是為了搜索所有頂點琅攘，防止遺漏連通域
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));
}
//對一個頂點進行優(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;
}
}
如上所述，每次都是引入當前優(yōu)先級最高(優(yōu) 先級數(shù)最小)的頂點s松邪，然后按照不同的策略更新其鄰接頂點的優(yōu)先級數(shù)坞琴。
這里借助函數(shù)對象prioUpdater，使算法設計者得以根據(jù)不同的問題需求逗抑，簡明地描述和實現(xiàn)對應的更新策略剧辐。具體地，只需重新定義prioUpdater對象即可邮府，而不必重復實現(xiàn)公共部分荧关。 比如，此前的BFS搜索和DFS搜索都可按照此模式統(tǒng)一實現(xiàn)
下面褂傀，以最小支撐樹和最短路徑這兩個經(jīng)典的圖算法為例忍啤，深入介紹這一框架的具體應用。
應用：
1.最小支撐樹
若圖G為一帶權網(wǎng)絡仙辟，則每一棵支撐樹的成本(cost)即為其所采用各邊權重的總和同波。在G 的所有支撐樹中，成本最低者稱作最小支撐樹(minimum spanning tree, MST)欺嗤。
聚類分析参萄、網(wǎng)絡架構設計、VLSI布線設計等諸多實際應用問題煎饼，都可轉化并描述為最小支 撐樹的構造問題讹挎。在這些應用中校赤，邊的權重大多對應于某種可量化的成本，因此作為對應優(yōu)化問 題的基本模型筒溃，最小支撐樹的價值不言而喻马篮。
消除歧義
盡管同一帶權網(wǎng)絡通常都有多棵支撐樹，但總數(shù)畢竟有限怜奖，故必有最低的總體成本浑测。然而， 總體成本最低的支撐樹卻未必唯一歪玲。以包含三個頂點的完全圖為例迁央，若三條邊的權重相等，則其 中任意兩條邊都構成總體成本最低的一棵支撐樹滥崩。
故嚴格說來岖圈，此類支撐樹應稱作極小支撐樹(minimal spanning tree)。當然钙皮， 通過強制附加某種次序即可消除這種歧義性蜂科。
暴力算法
由最小支撐樹的定義，可直接導出蠻力算法大致如下:逐一考查G的所有支撐樹并統(tǒng)計其成 本短条，從而挑選出其中的最低者导匣。然而根據(jù)Cayley公式，由n個互異頂點組成的完全圖共有nn-2棵 支撐樹茸时，即便忽略掉構造所有支撐樹所需的成本贡定，僅為更新最低成本的記錄就需要O(nn-2)時間。事實上基于PFS搜索框架可都，并采用適當?shù)捻旤c優(yōu)先級更新策略厕氨，即可得出如下高效的最小支 撐樹構造算法。
Prim算法
圖G = (V; E)中汹粤，頂點集V的任一非平凡子集U及其補集V\U都構成G的一個割(cut)，記作(U : V\U)田晚。若邊uv滿足u屬于U且v不屬于U嘱兼，則稱作該割的一條跨越邊(crossing edge)。
Prim算法的正確性基于以下事實:最小支撐樹總是會采用聯(lián)接每一割的最短跨越邊贤徒。
由以上性質芹壕，可基于貪心策略導出一個迭代式算法。每一步迭代之前接奈，假設已經(jīng)得到最小支 撐樹T的一棵子樹Tk = (Vk; Ek)踢涌，其中Vk包含k個頂點，Ek包含k - 1條邊序宦。于是睁壁，若將Vk及其補 集視作原圖的一個割，則在找到該割的最短跨越邊ek之后，即可 將Tk擴展為一棵更大的子樹Tk+1 = (Vk+1; Ek+1)潘明，其中Vk+1 = Vk 并 {uk}行剂，Ek+1 = Ek 并 {ek}。 最初的T1不含邊而僅含單個頂點钳降，故可從原圖的頂點中任意選取厚宰。
//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即可實現(xiàn)最小支撐樹。
以上Prim算法的時間復雜度為O(n2)遂填，作為PFS搜索的特例铲觉，Prim算法的效率 也可借助優(yōu)先級隊列進一步提高
2.最短路徑
給定帶權網(wǎng)絡G = (V, E)，以及源點(source)s吓坚，對于所有的其它頂點v撵幽， s到v的最短通路有多長?該通路由哪些邊構成?
首先我們要分析最短路徑樹等特征
- 單調性：最短路徑的任意前綴路徑必須是最短路徑
- 歧義：最短路徑不唯一，等權邊會導致結果不唯一凌唬，負權邊導致定義失效
- 無環(huán)路
Dijkstra算法
將頂點ui到起點s的距離記作:di = dist(s, ui)并齐，1 <i < n。不妨設di按非降序排列客税，
即di <dj當且僅當i < j况褪。于是與s自身相對應地必有:u1 = s。
- 最短路徑子樹序列
在從最短路徑樹T中刪除頂點{ uk+1, uk+2, ..., un }及其關聯(lián)各邊之后更耻，將殘存的子圖記 作Tk测垛。于是Tn = T，T1僅含單個頂點s秧均。實際上食侮，Tk必為一棵樹。為驗證這一點目胡，只需歸納證明 Tk是連通的锯七。為從Tk+1轉到Tk而刪除的頂點uk+1，在Tk+1中必是葉節(jié)點誉己。而根據(jù)最短路徑的單調性眉尸， 作為Tk+1中距離最遠的頂點，uk+1不可能擁有后代巨双。
于是噪猾，如上定義的子樹{ T1, T2, ..., Tn }，便構成一個最短路徑子樹序列筑累。 - 貪心迭代
顛倒上述思路可知袱蜡，只要能夠確定uk+1，便可反過來將Tk擴展為Tk+1慢宗。如此坪蚁，便可按照到s距離的非降次序奔穿，逐一確定各個頂點{ u1, u2, ..., un }，同時得到各棵最短路徑子樹迅细，并得到 最終的最短路徑樹T = Tn∥组希現(xiàn)在，問題的關鍵就在于:
如何才能高效地找到uk+1?
實際上茵典，由最短路徑子樹序列的上述性質湘换，每一個頂點uk+1都是在Tk之外，距離s最近者统阿。 若將此距離作為各頂點的優(yōu)先級數(shù)彩倚，則與最小支撐樹的Prim算法類似，每次將uk+1加入Tk并將其 拓展至Tk+1后扶平，需要且只需要更新那些仍在Tk+1之外帆离，且與Tk+1關聯(lián)的頂點的優(yōu)先級數(shù)。
為此结澄，每次由Tk擴展至Tk+1時哥谷，可將Vk之外各頂點u到s的距離看作u的優(yōu)先級數(shù)，如此麻献，每一最短跨越邊ek所對應的頂點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;
}
}
}
};
每次更新新頂點v的權重priority（v）等于上一個頂點uk的權重priority（uk）加上邊uk-v的權重勉吻。事實上监婶，每個頂點的權重等于該頂點到初始節(jié)點的邊權重和
圖模版
#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;
}
};
