---

一、鄰接矩陣存儲圖的深度優先遍歷過程分析

對圖1這樣的無向圖，要寫成鄰接矩陣，則就是下面的式子：

一般要計算這樣的問題，畫成表格來處理是相當方便的事情，實際中計算機處理問題，也根本不知道所謂矩陣是什么，所以畫成表格很容易幫助我們完成后面的編程任務。在我們前面介紹的內容中，有不少是借助著表格完成計算任務的，如Huffman樹。

為了記錄那些頂點是已經走過的，還要設計一個表來標記已經走過的頂點，在開始，我們假設未走過的是0，走過的是1，于是有：

深度優先遍歷過程如下：

（1）從第1行開始，尋找和V1相連的第1個頂點，首先在Visited表中標記V1被訪問到，就是：

在該行，我們找到的第一個連接頂點是V2，找到V2頂點后，記錄：V1->V2，意味著我們已經抵達V2，注意修改鄰接矩陣表；

（2）然后則轉向V2頂點所在的行，意味著我們已經抵達V2，再次在Visited表中標記V2頂點已經被訪問，就是：

然后，尋找連接V2的、并且是未被訪問過的第一個頂點，就是V4：記錄V2->V4；

（3）然后則轉向V4頂點所在的行，意味著我們已經抵達V4，再次在Visited表中標記V4頂點已經被訪問，就是：

然后則轉向V4頂點所在的行，尋找連接V4的、并且是未被訪問過的第一個頂點，就是V8：記錄V4->V8；

（4）然后則轉向V8頂點所在的行，意味著我們已經抵達V8，再次在Visited表中標記V8頂點已經被訪問，就是：

然后則轉向V8頂點所在的行，尋找連接V8的、并且是未被訪問過的第一個頂點，就是V5：記錄V8->V5；

（5）然后則轉向V5頂點所在的行，意味著我們已經抵達V5，再次在Visited表中標記V5頂點已經被訪問，就是：

尋找連接V5的、并且是未被訪問過的第一個頂點，此處未找到，注意V2、V8頂點已經在Visited表中標記已訪問過。

（5）這個地方一定注意：V5上找不到未訪問過的頂點，說明此路到此就算走死了。

此時看Visited表：其中還有頂點沒有抵達過，于是要按原路返回，所謂原路就是從表12、表10、表9走過的路線返回、然后逐個查找這些頂點上有無未抵達過的頂點。過程如下：再次從V5返回到V8，查找V8上有無未抵達過的頂點，結果是無；
再次從V8返回到V4，查找V4上有無未抵達過的頂點，結果是無；
再次從V4返回到V2，查找V2上有無未抵達過的頂點，結果是無；
再次從V2返回到V1，查找V1上有無未抵達的頂點，結果是V3，于是重復第(1)步，首先標記V3訪問到：
標記V1->V3，標記Visited表V3被訪問：

到V3，就是這樣的情況：

（6）到達V3后，尋找第一個未被訪問過的頂點：V6，首先標記Visited表，說明已經抵達V6，就是：

再從V6開始找下一個頂點就是V7：

（7）在Visited表中標注V7已經訪問到，就是：

至此，圖1的深度優先遍歷完成。

二、結果分析

從上面的過程可以看出：僅僅就頂點訪問到的次序而言，圖1的深度優先遍歷結果是：

V1->V2->V4->V8->V5->V3->6->V7

但實際執行過程中我們可以發現：所謂圖的遍歷、其結果應該是一個樹：

在C語言中，顯示這個結果并不容易，所以大多教材中并不會給出這樣的結果。

三、C語言編程實現圖的深度優先遍歷

圖1只有8個頂點，可在實際中，一個圖的頂點個數是不確定的，在編程中要保存頂點數據、鄰接矩陣，首先就要考慮動態數組；其次，為了方便鄰接矩陣的輸入和修改，最好是把數據保存在文本文件中。在我們的教材中、程序使用了鍵盤輸入的方式，而在實際操作中、在圖的頂點個數比較多的情況下，手工無差錯輸入很多數據、幾乎是無法辦到的事情，為此，我們在文件p176G719.txt中保存了圖1的鄰接矩陣數據。這個文件的名稱含義是：教材176頁圖7.19的頂點名稱和鄰接矩陣數據。有了這樣的數據文件，在記事本程序中可以很方便的修改和補充數據。這個文件的內容如下：

