圖的深度優先演算法

A. 圖的深度優先搜索演算法dfs函數裡面firstadjvex是什麼意思

FirstAdiVex(G,v);
初始條件：圖G存在，v是G中某個頂點。
操鏈辯作結果：返回v的第一個領接頂點，若弊野定點在G中沒有領接頂點，則返回棚卜缺空。

B. 圖的矩陣深度和廣度遍歷演算法

圖的遍歷是指從圖中任一給定頂點出發，依次訪問圖中的其餘頂點。如果給定的圖是連通圖，則從圖中的任意一點出發，按照一個指定的順序就可以訪問到圖中的所有頂點，且每個頂點只訪問一次。這個過程稱為圖的遍歷。
圖的遍歷比樹的遍歷復雜的多。樹是一種特殊類型的圖，即無圈（無迴路）連通圖。樹中的任意兩個頂點間都有唯一的路徑相通。在一個頂點被訪問過之後，不可能又沿著另外一條路徑訪問到已被訪問過的結點。而圖中的頂點可能有邊與其他任意頂點相連
。因此在訪問了某個頂點之後，可能沿著另一條邊訪問已被訪問過的頂點。例如圖（a）中的G1，在訪問了V1，V2和V3之後，有可能沿著邊（V3，V1）訪問到V1。為了避免一頂點被多次訪問，可以設立一個集合Visited，用來記錄已被訪問過的頂點。它的初值為空
集。一旦V1被訪問過，即把V1加到集合Visited中。圖的遍厲通常有兩種:圖的深度優先
搜索和圖的廣度優先搜索。
1）圖的深度優先搜索
從圖G=（V，E）的一個頂點V0出發，在訪問了任意一個與V0相鄰且未被訪問過的頂點W1之後，再從W1出發，訪問和W1相鄰且未被訪問過的頂點W2，然後再從W2出發進行如上所述訪問，直到找到一個它相鄰的結點，都被訪問過的結點為止。然後退回到尚有相
鄰結點未被訪問過的頂點，再從該頂點出發，重復上述搜索過程，直到所有被訪問過的頂點的鄰接點都被訪問過為止。圖的這種遍歷過程就稱為圖的深度優先搜索。例如從頂點V1出發對圖3.3.5進行深度優先搜索，遍歷的順序為 V1,V2,V5,V10,V6,V7,V3,V12,V1
1,V8,V4,V9。（與鄰接表中的鄰接點排列順序有關，即p->next.vertex=v2 or v3對遍歷
順序有影響 ）
例25.(p194.c)圖的深度優先搜索。從圖G的頂點V0
發進行深度優先搜索，列印出各個頂點的遍歷順序。
解：圖的深度優先搜索法為：
（1）首先訪問V0並把V0加到集合visited中；
（2）找到與V0相鄰的頂點W，若W未進入
visited中，則以深度優先方法從W開始搜索。
（3）重復過程（2）直到所有於V0相鄰的頂點
都被訪問過為止。

