圖的遍歷演算法背誦口訣

⑴ 先序遍歷和後序遍歷是什麼

1、先序遍歷也叫做先根遍歷、前序遍歷，可記做根左右（二叉樹父結點向下先左後右）。

首先訪問根結點然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹，如果二叉樹為空則返回。

例如，下圖所示二叉樹的遍歷結果是：ABDECF

（1）後序遍歷左子樹

（2）後序遍歷右子樹

（3）訪問根結點

如右圖所示二叉樹

後序遍歷結果：DEBFCA

已知前序遍歷和中序遍歷，就能確定後序遍歷。

(1)圖的遍歷演算法背誦口訣擴展閱讀：

圖的遍歷演算法主要有兩種，

一種是按照深度優先的順序展開遍歷的演算法，也就是深度優先遍歷；

另一種是按照寬度優先的順序展開遍歷的演算法，也就是寬度優先遍歷。寬度優先遍歷是沿著圖的深度遍歷圖的所有節點，每次遍歷都會沿著當前節點的鄰接點遍歷，直到所有點全部遍歷完成。

如果當前節點的所有鄰接點都遍歷過了，則回溯到上一個節點，重復這一過程一直到已訪問從源節點可達的所有節點為止。

如果還存在沒有被訪問的節點，則選擇其中一個節點作為源節點並重復以上過程，直到所有節點都被訪問為止。

利用圖的深度優先搜索可以獲得很多額外的信息，也可以解決很多圖論的問題。寬度優先遍歷又名廣度優先遍歷。通過沿著圖的寬度遍歷圖的節點，如果所有節點均被訪問，演算法隨即終止。寬度優先遍歷的實現一般需要一個隊列來輔助完成。

寬度優先遍歷和深度優先遍歷一樣也是一種盲目的遍歷方法。也就是說，寬度遍歷演算法並不使用經驗法則演算法， 並不考慮結果的可能地址，只是徹底地遍歷整張圖，直到找到結果為止。圖的遍歷問題分為四類：

1、遍歷完所有的邊而不能有重復，即所謂「歐拉路徑問題」（又名一筆畫問題）；

2、遍歷完所有的頂點而沒有重復，即所謂「哈密頓路徑問題」。

3、遍歷完所有的邊而可以有重復，即所謂「中國郵遞員問題」；

4、遍歷完所有的頂點而可以重復，即所謂「旅行推銷員問題」。

對於第一和第三類問題已經得到了完滿的解決，而第二和第四類問題則只得到了部分解決。第一類問題就是研究所謂的歐拉圖的性質，而第二類問題則是研究所謂的哈密頓圖的性質。

⑵ 求高手給個遍歷演算法

圖的遍歷

從圖中某一頂點出發訪遍圖中其餘頂點，且使每一頂點僅被訪問一次。這一過程叫做圖的遍歷。
遍歷圖的基本方法有兩種：深度優先搜索和廣度優先搜索。這兩種方法都適用於有向圖和無向圖。
和樹的遍歷類似，圖的遍歷也是從某個頂點出發，沿著，某條邊搜索路徑對圖中所有頂點各作一次訪問。若給定的圖是連通圖，則從圖中任意頂點出發順著邊可以訪問到該圖中所有的頂點，然而，圖的遍歷比樹的遍歷復雜得多，這是因為圖中的任一點都可能和其餘頂點相鄰接，故在訪問了某個頂點之後，可能順著某條迴路又到了該頂點。為了避免重復訪問同一個頂點，必須記住每個頂點是否被訪問過。為此，可設置一個布爾向量visited[1..n],它的初值為false，一旦訪問了頂點vi，便將visited[i]置為ture。