8
V1
V2
V3
V4
V5
V6
V7
V8
0 1 1 0 0 0 0 0
1 0 0 1 1 0 0 0
1 0 0 0 0 1 1 0
0 1 0 0 0 0 0 1
0 1 0 0 0 0 0 1
0 0 1 0 0 0 1 0
0 0 1 0 0 1 0 0
0 0 0 1 1 0 0 0

這個文件第一行是8，說明這個圖有8個頂點，隨后在第2行到第9行，則是圖的頂點名稱，第10行到末尾，則是該圖的鄰接矩陣。

根據不同的圖，在記事本程序中完成這樣的數據是非常簡單的事情，哪怕錯了再修改也是很容易做到。

1 設計圖的存儲結構以及數據文件讀取

圖的存儲、無論哪種方法，都是由兩部分組成的，一個是頂點名稱集合，一個是頂點關系集合，在鄰接矩陣方式中，頂點名稱是一個字符串數組，而頂點關系則是一個矩陣、這個矩陣在C語言中是一個二維數組。于是圖的結構可以是：

struct Graph
{int    A[100][100]; //鄰接矩陣char  V[100][20];  //頂點名稱矩陣，100行，每個名稱字符串不超過20字節int num;          //頂點個數int  Visited[100];  //訪問記錄表
};

但這樣的定義很死板，它假設程序最大是100個頂點，實際我們的教材中就是這么定義的。但幸好我們前面已經知道該怎么處理二維數組，于是這里我們可以動態申請內存，以保證在很多頂點的情況也能使用，對二維數組，則上述定義變為：

struct Graph
{int  **pA;  //鄰接矩陣指針char **pV;  //頂點名稱指針int num;    //頂點個數int *Visited;//訪問記錄表指針
};

對這樣數組的構造，參見第5部分：數組，好在我們前面有過介紹。

回憶一下，如有數組：

int A[3][3]={{1,2,3},{4,5,6},{7,8,9}};

則A[0]、A[1]、A[2]則代表每一行的地址，一般稱為行首地址，比如這三行行首地址分別是[100]、[200]、[300]，這三個地址數據分別存儲在地址[2000]、[2001]、[2002]的存儲空間里，則地址[2000]就是這個數組A的含義，就是所謂行首地址數組的首地址。
反過來，如:

int *p[3];
p[0]=A[0];p[1]=A[1];p[2]=A[2];

上面的式子里，如p[0]地址為[3000]、[3001]、[3002]，其中的內容保存的是100、200、300，這樣就相當于保存了A數組的行首地址，所以p就是個二維數組行首指針數組，只不過它僅僅是三行的二維數組。如把p[0]的地址給另外一個指針變量pA，則pA就是：

int  **pA;

假如這個變量的地址在[5000]，給這個變量賦值：

pA=&p[0];

于是地址[5000]中將存儲3000，這里pA和A的含義是一致的。實際數組A本身就是地址[5000]，如有以下語句：

X=A[1][2];

就是從A的地址[5000] 、讀到內容3000、再從3001讀到200、再從200后取第1個數，過程如下圖3所示：

針對n個頂點，則初始化一個圖的函數就是：

#define VLENGTH 20     //定義每個頂點名稱不超過20字節
struct Graph *GraphInit(int n)
{int i;struct Graph *g;if(n<=0) return NULL;g=(struct Graph *)malloc(sizeof(struct Graph));g->num=n;g->pA=(int  **)malloc(sizeof(int )*n);g->pV=(char **)malloc(sizeof(char)*n); for(i=0;i<n;i++){g->pA[i]=(int  *)malloc(sizeof(int)*n);g->pV[i]=(char *)malloc(sizeof(char)*VLENGTH);}g->Visited=(int *)malloc(sizeof(int )*n); for(i=0;i<n;i++)g->Visited[i]=0; return g;
}

注意第9行，是為行首地址數組申請內存；

注意第13行，是為每行數據申請存儲空間；

注意第14行，前面定義每個頂點的名稱是VLENGTH長度，這里是20字節。

由于C語言的指針可以用下標法讀寫內容，所以完全可以把pA、pV當做普通的二維數組來處理，此處不再敘述。

2 從文件中讀數據到鄰接矩陣和頂點名稱矩陣

這個過程在鏈表的處理中已經介紹過了，只不過數據格式有差異而已。針對我們前面介紹的數據格式，讀數據文件并構造圖的函數如下：