下面是對用鄰接表表示的圖G進行深度優先搜索的程序
int rear=0; /*Visit和rear都為全局變數*/
int visit[500];
depth_first_search(g,v0) /*從V0開始對圖G進行深度
優先搜索*/
graphptr g[ ]; /*指針數組,為鄰接表表頭頂點指針
g[vi]...g[vn]*/
int v0; /*這里V0和W都是頂點標號,如V0=0或1*/
{ /*g[v0]是頂點V0的表頭指針*/
int w;
graphptr p; /*鏈表的結點指針*/
visit [++rear]=v0;
printf("%d\n",v0);
p=g[v0];/*指定一個頂點，通過鄰接表表頭指針
，訪問v0的鄰接頂點*/
while (p!=NULL)
{
w=p->vertex ;/*這里W是與V0相鄰的一個頂點*/
if (!visited(w))/*當V0的相鄰結點，W未被訪問時，從W開始遍厲*/
depth_first_search(g,w);
p=p->next;/*接著訪問另一個相鄰頂點*/
}
}
int visited(w) /*檢查頂點w是否進入visited(w)*/
int w ;
{
int i;
for (i=1;i<=rear;i++)
if (visit [ i ] == w) return(1);/*W在visit[]中，說明被訪問過*/
return(0); /*W不在visit[]中，說明未被訪問過，返回0*/
}
2）圖的廣度優先搜索
從圖G的一個頂點V0出發，依次訪問V0的鄰接點K1,K2...Kn。然後再順序訪問K1,K2...Kn的所有尚未被訪問過的鄰接點。如此重復，直到圖中的頂點都被訪問過為止。圖的這種搜索稱為圖的廣度優先搜索。例如：從V1出發按廣度優先搜索方法遍歷圖3.3.5,頂
點的訪問順序為V1,V2,V3,V4,V5,V6,V7,V8,V9,V10,V11,V12。
圖的廣度優先搜索類似樹的按層次遍歷，需要有一個隊列來存放還沒
有來得及處理的頂點。圖的廣度優先搜索演算法為：
（1）首先把V0放入隊列；
（2）若隊列為空則結束，否則取出隊列的頭V；
（3）訪問V並把所有與V相鄰且未被訪問的頂點插入隊列；
（4）重復（2）-（3）直到隊列為空。
上述演算法中所有已被訪問過的頂點都放在隊列中，因此只要檢查某個頂點是否在隊列中就可以判斷出該頂點是否已被訪問過。
廣度搜索法的程序如下：
broad_first_search(g,v0) /*從V0開始對圖g進行廣度優先搜索*/
graphptr g[ ]; /*為鄰接表，表頭頂點指針*/
int v0;
{
int queue[500],front =1, tail=1,v;
graphptr p;
queue [tail]=v0; /*把V0插入隊列queue*/
while (front <=tail)/*當隊列不為空*/
{
v=queue[front++]; /*取出隊列中的頂點*/
printf("%d\n",v); /*訪問該頂點*/
p=g[v]; /*從頂點V的鏈表來考慮與V相鄰的頂點*/
while (p!=NULL)
{
v=p->vertex; /*從第一個結點（即邊）中找出相鄰的頂點*/
if (!visited(queue,tail,v))/*判斷頂點是否進入隊列，如進入隊列
說明已被訪問或將要訪問*/
queue[++tail]=v;/*如果該頂點未被訪問過，將此相鄰頂點插入隊列*/
p=p-->next;/*再考慮該結點的下一個相鄰頂點*/
}
}
}
visited (q,tail,v)/*判斷頂點是否被訪問過，訪問過時，返回1，否則返回0*/
int q[ ],tail,v;/*進入隊列的頂點，在front之前的頂點已被訪問過列印輸出，
在front和tail之間的頂點是即將要訪問頂點*/
{
int i;
for(i=1;i<=tail;i++)/*掃描隊列，確定v是否在隊列中，在隊列中返回1，否則返回0*
/
if (q[i]==v)return(1);/*隊列中的頂點都認為已被訪問過*/
return(0);
}

深度優先的非遞歸演算法

/*設當前圖(或圖的某個連通分枝)的起始訪問點為p*/
NodeType stackMain,stackSec
visit(p)
p->mark=true;
do
{
for(all v isTheConnectNode of (G,p))//將當前點的鄰接點中的所有結點壓入副棧中
if(v.marked==false)
statckSec.push(v)
//將副棧中的點依次彈出，壓入主棧中，這與非遞歸演算法中使用隊列的意圖類似
while(!stackSec.isEmpty())
stackMain.push(statckSec.pop());
do//找出下一個未訪問的結點或者沒找到，直到棧為空
{
if(!stackMain.isEmpty())

{
p=stackMain.pop();

}
}while(p.marked==true&&!stackMain.isEmpty())
if(p.marked==false)//訪問未訪問結點.

{

visit(p);

p.marked=true;

}

}while(!stackMain.isEmpty())

C. 圖遍歷演算法之DFS/BFS