一、連通圖的深度優先搜索
連通圖深度優先搜索的基本思想如下：假定圖中某個頂點v1為出發點，首先訪問出發點v1，然後任選一個v1的訪問過的鄰接點v2，以v2為新的出發點繼續進行深度優先搜索，直至圖中所有頂點被訪問過。
顯然，圖的深度優先搜索是一個遞歸過程，類似於樹的前序遍歷，它的特點是盡可能先對縱深方向進行搜索，故稱之深度優先搜索。
現以圖5-10中G為例說明深度優搜索過程。假定v1是出發點，首先訪問v1。因v1有兩個鄰接點v2、v3均未被訪問，選擇v2作為新的出發點。訪問v2之後，再找v2的未訪問過的鄰接點。同v2鄰接的有v1、v4、v5，其中v1以被訪問過，而v4、v5未被訪問。選擇v4作為新的出發點。重復上述搜索過程繼續依次訪問v8、v5。訪問v5之後，由於與v5相鄰的頂點均以被訪問，搜索退回到v8。由於v8、v4、v2都沒有未被訪問的鄰接點，所以搜索過程連續地從v8退回到v4，再退回到v2最後退回到v1這時選擇v1的未被訪問過的鄰接點v3，繼續往下搜索，依次訪問v3、v6、v7，從而遍歷了圖中全部頂點。在這個過程中得到的頂點的訪問序列：

(a)無向圖G

(b)G的深度優先搜索過程
圖5-10a 深度優先搜索過程示例

v1→v2→v4→v8→v5→v3→v6→v7
這樣的序列就稱之為圖的深度優先搜索遍歷序列。
連通圖的深度優先搜索的非形式演算法如下:
procere dfs (g:graph;v1:integer);
//從v1出發深度優先遍歷圖g//
begin write(v1);
visited[v1]:=ture;
找出g中v1的第一鄰接點w;
while w存在do
[ if w 未被訪問 then dfs(g,w);
w:=g中v1的下一鄰接點]
end;
上述非行式演算法未涉及圖的存儲結構.圖的遍歷過程必然地包含對圖中每個頂點查找其鄰接點這一操作;而在圖的不同存儲結構上查找鄰接點的方法是不同的.
若以鄰接表為存儲結構,查找鄰接點操作實際上是順序查找鏈表.鄰接表上的深度優先演算法如下:
procere dfs(g:adj_list;v1:integer);
//從v1出發深度優先遍歷圖g.g以鄰接表為存儲結構//
begin write(v1);
visited[v1]:=ture;//標志v1已訪問//
p=g[v1].link;//找v1的第一個鄰接點//
while p<>nil do
[ if not (visited[p↑.adjvex]);//書錯寫成vertex//
then dfs(g,p↑.adjvex);
p:=p↑.next]//回溯----找v1的下一個鄰接點//
end;

二、連通圖的廣度優先搜索
連通圖廣度優先搜索的基本思想是：從圖中某個頂點v1出發，訪問了v1之後依次訪問v1的所有鄰接點；然後分別從這些鄰接點出發按深度優先搜索遍歷圖的其它頂點，直至所有頂點都被訪問到。它類似於樹的按層次遍歷，其特點是盡可能優先對橫向搜索，故稱之為廣度優先搜索。
下面以圖5-10中G為例說明廣度優先搜索的過程。首先從起點v1出發，訪問v1。v1有兩個未曾訪問的鄰接點v2和v3。先訪問v2，再訪問v3。然後再先後訪問v2的未曾訪問過的鄰接點v4、v5及v3的未曾訪問過的鄰接點v6、v7。最後訪問v4的未曾訪問過的鄰接點v8。至此圖中所有頂點均以被訪問到。得到的頂點訪問序列為：

(a)無向圖G

(b)G的廣度優先搜索過程
圖5-10b 廣度優先搜索過程示例