struct Graph * GraphCreat(char FileName[20])
{int i,j,n;FILE *fp,*fopen();struct Graph *G;fp=fopen(FileName,"r");if(fp==NULL) return NULL;fscanf(fp,"%d",&n);G=GraphInit(n);for(i=0;i<n;i++)fscanf(fp,"%s",G->pV[i]);for(i=0;i<n;i++)for(j=0;j<n;j++)fscanf(fp,"%d",&G->pA[i][j]);fclose(fp);return G;
}

第8行首先讀文件中頂點個數，然后根據頂點個數、使用GraphInit()申請內存并構造這個圖的存儲空間，然后在第10行讀n個頂點名稱、在第12行按二維數組的組織讀鄰接矩陣。最后，返回G就是包含有頂點名稱、鄰接矩陣的圖的存儲空間。

有了這兩個函數后，就可以編寫main()來測試它們，就是：

main()
{int i,j;struct Graph *G;G=GraphCreat("p176G719.txt");//打印頂點名稱for(i=0;i<G->num;i++)printf("%s ",G->pV[i]);printf("\n");//打印鄰接矩陣for(i=0;i<G->num;i++) {for(j=0;j<G->num;j++)printf("%d ",G->pA[i][j]);printf("\n");}
}

這個程序第5行，你可以修改成用scanf()來讀到一個文件名稱字符串，然后，就可以使用任何格式符合要求的數據文件了。
G0.C中還包含有GraphFirstAdj()、GraphNextAdj()、GraphDestory()三個函數，這些函數的意義你能看懂么？

2 深度優先遍歷的編程實現

從前面算法分析過程可知：對一個圖的深度優先遍歷，實際就是從第n個頂點開始、標記該頂點已被訪問，然后查找該頂點上第一個和它相連、并且未被訪問到的頂點、比如是第i個頂點，再去第i個頂點，如此繁瑣的說這些，實際就是：

void DFS(struct Graph *G,int n)
{int i;if(G==NULL) return;if(n<0||n>G->num) return;G->Visited[n]=1;printf("%s ",G->pV[n]); for(i=0;i<G->num;i++)if(G->pA[n][i]!=0&&G->Visited[i]!=1) DFS(G,i);
}

第6行是標記該頂點被訪問；

第9行就是：查找第n個頂點上、未被訪問到的頂點，如找到該頂點、且頂點編號是i，則再次DSF(G,i)；

有了這個函數后，構造main()開始從第0個頂點遍歷圖1，就是：

main()
{int i,j;struct Graph *G;G=GraphCreat("p176G719.txt");for(i=0;i<G->num;i++)printf("%s ",G->pV[i]);printf("\n");for(i=0;i<G->num;i++) {for(j=0;j<G->num;j++)printf("%d ",G->pA[i][j]);printf("\n");}DFS(G,0);printf("\n");
}

進一步測試該函數，按圖1的數據仔細分析下它的執行過程，如有圖的連接分量不為1，則會在第一個連接分量遍歷完成后終止。如下圖4，在G1.C中是無法全部遍歷完成的。這個圖的文件在G4.TXT，修改表23中第5行，從G4.TXT中讀數據，則會發現這個程序僅僅遍歷了A、B、C、D，而沒有到達過E、F、G這三個頂點。

為確保多個分量的圖都能順利遍歷完成，則該函數退出后還需要判斷是有頂點是否確保全部遍歷完成、并確保每次遍歷開始的時候、其訪問數組Visited[]中全部是0，就是：

void DFSTraverse(struct Graph *G)
{int i;if(G==NULL) return;for(i=0;i<G->num;i++)G->Visited[i]=0;for(i=0;i<G->num;i++)if(G->Visited[i]==0) DFS(G,i); 
}

表24中函數，很容易修改成計算圖的連接分量的函數，這個工作就由同學們自己完成。如果你遇到困難無法完成，參見G3.C
略加修改main()函數，補充：

DFSTraverse(G);

即可完成圖4的深度優先遍歷。到此，C語言的深度優先遍歷到此結束。

四、圖的遍歷及其應用

1 圖的關節點

圖的關節點、在圖上或許僅僅是個理論或者方法，但對GIS而言，卻絕對是個重要意義的理論、盡管目前還沒見到這類應用。
求解圖的關節點、是典型的深度優先遍歷應用，首先我們從教材中找到G5的圖，其鄰接矩陣如下：