在計算機科學， 圖遍歷（Tree Traversal，也稱圖搜索）是一系列圖搜索的演算法， 是單次訪問樹結構類型數據（tree data structure)中每個節點以便檢查或更新的一系列機制。圖遍歷演算法可以按照節點訪問順序進行分類，根據訪問目的或使用場景的不同，演算法大致可分為28種：

圖遍歷即以特定方式訪問圖中所有節點，給定節點下有多種可能的搜索路徑。假定以順序方式進行（非並行），還未訪問的節點就需通過堆棧（LIFO）或隊列（FIFO）規則來確定訪問先後。由於樹結構是一種遞歸的數據結構，在清晰的定義下，未訪問節點可存儲在調用堆棧中。本文介紹了圖遍歷領域最流行的廣度優先搜索演算法BFS和深度優先搜索演算法DFS，對其原理、應用及實現進行了闡述。通常意義上而言，深度優先搜索（DFS）通過遞歸調用堆棧比較容易實現，廣義優先搜索通過隊列實現。

深度優先搜索（DFS）是用於遍歷或搜索圖數據結構的演算法，該演算法從根節點開始（圖搜索時可選擇任意節點作為根節點）沿著每個分支進行搜索，分支搜索結束後在進行回溯。在進入下一節點之前，樹的搜索盡可能的加深。
DFS的搜索演算法如下（以二叉樹為例）：假定根節點（圖的任意節點可作為根節點）標記為 ,
(L) : 遞歸遍歷左子樹，並在節點 結束。
(R): 遞歸遍歷右子樹，並在節點 結束。
(N): 訪問節點 。
這些步驟可以以任意次序排列。如果（L）在（R）之前，則該過程稱為從左到右的遍歷；反之，則稱為從右到左的遍歷。根據訪問次序的不同，深度優先搜索可分為 pre-order、in-order、out-order以及post-order遍歷方式。

（a）檢查當前節點是否為空；
（b）展示根節點或當前節點數據；
（c）遞歸調用pre-order函數遍歷左子樹；
（d）遞歸調用pre-order函數遍歷右子樹。
pre-order遍歷屬於拓撲排序後的遍歷，父節點總是在任何子節點之前被訪問。該遍歷方式的圖示如下：

遍歷次序依次為：F -B -A-D- C-E-G- I-H.

（a）檢查當前節點是否為空；
（b）遞歸調用in-order函數遍歷左子樹；
（c）展示根節點或當前節點數據；
（d）遞歸調用in-order函數遍歷右子樹。
在二叉樹搜索中，in-order遍歷以排序順序訪問節點數據。該遍歷方式的圖示如下：

遍歷次序依次為：A -B - C - D - E - F - G -H-I

（a）檢查當前節點是否為空；
（b）遞歸調用out-order函數遍歷右子樹；
（c）展示根節點或當前節點數據；
（d）遞歸調用out-order函數遍歷左子樹。
該遍歷方式與LNR類似，但先遍歷右子樹後遍歷左子樹。仍然以圖2為例，遍歷次序依次為：H- I-G- F- B- E- D- C- A.

（a）檢查當前節點是否為空；
（b）遞歸調用post-order函數遍歷左子樹；
（c）遞歸調用post-order函數遍歷右子樹；
（d）展示根節點或當前節點數據。
post-order遍歷圖示如下：

遍歷次序依次為：A-C-E-D-B-H-I-G-F.

pre-order遍歷方式使用場景：用於創建樹或圖的副本；
in-order遍歷使用場景：二叉樹遍歷；
post-order遍歷使用場景：刪除樹

遍歷追蹤也稱樹的序列化，是所訪問根節點列表。無論是pre-order，in-order或是post-order都無法完整的描述樹特性。給定含有不同元素的樹結構，pre-order或post-order與in-order遍歷方式結合起來使用才可以描述樹的獨特性。

樹或圖形的訪問也可以按照節點所處的級別進行遍歷。在每次訪問下一層級節點之前，遍歷所在高層級的所有節點。BFS從根節點（圖的任意節點可作為根節點）出發，在移動到下一節點之前訪問所有相同深度水平的相鄰節點。

BFS的遍歷方法圖示如下：