v1→v2→v3→v4→v5→v6→v7→v8
相應的，這樣的序列就稱之為圖的廣度優先搜索遍歷序列。
在廣度優先搜索中，若對x的訪問先於y，則對x鄰接點的訪問也先於隊y的鄰接點的訪問。因此，可採用隊列來暫存那些剛訪問過，但可能還有為訪問過的鄰接點的頂點。
連通圖的廣度優先搜索演算法如下：
procere bfs(g:adj_list;v1:integer);//書錯寫成adjlist//
//以鄰接表為存儲結構的廣度優先搜索。Q為隊列，假定visited的各分量已只置 為false//
begin init_linkedque(Q);//設計一個空隊Q//
visited[v1]:=ture;write(v1);
in_limkedque(Q,v1); //v1入隊//
while not empty(Q) do
[ v:=out_linkedque(Q);
p:=adj_list[v].link;//書錯寫成adjlist//
while p<>nil do
[ if visited[p↑.adjvex]:=false;//書錯寫成vertex//
then
[visited[p↑.adjvex]:=ture;
with(p↑.adjvex);
in_linkedque(Q,p↑.adjvex);]
p:=p↑.next]]
end;

三、圖的連通分量計算
如果要遍歷一個非連通圖，則需要多次調用dfs或bfs，每一次都要得到一個連通分量；調用dfs或bfs的次數就是連通分量的個數。因此很容易寫出非連通圖的遍歷演算法和計算一個圖的連通分量得演算法。下面給出的是以鄰接表為存儲結構，通過調用深度優先搜索演算法實現的計算連通分量的演算法。
procee conn_component (var g:graph;
var visited:array[1..vnum);
begin for v:=1 to vnum do
visited[v]:flase;
count:=0;
for v:=1 to vnum do
if not(visited[v])then
[count:=count+1;
write('component',count,':');
dfs(g,v);writeln;]
end;
對於圖5-5中非連通圖G3，用上述演算法可求出3個連通分量，各連通分量所含頂點如下：
component1: 1 2 3
component2: 4 5 6 7
component3: 8 9
注意，若從上述演算法中刪去有關連通分量計數器的操作，就得到一個非連通圖德遍歷演算法。

詳細資料和圖片請參看參考資料，那裡的比較詳細

⑶ 數據結構中出圖的二種遍歷，寫出演算法與思想，謝謝

BFS，廣度優先搜索
先遍歷離起點近的，再到遠的，直至全圖。先遍歷所有與起點距離為1的點，再到所有距離為2的點……
具體實現，需要一個隊列進行輔助存儲。
舉個例，S為起點，S到A,B,C3個點相鄰。A又與A1,A2相鄰，B與B1,B2相鄰，C沒有與其他點相鄰。對於遍歷A發生的事情，就是「發現」了A1,A2。但是，這是不能立即遍歷A1,A2，這與BFS宗旨違背，必須先遍歷B,C。而又由於B,C肯定是比A1,A2先「發現」，這就體現了一種「先進先出」的性質，因而需要隊列對為擴展的結點進行暫存
BFS()
{
queue q;
q.push(s);//一開始的s點
while(q非空)
{
從q中取一元素
將該元素「發現」，而又未被進過q的結點入隊
}
}

DFS，深度優先搜索
先選定一條路徑，對路徑上的點進行遍歷。然後，從路徑的盡頭開始，逐步回退，在每個分支再遍歷其他路徑及其上面的點。
具體實現，常寫作遞歸，故可理解為通過棧輔助存儲。
還是上面的距離，DFS出來的其中一種序列是S,A,A1,A2,B,B1,B2,C。路徑S,A,A1為第一選取的路徑，然後回退，逐步選取其他分支，在A選取了A2作為第二路徑，以此類推。由於這樣對每個點所做的操作就是「發現」，「遍歷」與「回退」，操作種類相同，故常寫作遞歸。。。
DFS(int target)
{
for(target的每個發現點)
{
DFS(該發現點)
}
//結束函數實際上就是回退的過程
}

⑷ 圖的圖的遍歷

常見的圖遍歷方式有兩種：深度優先遍歷和廣度優先遍歷，這兩種遍歷方式對有向圖和無向圖均適用。 深度優先遍歷的思想類似於樹的先序遍歷。其遍歷過程可以描述為：從圖中某個頂點v出發，訪問該頂點，然後依次從v的未被訪問的鄰接點出發繼續深度優先遍歷圖中的其餘頂點，直至圖中所有與v有路徑相通的頂點都被訪問完為止。
深度優先遍歷演算法實現：
為了便於在演算法中區分頂點是否已被訪問過，需要創建一個一維數組visited[0..n-1]（n是圖中頂點的數目），用來設置訪問標志，其初始值visited（0≤i≤n-1）為"0"，表示鄰接表中下標值為i的頂點沒有被訪問過，一旦該頂點被訪問，將visited置成"1"。
int visited[0..n-1]={0,0,...0};
void DFS(AdjList adj,int v)
{//v是遍歷起始點的在鄰接表中的下標值，其下標從0開始
visited[v]=1; visited(adj[v].elem);
for (w=adj[v].firstedge;w;w=w->next)
if (!visited[w->adjvex]) DFS(adj,w->adjvex);
}
對於無向圖，這個演算法可以遍歷到v頂點所在的連通分量中的所有頂點，而與v頂點不在一個連通分量中的所有頂點遍歷不到；而對於有向圖可以遍歷到起始頂點v能夠到達的所有頂點。若希望遍歷到圖中的所有頂點，就需要在上述深度優先遍歷演算法的基礎上，增加對每個頂點訪問狀態的檢測： intvisited[0..n-1]={0,0,...0};voidDFSTraverse(AdjListadj){for(v=0;v<n;v++)if(!visited[v])DFS(adj,v);} 對圖的廣度優先遍歷方法描述為：從圖中某個頂點v出發，在訪問該頂點v之後，依次訪問v的所有未被訪問過的鄰接點，然後再訪問每個鄰接點的鄰接點，且訪問順序應保持先被訪問的頂點其鄰接點也優先被訪問，直到圖中的所有頂點都被訪問為止。下面是對一個無向圖進行廣度優先遍歷的過程。
下面我們討論一下實現廣度優先遍歷演算法需要考慮的幾個問題：
（1）在廣度優先遍歷中，要求先被訪問的頂點其鄰接點也被優先訪問，因此，必須對每個頂點的訪問順序進行記錄，以便後面按此順序訪問各頂點的鄰接點。應利用一個隊列結構記錄頂點訪問順序，就可以利用隊列結構的操作特點，將訪問的每個頂點入隊，然後，再依次出隊，並訪問它們的鄰接點；
（2）在廣度優先遍歷過程中同深度優先遍歷一樣，為了避免重復訪問某個頂點，也需要創建一個一維數組visited[0..n-1]（n是圖中頂點的數目），用來記錄每個頂點是否已經被訪問過。
int visited[0..n-1]={0,0,...0};
void BFS(AdjList adj,int v)
{//v是遍歷起始點在鄰接表中的下標，鄰接表中下標從0開始
InitQueue(Q); //Q是隊列
visited[v]=1; visite(adj[v].elem); EnQueue(Q,v);
while (!QueueEmpty(Q)) {
DeQueue(Q,v);
for (w=adj[v].firstedge;w;w=w->next)
if (!visited[w->adjvex]) {
visited[w->adjvex]=1;
visite(adj[w->adjvex].elem);
EnQueue(Q,w->adjvex); }
}
}

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

圖的遍歷是指從圖中任一給定頂點出發，依次訪問圖中的其餘頂點。如果給定的圖是連通圖，則從圖中的任意一點出發，按照一個指定的順序就可以訪問到圖中的所有頂點，且每個頂點只訪問一次。這個過程稱為圖的遍歷。
圖的遍歷比樹的遍歷復雜的多。樹是一種特殊類型的圖，即無圈（無迴路）連通圖。樹中的任意兩個頂點間都有唯一的路徑相通。在一個頂點被訪問過之後，不可能又沿著另外一條路徑訪問到已被訪問過的結點。而圖中的頂點可能有邊與其他任意頂點相連
。因此在訪問了某個頂點之後，可能沿著另一條邊訪問已被訪問過的頂點。例如圖（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())