從A點開始、進入A點后由鄰接矩陣右端向左遍歷，其結果就是：ALMJBHKGIDECF

仔細根據上述結果、可以得到圖5這樣的深度遍歷生成樹。

注意圖5：每個結點上標注的數字是在深度優先遍歷上抵達的次序。

對這個鄰接矩陣，我們從右向左做了深度優先遍歷，這代表著一個方向，然后，我們要從左到右、在遍歷的時候、逐個結點尋找與當前結點相連的最小次序結點（這里一直沒想好個比較恰當的措辭來描述這個概念），而這個結點、則構成了所謂的回邊路徑，如圖5中虛線所指的線路，如J-L、B-A等線路。這種線路很關鍵：它的物理意義是：你可以通過B直接抵達A、或者C直接抵達A、G直接抵達B等等，這些回邊路徑，則立刻喻示著你炸毀K點、對I點則沒什么影響。

從右向左深度優先遍歷，這里的現實意義就是說：從其他各個頂點回到A的情況。

相連最小次序結點序號，通常用Low[ ]數組來表示，比如J結點，這個值就是2，它代表著J可以抵達第2個遍歷到的結點L，這就是所謂的回邊路徑。同理，對于C，這個值是1，它代表著在C點，可以直接到A。

如果當前結點下標是v，而在Visited[v]代表這個結點深度遍歷中的次序，w代表v頂點在生成樹上的孩子結點下標，k代表v的祖先結點下標，則：

Low[v]=min{Visited[v],Low[w],Visited[k]}

當然，這個式子很簡潔，要真正計算出來Low[ ]的值、顯然要在程序上說了算。而要在編程中體現這些，還要首先是能手工計算出這個值來。

2 關節點的計算

首先我們設計表格如下：

(1) 頂點A，步驟1

對于A，它就是來自步驟1，就是A，于是Low為1。

(2) 頂點L，步驟2

現在，根據遍歷的次序，我們抵達L這個頂點，注意L的鄰接矩陣：

從表27可知：深度優先遍歷經過的頂點里有A、J、M，其中只有A是深度優先遍歷訪問過的頂點、所以最小次序號是1，也就是A是L能直接抵達的回邊路徑上的頂點，所以，表26就是以下結果：

(3) 頂點M，步驟3

現在，我們根據表28抵達頂點M，這個頂點的鄰接矩陣表如下：

這個地方可以看到：M可以和B、J、L相連，但B、J尚未被訪問過，而M又從L而來，所以此時M的回邊就是L的回邊，于是有：

(4) 頂點J，步驟4

根據遍歷的次序，我們進入頂點J，此時鄰接矩陣如下：

對于頂點J，這里可知與L、M相連，從表30知道L是步驟2到達、M是步驟3到達，取步驟次序最小、即為2，它意味著在頂點J上可以抵達深度遍歷次序為2的頂點、就是L，于是有：

從這個表第4步，我們回頭看圖5，就相當于J與L之間的連接虛線。在L、M之間找最小連接次序的意義是：把M炸掉、J依然能回到L。

(5) 頂點B，步驟5

依然要看鄰接矩陣，B頂點是：

在這里，我們發現B與A、C、D、G、H、M相連，其中：A、M是深度優先遍歷已經遍歷過得頂點，找最小次序的、就是A，也就是第一步就抵達的頂點，所以有：

(6) 頂點H，步驟6

再次看鄰接矩陣表，H頂點就是：

可以發現H與B、G、K連接，其中B是深度優先遍歷訪問過的頂點，注意到B的是在第5步訪問的，所以有：

對于頂點H，該頂點是由鄰接矩陣這種硬性連接造成的回邊路徑只能是5、就是說它只能通過B回到A，這就非常麻煩，立刻喻示著B是一個關節點。

(7) 頂點K，步驟7

同樣要仔細看鄰接矩陣，K就是：

我們看到K與G、H相連，但這兩個頂點目前都沒有被深度優先遍歷訪問到，此時的情況、立刻說明從鄰接矩陣中無法得到Low，同表28的頂點M情況一致，就是說從H頂點來，而H頂點又來自B，所以K的Low也是5。

這現實意義也很明確：如果把B炸毀了、K就是受害者，當然H也是。

(8) 頂點G，步驟8

還是看G的鄰接矩陣：

在這個表中可知：G連接有B、H、I、K，其中B、H、K是深度優先遍歷都訪問過的，這3個頂點里，以訪問B的步驟最小，就是5，于是：