遍歷次序依次為： F-B-G-A-D-I-C-E-H.

圖演算法相關的R包為igraph，主要包括圖的生成、圖計算等一系列演算法的實現。

使用方法：

參數說明：

示例：

結果展示：

DFS R輸出節點排序：

使用方法：

參數含義同dfs
示例：

結果展示：

BFS R輸出節點排序：

以尋找兩點之間的路徑為例，分別展示BFS及DFS的實現。圖示例如下：

示例：

輸出結果：

示例：

輸出結果：

[1] 維基網路： https://en.wikipedia.org/wiki/Tree_traversal
[2] GeeksforGeeks: https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
[3] http://webdocs.cs.ualberta.ca/~holte/T26/tree-traversal.html
[4]Martin Broadhurst, Graph Algorithm: http://www.martinbroadhurst.com/Graph-algorithms.html#section_1_1
[5]igraph: https://igraph.org/r/doc/dfs.html
[6]igraph: https://igraph.org/r/doc/bfs.html
[7] Depth-First Search and Breadth-First Search in python: https://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/

D. 圖的廣度、深度優先搜索和拓撲排序

廣度優先搜索是最簡單的圖搜索演算法之一。之所以得名是因為該演算法始終將已經發現的結點集合，沿著其 廣度方向 向外擴展去尋找未發現結點。
具體演算法執行過程如下圖所示：

深度優先搜索，只有可能就在圖中盡可能的 深入 ，總是從最近才發現的結點出發，尋找下一個結點。
具體演算法執行過程如下圖所示：

拓撲排序是計算機中經常遇到的概念，下面用於《演算法導論》的定義

如下圖3-1所示，事件E1完成之後，可以同時執行事件E2和E3，兩事件執行結束之後，執行事件E4，最後可以同時執行事件E5和E6。每個事件的執行都依賴於它之前事件是否執余槐陪行完成，執行的順序是固定的，這樣的線性順序就是 拓撲排序 。

圖的廣度、深度優先搜索和拓撲排序是圖論演算法中的基礎，也是實踐中經常遇到的問題。在考研和面試筆試中會通過選擇題或者填空題考察，學習理解上文圖示中的演算法思想，輔助練習問題不大。當然也有關於這里的演算法題，例如LeetCode815公交路線問題，就是利用圖的廣度優先搜索求解，因豎蠢為解題復雜，並且在平時的應試中出現概率不大，這里不做詳細講解。有興趣的可明段以在LeetCode中搜索，題目後面有我提交過的題解。

E. 基本演算法——深度優先搜索（DFS）和廣度優先搜索（BFS）

        深度優先搜索和廣度優先搜索，都是圖形搜索演算法，它兩相似，又卻不同，在應用上也被用到不同的地方。這里拿一起討論，方便比較。

一、深度優先搜索

        深度優先搜索屬於圖演算法的一種，是一個針對圖和樹的遍歷演算法，英文縮寫為DFS即Depth First Search。深度優先搜索是圖論中的經典演算法，利用深度優先搜索演算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。一般用堆數據結構來輔助實現DFS演算法。其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次。

基本步奏

（1）對於下面的樹而言，DFS方法首先從根節點1開始，其搜索節點順序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中優先選擇左分枝）。

（2）從stack中訪問棧頂的點；

（3）找出與此點鄰接的且尚未遍歷的點，進行標記，然後放入stack中，依次進行；

（4）如果此點沒有尚未遍歷的鄰接點，則將此點從stack中彈出，再按照（3）依次進行；

（5）直到遍歷完整個樹，stack里的元素都將彈出，最後棧為空，DFS遍歷完成。

二、廣度優先搜索

        廣度優先搜索（也稱寬度優先搜索，縮寫BFS，以下採用廣度來描述）是連通圖的一種遍歷演算法這一演算法也是很多重要的圖的演算法的原型。Dijkstra單源最短路徑演算法和Prim最小生成樹演算法都採用了和寬度優先搜索類似的思想。其別名又叫BFS，屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。基本過程，BFS是從根節點開始，沿著樹(圖)的寬度遍歷樹(圖)的節點。如果所有節點均被訪問，則演算法中止。一般用隊列數據結構來輔助實現BFS演算法。

