/*******************************
圖的DFS信息構(gòu)建 by oyjpArt
g矩陣: g[i][j] -> 0 : 無邊
1 : 可重復(fù)訪問邊
-1: 非可重復(fù)訪問邊
說明:以為在無向圖中u->v訪問之后就不能再從v->u訪問了
故{u, v}訪問了之后{v, u}要置-1
如果是有向圖 則沒有這個(gè)規(guī)則
gc矩陣:gc[i][j]-> 0 : 無邊
1 : 樹枝邊
2 : 反向邊
3 : 正向邊
4 : 交叉邊
d數(shù)組: 頂點(diǎn)的開始訪問時(shí)間表
f數(shù)組: 頂點(diǎn)的結(jié)束訪問時(shí)間表
c數(shù)組: 頂點(diǎn)顏色表 0白色 -1灰色 1黑色
p數(shù)組: 頂點(diǎn)的前驅(qū)表
l數(shù)組: 頂點(diǎn)的L值(最頂層的祖先層數(shù))
b數(shù)組: 頂點(diǎn)的度數(shù)表
關(guān)于標(biāo)號函數(shù) LOW()
LOW(U)代表的是與U以及U的子孫直接相連的結(jié)點(diǎn)的最高輩分（深度）
d[U] U首次被訪問時(shí)
LOW[U] = min(LOW[U], d[W]) 訪問邊{U,W}
min(LOW[U], LOW[S]) U的兒子S的關(guān)聯(lián)邊全部被訪問時(shí)
/*******************************/
const int maxn = 100;
int n, g[maxn][maxn], gc[maxn][maxn];
int d[maxn], f[maxn], l[maxn], p[maxn], c[maxn], b[maxn];
int time;
void dfs_visit(int u) {//遞歸搜索以U為根的深度優(yōu)先樹
int v;
c[u] = -1; //置頂點(diǎn)為灰色//去掉這句之后適用于有向圖(后面設(shè)置不可訪問亦同)
time++; d[u] = time, l[u] = time;
for(v = 1; v<=n; v++)
if(g[u][v] > 0)
if(c[v] == 0) { //如果v是白色節(jié)點(diǎn)
g[v][u] = -1; //不可再訪問
gc[u][v] = 1; //樹枝邊
b[u]++; //度數(shù)
p[v] = u; //記錄父親節(jié)點(diǎn)
dist_visit(v); //遞歸搜索以v為根的深度優(yōu)先樹
if(l[v] < l[u]) //v是u的后代
l[u] = l[v]; //u的兒子v的關(guān)聯(lián)邊搜索完后計(jì)算父親的low值
g[v][u] = 1; //恢復(fù)可訪問標(biāo)志
}
else {
if(c[v] < 0) { //若頂點(diǎn)為灰色
if(l[v] < l[u]) //u與v相連
l[u] = l[v];
gc[u][v] = 2; //反向邊
}
else { //黑色
if(d[v] > d[u])
gc[u][v] = 3; //正向邊
else
gc[u][v] = 4; //交叉邊
}
}
c[u] = 1; //DFS完畢 置黑色吧
time++; f[u] = time;
}
void dfs() {
int u;
memset(gc, 0, sizeof(gc));
memset(c, 0, sizeof(c));
memset(b, 0, sizeof(b));
time = 0;
for(u = 1; u <= n; u++)
if(c[u] == 0) {
p[u] = 0;
dfs_visit(u);
}
}
/*******************************
DFS3大經(jīng)典應(yīng)用
一: TOPO排序
DFS之后按照結(jié)束訪問時(shí)間反向排序即可 如果在DFS過程中出現(xiàn)方向邊(成環(huán)) 則無法TOPO
當(dāng)然我們還有一種經(jīng)典的TOPO方法 找0度節(jié)點(diǎn)迭代刪除法 o(M+N)的TC
二: 求割點(diǎn)和橋
判定規(guī)則1: 如果root節(jié)點(diǎn)又多于一個(gè)1子節(jié)點(diǎn) 則root是割點(diǎn)
判定規(guī)則2: 如果一個(gè)節(jié)點(diǎn)u有某一個(gè)子節(jié)點(diǎn)v不含到u的祖先節(jié)點(diǎn)的后向邊 則u為割點(diǎn)
即對于u的子節(jié)點(diǎn)v, u是割點(diǎn)的條件 (p[u] == 0 && b[v] > 1) || (p[u] > 0 && l[v] >= d[u])
橋: 不屬于任何簡單回路的邊 "一牽動(dòng)全身" l[v] > d[u]即是橋
之所以不能等于 實(shí)際上等于的情況是存在2條以上的邊 自然就不是橋了~
(注意加上割點(diǎn)表 以防重復(fù)輸出)
三: 求有向圖的極大強(qiáng)連通分支
1.對圖進(jìn)行DFS遍歷 遍歷中記下所有的結(jié)束時(shí)間A[i].遍歷的結(jié)果是構(gòu)建的一座森林W1
我們對W1中的每棵樹G進(jìn)行步驟2到步驟3的操作
2.改變圖G中每一條邊的方向 構(gòu)造出新的有向圖Gr
3.按照A[i]由小到大的順序?qū)r進(jìn)行DFS遍歷.遍歷的結(jié)果是構(gòu)建了新的樹林W2.
W2中每棵樹上的頂點(diǎn)構(gòu)成了有向圖的極大強(qiáng)連通分支
/*******************************/
//一個(gè)更加簡潔的程序框架(來自<<算法藝術(shù)與信息學(xué)競賽>>)-------
這里面的Ancestor相當(dāng)于上面所說的LOW
Procedure DFS(節(jié)點(diǎn)編號k, k的父親節(jié)點(diǎn)編號father, deep:integer)
var i, tot : integer;
begin
C[k] = -1; {灰色}
D[k] = deep; {記錄深度}
Ancestor[k] = deep, tot = 0;
for i = 1->n
begin
if(節(jié)點(diǎn)i和k相連) and (i != father) and (Ci = -1)
then Ancestor[k] = Min(Ancestor[k], Di);
if(節(jié)點(diǎn)i與k相連) and (Ci = 0) then
begin
DFS(i, k, deep + 1);
tot++, Ancestor[k] = Min(Ancestor[k], Ancestor[i]);
if(k == Root) and (tot > 1) or
( (k != Root) and (Ancestor[i] >= D[k]) )
then Cut[k] = true;
if(Ancestor[i] > D[k]) then Brige[k][i] = true
end
end
C[k] = 1; //黑色
time++, A[i] = time;
end;
//-----------------------------------------------------------