對這個結果還能說什么？意味著B炸掉后又多了個受害者。

(9) 頂點I，步驟9
同樣要看鄰接矩陣，對于I就是：

這個頂點更不幸，它僅僅與G相連，對于這樣的頂點，我們知道訪問到G的步驟：8，就是這個頂點的Low，就是：

回憶我們對B-H路徑的分析，我們知道此時的G同樣是I的關節點，I回到A，必須經過G。如果炸掉G、B這樣的頂點，I城市就算沒救了。

(10) 頂點D，步驟10

還是先看鄰接矩陣，對于D，就是：

可知頂點D與B、E相連，對于D，此時最先抵達的頂點是B，在步驟5，所以有：

這個結果說明B依然是控制著D的生命線。

(11) 頂點E，步驟11

還是看E的鄰接矩陣，就是：

可以知道E與D直接相連，于是回邊上另一個頂點D、也就是在步驟D，于是：

總結下：設當前頂點為v，下一個頂點是w，其步驟都在Visited[ ]中保存，則：

Low[w]>= Visited[v]

則v必然是關節點，比如此時v是頂點D，而w代表E；或者v是頂點B，而w代表H、K等頂點。

從圖5中我們不難發現炸掉D確實能孤立E。

(12) 頂點C，步驟12

還是看鄰接矩陣，在頂點C有：

從這個地方可知C與A、B相連，這兩個頂點都在第1、5步驟訪問過，顯然回到A最直接，于是此時Low為1。

由于有這個回邊線路，所以看圖5我們就知道：炸掉B對這個結點不起任何作用。

最后一個頂點F，看鄰接矩陣表可知與A相連，所以表46中自行寫入1即可，不再重復計算。

到此，G5圖中各個頂點回到A頂點路徑上、各個回邊和關節點計算完畢，我們回顧這個過程不難發現：A、B、G、D是這個圖的關節點。

在關節點上分割圖，立刻可以將一個圖分割成若干個不相連的子圖，這就是圖論中對關節點的要求。

2 關節點計算的編程實現

根據上面計算的過程，我們可以總結如下：

關節點的計算首先要獲得Low[ ]，如設圖為G，則計算過程分兩種情況：

（1） 深度遍歷過程中，如到當前頂點v，如該頂點鄰接頂點沒有被深度優先遍歷訪問過，如前面的M、K這兩個頂點，則此時該頂點最早回邊頂點值(Low)等同前一節點值，也就是：G->Low[v]=G->Low[w]；

（2） 在遍歷過程中，如到當前頂點v，該結點鄰接矩陣中可以找到已經遍歷過的鄰接頂點，則G->Low[v]= min(G->Visited[w]);，如B、J等。

而關節點的判斷條件則是：

遍歷過程中，如當前頂點為v，鄰接頂點為w，如滿足：

G->Low[w]>=G->Visited[v]

如v是頂點B、w是頂點H，則v是關節點。

為了滿足上述計算要求，我們首先修改Graph的定義，補充內容如下：

struct Graph
{int  **pA;char **pV;int num;int *Visited;int  Count;int *Low;
};

新補充的變量Count是一個計數器，用來計算深度優先遍歷的步驟，有這個步驟，我們才能在圖5上標注每個結點在深度優先遍歷中是在哪一步到達的。而對于Low[ ]，我們知道這里是最小回邊的次序號，定義為指針是準備按頂點個數來動態申請內存，由此，我們圖的初始化函數就是表27。

同表19的程序實際沒什么差別，僅僅是初始化了Low[ ]這個數組。
深度優先遍歷的過程，同前面的過程實際完全一致，但此時Visited[ ]中將不是簡單的把已經訪問過得頂點如v設置成1，而是要標記步驟，標記步驟，就是讓深度優先遍歷的過程中，每次都要進行：

++G->Count;

然后把這個結果賦值給：

G->Visited[v]=Count;

其中v是遍歷到當前結點的下標。

所以能標記步驟的深度優先遍歷就是表28，運行下這個程序，你會看到遍歷結果，逐個將Visited[ ]中的值打印出來，就有了深度優先遍歷到每個頂點的步驟。