基本步奏

（1）給出一連通圖，如圖，初始化全是白色（未訪問）；

（2）搜索起點V1（灰色）；

（3）已搜索V1（黑色），即將搜索V2，V3，V4（標灰）；

（4）對V2，V3，V4重復以上操作；

（5）直到終點V7被染灰，終止；

（6）最短路徑為V1，V4，V7.

F. 採用鄰接表存儲的圖的深度優先遍歷演算法類似於二叉樹的先序遍歷，為什麼是先序呢

這是因為圖的深度優先遍歷演算法先訪問所在結點，再訪問它的鄰接點。與二叉樹的先序遍歷先訪問子樹的根結點，再訪問它的孩子結點（鄰接點）類似。圖的廣度優先遍歷演算法類似於二叉樹的按層次遍歷。
先序遍歷也叫做先根遍歷、前序遍歷，可記做根左右（二叉樹父結點向下先左後右）。
首先訪問根結點然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹，如果二叉樹為空則返回。
例如，下圖所示二叉樹的遍歷結果是：ABDECF。

(6)圖的深度優先演算法擴展閱讀：
遍歷種類：
一、NLR：前序遍歷(Preorder
Traversal
亦稱（先序遍歷）），訪問根結點的操作發生在遍歷其左右子樹之前。
二、LNR：中序遍歷(Inorder
Traversal)，訪問根結點的操作發生在遍歷其左右子樹之中（間）。
三、LRN：後序遍歷(Postorder
Traversal)，訪問根結點的操作發生在遍歷其左右子樹之後。
注意：
由於被訪問的結點必是某子樹的根，所以N(Node）、L(Left
subtree）和R(Right
subtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為
先根遍歷、中根遍歷和後根遍歷。
參考資料來源：網路-先序遍歷

G. 圖的深度優先遍歷序列什麼唯一

圖的深度優先遍歷序列不唯一的 。如下面這個圖 深度優先遍歷可以是ABEFCD ，也可以是ADCBFE。

假設給定圖G的初態是所有頂點均未曾訪問拍孫過。在G中任選一頂點v為初始出發點(源點)，則深度優先遍歷可定義如下：首先訪問出發點v，並將其標記為已訪問過；然後依次從v出發搜索v的每個鄰接點w。

若w未曾訪問過，則以w為新的出發點繼續進行深度優先遍歷，直至圖中所有和源點v有路徑相通的頂點(亦稱為從源點可達的頂點)均已被訪問為止。

若此時圖中仍有未訪問的頂點，襲數鏈則另選一個尚未訪問的頂點作為新的源點重復上述過程，直至圖中所有頂點均已被訪問為止。

圖的深度優先遍歷類似於樹的前序遍歷。採用的搜索方法的特點是盡可能先對縱深方向進行搜索。這種搜索方法稱為深度優先搜索(Depth-First Search)。相應地，用此方法遍歷圖就很自然地稱之為圖的深度優先遍歷。

(7)圖的深度優先演算法擴展閱讀：

圖的遍歷要比樹的遍歷畢答復雜得多，由於圖的任一頂點都可能和其餘頂點相鄰接，故在訪問了某頂點之後，可能順著某條邊又訪問到了已訪問過的頂點。

因此，在圖的遍歷過程中，必須記下每個訪問過的頂點，以免同一個頂點被訪問多次。為此給頂點附設訪問標志visited，其初值為false，一旦某個頂點被訪問，則其visited標志置為true。

圖的遍歷方法有兩種：

一、深度優先搜索遍歷（Depth-First Search 簡稱DFS）。

二、廣度優先搜索遍歷（Breadth_First Search 簡稱BFS）。

H. DFS(深搜)演算法

深度優先搜索演算法(Depth-First-Search) :是一種用於遍歷或搜索樹或圖的演算法。 沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。當節點v的所在邊都己被探尋過或者在搜尋時結點不滿足條件，搜索將回溯到發現節點v的那條邊的起始節點。整個進程反復進行直到所有節點都被訪問為止。

話說大詩人李白，一生好飲。幸好他從不開車。

一天，他提著酒壺，從家裡出來，酒壺中有酒2斗。他邊走邊唱：

無事街上走，提壺去打酒。
逢店加一倍，遇花喝一斗。

這一路上，他一共遇到店5次，遇到花10次，已知最後一次遇到的是花，他正好把酒喝光了。

請你計算李白遇到店和花的次序，可以把遇店記為a，遇花記為b。則：babaabbabbabbbb 就是合理的次銷念早序。像這樣的答案一共有多少呢？請你計算出所有可能方案的虧雀個數（包含題目給出的）。

注意：通過瀏覽器提交答案。答案是個整數。不要書寫任何多餘的內容。

答案：14

小明剛剛看完電影《第39級台階》，離開高鉛電影院的時候，他數了數禮堂前的台階數，恰好是39級!
站在台階前，他突然又想著一個問題：
如果我每一步只能邁上1個或2個台階。先邁左腳，然後左右交替，最後一步是邁右腳，也就是說一共要走偶數步。那麼，上完39級台階，有多少種不同的上法呢？
請你利用計算機的優勢，幫助小明尋找答案。

要求提交的是一個整數。
注意：不要提交解答過程，或其它的輔助說明文字。

I. 深度優先搜索法和廣度優先搜索法

深度優先搜索所遵循的搜索策略是盡可能「深」地搜索圖。在深度正模優先搜索中，對於最新發現的結點，如果它還有以此為起點而未搜過的邊，就沿著邊繼續搜索下去。當結點v的所有邊都已被探尋過，搜索將回溯到發現結點v有那條邊的始結點。這一過程一直進行到已發現從源結點可達的所有結點為止。如果還存在未被發現的結點，則選擇其中一個作為源結點並重復以上過程，整個過程反復進行直到所有結點都被發現為止。

深度優先搜索基本演算法如下{遞歸演算法}：
PROCEDURE dfs_try(i);
FOR i:=1 to maxr DO
BEGIN
IF 子結點 mr 符合條件 THEN
BEGIN
產生的子結點mr入棧；
IF 子結點mr是目標結點
THEN 輸出
ELSE dfs_try(i+1);
棧頂元素出棧;
END;
END; 寬度優先搜索演算法（又稱廣度優先搜索演算法）是最簡單的圖的搜索演算法之一，這一演算法也是很多重要的圖的演算法的原型。Dijksta單源最短路徑演算法和Prim最小生成樹演算法都採用了與寬度優先搜索類似的思想。
寬度優先搜索的核心思想帶模是：從初始結點開始，應用算符生成第一層結點，檢查目標結點是否在這些後繼結點中，若沒有，再用產生式規則將所有第一層的結點逐一擴展，得到第二層結點，並逐一檢查第二層結點中是否包含目標結點。若沒有，再用算符逐一擴展第舉行緩二層所有結點……，如此依次擴展，直到發現目標結點為止。

寬度優先搜索基本演算法如下：
list[1]:=source; {加入初始結點，list為待擴展結點的表}
head:=0; {隊首指針}
foot:=1; {隊尾指針}
REPEAT
head:=head+1;
FOR x:=1 to 規則數 DO
BEGIN
根據規則產生新結點nw;
IF not_appear(nw,list) THEN {若新結點隊列中不存在，則加到隊尾}
BEGIN
foot:=foot+1;
list[foot]:=nw;
list[foot].father:=head;
IF list[foot]=目標結點 THEN 輸出；
END；
END；
UNTIL head>foot; {隊列為空表明再無結點可擴展}

J. 求c語言圖的深度優先遍歷演算法

#define MaxVerNum 100 /* 最大頂點數為*/
typedef enum {False,True} boolean;
#include "stdio.h"
#include "stdlib.h"
boolean visited[MaxVerNum];

typedef struct node /* 表結點*/
{
int adjvex;/* 鄰接點域,一般是放頂點對應的序號或在表頭向量中的下標*/
char Info; /*與邊(或弧)相關的信息*/
struct node * next; /* 指向下一個鄰接點的指針域*/
} EdgeNode;
typedef struct vnode /* 頂點結點*/
{
char vertex; /* 頂點域*/
EdgeNode * firstedge; /* 邊表頭指針*/
} VertexNode;
typedef struct
{
VertexNode adjlist[MaxVerNum]; /* 鄰接表*/
int n,e; /* 頂點數和邊數*/
} ALGraph; /* ALGraph是以鄰接表方式存儲的圖類型*/

//建立一個無向圖的鄰接表存儲的演算法如下：
void CreateALGraph(ALGraph *G)/* 建立有向圖的鄰接表存儲*/
{
int i,j,k;
int N,E;
EdgeNode *p;
printf("請輸入頂點數和邊數：");
scanf("%d %d",&G->n,&G->e);
printf("n=%d,e=%d\n\n",G->n,G->e);
getchar();
for(i=0;i<G->n;i++) /* 建立有n個頂點的頂點表*/
{
printf("請輸入第%d個頂點字元信息(共%d個)：",i+1,G->n);
scanf("%c",&(G->adjlist[i].vertex)); /* 讀入頂點信息*/
getchar();
G->adjlist[i].firstedge=NULL; /* 頂點的邊表頭指針設為空*/
}
for(k=0;k<2*G->e;k++) /* 建立邊表*/
{
printf("請輸入邊<Vi,Vj>對應的頂點序號(共%d個)：",2*G->e);
scanf("%d %d",&i,&j);/* 讀入邊<Vi,Vj>的頂點對應序號*/
p=(EdgeNode *)malloc(sizeof(EdgeNode)); // 生成新邊表結點p
p->adjvex=j; /* 鄰接點序號為j */
p->next=G->adjlist[i].firstedge;/* 將結點p插入到頂點Vi的鏈表頭部*/
G->adjlist[i].firstedge=p;
}
printf("\n圖已成功創建!對應的鄰接表如下：\n");
for(i=0;i<G->n;i++)
{
p=G->adjlist[i].firstedge;
printf("%c->",G->adjlist[i].vertex);
while(p!=NULL)
{
printf("[ %c ]",G->adjlist[p->adjvex].vertex);
p=p->next;
}
printf("\n");
}
printf("\n");
} /*CreateALGraph*/

int FirstAdjVertex(ALGraph *g,int v)//找圖g中與頂點v相鄰的第一個頂點
{
if(g->adjlist[v].firstedge!=NULL) return (g->adjlist[v].firstedge)->adjvex;
else return 0;
}

int NextAdjVertex(ALGraph *g ,int vi,int vj )//找圖g中與vi相鄰的，相對相鄰頂點vj的下一個相鄰頂點
{
EdgeNode *p;
p=g->adjlist[vi].firstedge;
while( p!=NULL && p->adjvex!=vj) p=p->next;
if(p!=NULL && p->next!=NULL) return p->next->adjvex;
else return 0;
}
void DFS(ALGraph *G,int v) /* 從第v個頂點出發深度優先遍歷圖G */
{
int w;
printf("%c ",G->adjlist[v].vertex);
visited[v]=True; /* 訪問第v個頂點，並把訪問標志置True */
for(w=FirstAdjVertex(G,v);w;w=NextAdjVertex(G,v,w))
if (!visited[w]) DFS(G,w); /* 對v尚未訪問的鄰接頂點w遞歸調用DFS */
}

void DFStraverse(ALGraph *G)
/*深度優先遍歷以鄰接表表示的圖G，而以鄰接矩陣表示時，演算法完全相同*/
{ int i,v;
for(v=0;v<G->n;v++)
visited[v]=False;/*標志向量初始化*/
//for(i=0;i<G->n;i++)
if(!visited[0]) DFS(G,0);
}/*DFS*/

void main()
{
ALGraph G;
CreateALGraph(&G);
printf("該無向圖的深度優先搜索序列為：");
DFStraverse(&G);
printf("\nSuccess!\n");
}