struct Graph *GraphInit(int n)
{int i;struct Graph *g;if(n<=0) return NULL;g=(struct Graph *)malloc(sizeof(struct Graph));g->num=n;g->pA=(int  **)malloc(sizeof(int )*n);g->pV=(char **)malloc(sizeof(char)*n); for(i=0;i<n;i++){g->pA[i]=(int  *)malloc(sizeof(int)*n);g->pV[i]=(char *)malloc(sizeof(char)*VLENGTH);}g->Visited=(int *)malloc(sizeof(int )*n); g->Low=(int *)malloc(sizeof(int )*n); for(i=0;i<n;i++){g->Visited[i]=0; g->Low[i]=0;}g->Count=0;return g;
}

表48補充了Low[ ]空間申請、Low[ ]構造初始值的語句，基本是表19程序的補充。

void DFS(struct Graph *G,int v)
{int w;if(G==NULL) return;if(v<0||v>G->num) return;++G->Count; G->Visited[v]=G->Count; printf("%3s",G->pV[v]);for(w=G->num-1;w>=0;w--)if(G->pA[v][w]!=0) {if(G->Visited[w]==0)DFS(G,w);}
}

同原來的DFS()相比，就是加了個計數器并能記錄步驟，補充如G4.c的main()，讀進文件P719G5.txt的數據來計算，這樣，你就獲得了深度優先遍歷的結果和步驟。注意表49第9行，我們是從鄰接矩陣右邊向左開始遍歷。

有了遍歷步驟計數，下面就準備計算Low[ ]，回顧第18頁對Low[ ]計算的總結，先設定min是我們要計算的值，并假設在開始、這個值就是當前頂點v被遍歷到的步驟，也就是有這樣的假設：

min=G->Visited[v]=Count;

注意(1)的結果：如果進入第v個頂點后、如果該頂點鄰接頂點沒有一個被深度優先遍歷訪問過，也就是該情況在表49第13行所在位置，于是修改這里為：

if(G->Visited[w]==0)
{DFS(G,w);if(G->Low[w]<min) min=G->Low[w];
}

此種情況下如M、K這兩個頂點，該情況下就是說只能原路返回、其Low[v]值是前一個的Low[w]的值。注意這里w是一個循環變量，逐個尋找沒找到與v相連的、被深度優先遍歷訪問過的。

另外一種情況則是說：假如當前結點v的鄰接頂點里、其中有被深度優先遍歷訪問過的，這種情況下，要把訪問過的頂點次序依次排列、找到最小的值。這樣，就是在上述代碼下添加一下內容：

if(G->Visited[w]==0){DFS(G,w);if(G->Low[w]<min) min=G->Low[w];}
else  if(G->Visited[w]<min) min=G->Visited[w];

同樣，w作為循環變量，是逐個計算著其中最小的值。如此計算的min、其值就是Low[v]的值，現在，深度優先遍歷的代碼就是：

void DFS(struct Graph *G,int v)
{int w,min;if(G==NULL) return;if(v<0||v>G->num) return;G->Visited[v]=min=++G->Count; //設置當前頂點步驟，假設min就是當前步驟printf("%3s",G->pV[v]);for(w=G->num-1;w>=0;w--)if(G->pA[v][w]!=0) {if(G->Visited[w]==0)  //沒有頂點被訪問過{DFS(G,w);if(G->Low[w]<min) min=G->Low[w];}else  if(G->Visited[w]<min) min=G->Visited[w]; //有被訪問的頂點}G->Low[v]=min; 
}

在循環體外，第18行，則將min賦值給當前頂點Low[ ]，到此，Low[ ]計算完畢。
如果要顯示關節點，根據我們前面分析的結果，則在第14行下加入：

if(G->Low[w]>=G->Visited[v]) printf("%3s\n",G->pV[v]);  

為了讓顯示明了，表50中第7行關于遍歷的結果、就不要顯示了，最好注釋掉。到這里，有關關節點的計算全部完成。

關節點的含義是：從這里分割一個圖，將會得到互相不連的若干子圖，此種情況下又涉及到圖的另一個問題：有向圖的強連通分量的計算，簡述就是頂點之間可以兩兩抵達。以下圖有3個連通分量{1,2,3,4},{5},{6}，過去，求連通分量要兩次DFS，后來產生了Tarjan算法，從而可以快速獲得連通分量。

實際說起來關節點的計算方法、是來自Tarjan算法，是在先能計算連通分量后、才發展到去計算關節點的，有了上面關節點的計算，你能計算圖6的連通分量么？這個圖的鄰接矩陣數據見G10.TXT。