看到這篇部落格相信一開始映入讀者眼簾的就是下面這幅圖了，這就是傳說中的七橋問題（哥尼斯堡橋問題）。在哥尼斯堡，普雷格爾河環繞着奈佛夫島（圖中的a島）。這條河将陸地分成了下面4個區域，該處還有着7座連接配接這些陸地的橋梁。
問題是如何從某地出發，依次沿着各個橋，必須經過每座橋且每座橋隻能經過1次，最終回到原地。
不知道這個問題且好奇的童鞋現在肯定在忙活着找出來這道題的結果了。
是偉大的數學家歐拉（leonhard euler）在1736年首次使用圖的方法解決了該問題。
歐拉将上面的模型轉換成了下面這種”圖“的形式。
歐拉把頂點的度定義為與該頂點相關聯的邊的條數，并且他證明了存在從任意點出發，經過所有邊恰好一次，并最終回到出發頂點的走法的充分必要條件是：每個頂點的度均為偶數。人們稱之為歐拉閉迹（eulerian walk）。
圖（graph）g=（v，e）由頂點（vertex）的集v和邊（edge）的集e組成。頂點代表了對象，在示意圖中我們使用點或圓來表示它；邊代表了兩個對象的連接配接關系，在示意圖中我們使用連接配接兩頂點的線段來表示。
有時也把邊稱作弧（arc），如果點對（v，w）是有序的，那麼圖就叫做有向的圖（有向圖）。如果點對(v,w)是無序的，那麼圖就叫做無向的圖（無向圖）。簡單的講，邊沒有指向性的圖叫做無向圖，邊具有指向性的圖叫做有向圖。
頂點v和w鄰接（adjacent）當且僅當（v，w）屬于e。
我們可以給邊賦予各式的屬性，比如權值（cost）。權值可以表示從一個頂點到另一個頂點的距離，也可以表示一個頂點到另一個頂點說話費的代價（比如時間、金錢等）。一個邊上帶權值的圖稱為網絡（network）。
如果無向圖中從每一個頂點到其他每個頂點都存在一條路徑，則稱該無向圖是連通的（connected）。具有這樣性質的有向圖稱為是強連通的的（strongly connected）。如果有向圖不是強連通的，但它的基礎圖（underlying graph）（也就是其弧上去掉方向說形成的圖）是連通的，那麼稱該有向圖是弱連通的（weakly connected）。完全圖（complete graph）是其每一對頂點間都存在一條邊的圖。
所謂入度（indegree）是指的頂點v的邊（u，v）的條數。
如下表示了一個有着7個頂點和12條邊的有向圖。
如果具有n個頂點，e條邊的圖g的頂點i的度為di，則g的邊數為：
e=∑n−10di2
現在将圖看作抽象資料類型，下面給出adt圖的結構：
functions
對于所有的 graph∈graph ，v，v1，v2∈vertices
graph create()
return一個空圖
graph insertvertex (graph, v)
向圖graph中插入沒有關聯邊的新頂點v，return改變後的圖
graph insertedge (graph, v1，v2)
在圖graph的頂點v1和v2之間插入一條邊，return改變後的圖
graph deletevertex (graph, v)
删除圖graph的頂點v及與其關聯的所有邊，return改變後的圖
graph deleteedge (graph，v1，v2)
删除圖graph的邊（v1,v2)，頂點v1,v2不删除，return改變後的圖
boolean isempty (graph)
if(graph==空圖） return true,else return false
list adjacent (graph, v)
return頂點v的所有鄰接結點
圖主要有3種常用的存儲表示方式：鄰接矩陣（adjacency matrices），鄰接表（adjacency lists），鄰接多重表（adjacency multilists）。
鄰接矩陣
鄰接矩陣使用|v|∗|v|的二維數組來表示圖。g[i][j]表示的是頂點i和頂點j的關系。
1）因為在無向圖中，我們隻需要知道頂點i和頂點j是否是相連的，是以我們隻需要将g[i][j]和g[j][j]設定為1或是0表示相連或不相連即可。如下圖所示。
2）而在有向圖中，我們隻需要知道是否有從頂點i到頂點j的邊，是以如果頂點i有一條指向頂點j的邊，那麼g[i][j]就設為1，否則設為0。有向圖與無向圖不同，并不需要滿足g[i][j]=g[j][i]。
3）在帶權值的圖中，g[i][j]表示的是頂點i到頂點j的邊的權值。由于在邊不存在的情況下，如果将g[i][j]設為0，就無法和權值為0的情況區分開來，是以選取适當的較大的常數inf（隻要能和普通的權值差別開來就可以了），然後令g[i][j]=inf就好了。當然，在無向圖中還是要保持g[i][j]=g[j][i]。在一條邊上有多種不帶權值的情況下，定義多個同樣的|v|∗|v|數組，或者是使用結構體或類作為數組的元素，就可以和原來一樣對圖進行處理了。
使用這種存儲方式，可以很友善地判斷任意兩個頂點之間是否有邊以及确定頂點的度，這也是這種表示法最大的優勢。任意一個頂點i的度等于其鄰接矩陣中頂點i所對應的行中的數字之和：
∑n−1j=0adjmat[i][j]
在這種表示法中掃描所有邊至少需要o(n2)時間，因為必須檢查矩陣中的n2−n個元素才能确定圖中邊的條數（鄰接矩陣對角線上的n個元素都是0，是以不用檢查。又因為無向圖的鄰接矩陣是對稱的，實際隻需檢查鄰接矩陣的一半元素）。通常把邊很少的圖成為稀疏圖（sparse graphs）。
鄰接表
如果用鄰接矩陣表示稀疏圖就會浪費大量記憶體空間，而用連結表，則是通過把頂點所能到的頂點的邊儲存在連結清單中來表示圖，這樣就隻需要o(|v|+|e|)的記憶體空間。
而所謂的鄰接表，就是用n個連結清單代替鄰接矩陣中的n行。連結清單中的結點結構至少要包含一個頂點域和一個鍊域。對于任意給定的連結清單i，連結清單中的結點就是與頂點i相鄰的所有頂點。鄰接表存儲聲明的c語言聲明如下：
鄰接多重表
在無向圖的鄰接表存儲表示中，每一條邊(vi，vj) 都表示為兩項：一項在頂點vi 的鄰接表中，而另一項在頂點 vj 的鄰接表中。在多重表中，各連結清單中的結點可以被幾個連結清單共享，此時圖中的每一條邊隻對應于一個結點，而這個結點出現在該邊所關聯的兩個頂點的每個鄰接連結清單中。如下圖所示：
鄰接多重表結點結構的c語言聲明為：
請先忽視下圖中所有的下标，讓我們從頭開始。随意選擇一個點，此處選擇v3，作為切入點。是以到v3的距離為0。從v3出發，距離為1的結點是v1和v6；繼續下一步，v6已經無路可走，而與v1距離為1的是v2和v4，是以對它們标記上2；繼續下去，v2和v4走一步都可以到v5，v4走一步可以到v7，是以v5和v7被标記為3。至此搜尋便結束了。
這就是廣度優先搜尋（breadth-first search），該方法按層處理頂點。距起始點最近的那些頂點首先被求值，最遠點則最後被求值，這很像對樹的層序周遊（level-order traversal）。
為了實作廣度優先搜尋，可以使用動态連結隊列。在隊列中的每個頂點都包含兩個域：頂點的序号和連結指針。
函數bfs所使用的隊列的定義和函數原型聲明為：
圖的廣度優先搜尋算法：
圖中每個頂點都被存入隊列一次，是以該算法中的while循環至多重複n次。如果采用鄰接表存儲表示，那麼該算法所需要的時間為：
d0+d1+…+dn−1=o(e)
其中di 為頂點 vi 的度。
而如果采用鄰接矩陣來實作，那麼對于每個頂點的通路，while循環的時間為o(n)，是以算法的總耗時為o(n2) 。和接下來的深度優先搜尋一樣，一次廣度優先搜尋通路到的頂點以及與這些頂點相關聯的邊形成的圖g的一個連通分支。
深度優先搜尋内容較多，已經在下文中單獨列出。
使用以上的兩種搜尋算法也可以用來判斷一個無向圖是否是連通的。具體步驟如下：
1.調用bfs(0)或dfs(0)
2.檢查是否存在未被通路過的頂點
具體代碼如下：
算法分析：如果采用鄰接表存儲，那麼函數dfs時間開銷為o(e)。這裡for循環的時間開銷為o(n)，是以整個算法的時間複雜性為o(n+e)。
雙聯通圖（biconnected graph）是沒有關節點的連通圖。對此有一個比較重要的公式如下：
回退邊也叫back edge，大家顧名思義就好，下面有更多應用。
下面來段求解圖的雙連通分支的算法：
拓撲排序（topological sort）是對有向無環圖的頂點的一種排序，它使得如果存在一條從vi到vj的路徑，那麼在排序中vj出現在vi的後面。正是由于這個特性，如果圖含有回路，那麼拓撲排序是不可能的。
拓撲排序簡單的說，就是将上圖變成下圖。
求拓撲排序算法的一種簡單方式：選中一個沒有入邊的頂點，顯示出該點，并将它和它的邊一起從圖中删除，然後對圖的其餘部分應用同樣的方法處理。
假設每一個頂點的入度被存儲且圖被讀入一個鄰接表中，下面的代碼則可以生成一個拓撲排序。
對上圖應用拓撲排序的結果如下：
單源最短路徑問題：給定一個權重圖g=（v，e）和一個特定頂點s作為輸入，找出從s到g中每一個其他點的最短權重路徑。
如下圖所示，從v1到v6的最短權重路徑的值為6（v1−v4−v7−v6），從v2到v5的最短權重路徑的值為5（v2−v4−v5）。
下面這個圖從v5到v4的最短權重路徑可就有意思了，它是1麼？不是。按照v5−v4−v2−v5−v4的路徑走則是一條更短的路徑了，因為這是帶負值回路的圖。而由于帶負值而引入的循環，這個循環叫做負值回路（negative-cost cycle），當它出現在圖中時，最短路徑問題就是不确定的了。有負值的邊未必不好，但它們明顯使問題更加難了。
當未指明所讨論的是權重路徑還是無權路徑時，如果圖是權重的，那麼路徑就是權重的。
下面列出單源最短路徑算法：
思考：找出a到所有其他頂點的最短路徑以及b到所有其他頂點的最短無權路徑。
如果要求所有頂點對之間的最短路徑，可以用下面這個算法：
我們由一個問題引入傳遞閉包的概念。有一個邊不帶權值的有向圖g，要判斷任意兩個頂點i 和j 之間是否存在一條路徑，此處有兩種情況，一種是路徑長度為正數，一種是路徑長度為非負。以上兩種情況分别被稱為圖的傳遞閉包（transitive closure），和自反傳遞閉包（reflexive transitive closure）。
傳遞閉包矩陣（transitive closure matrix）是一個矩陣，記作a+，如果從頂點i到j存在一條長度大于0的路徑，則a+[i][j]=1，否則a+[i][j]=0 。
自反傳遞閉包矩陣是一個矩陣，記作a∗ ，如果從頂點i到j存在一條長度大于0的路徑，則a∗[i][j]=1，否則a∗[i][j]=0 。
前面的廣度優先搜尋中的圖是無權圖，而如果一旦變成了權重圖，那麼問題就變得困難起來了。
對于每個頂點，我們标記為known以及unknown，和上面一樣，還得有一個距離的dv。與無權最短路徑一樣，dijkstra算法也是按階段進行，在每個階段選擇一個頂點v，它在所有unknown頂點中具有最小的dv，同時算法聲明從s到v的最短路徑是known的。然後緊接着，不斷的進行下去即可。
那麼這個算法到底是怎麼回事了？請看下圖。
圖中已經對權重做好了标記，以v1作為切入點，是以初始情況如下左圖。
v1此時已經是known的了，而其有2個鄰接點v2和v4，是以可以調整為如下右圖。正無窮圖示辨別沒有連通。pv表示前一個鄰接點。
毫無疑問這裡會接下來走到v4去，因為v4的權重為1比v2的權重為2要小。調整為如下左圖。
可能你已經看到了上圖中的右圖而好奇為什麼下一步是v2，但是v4根本不能走到v2。因為v4能夠走到的，比如v3，權重從v1開始一共是3，這比從v1到v2還要大。于是就跳轉回到了v2。
下一步便走到了v5，因為隻有值為3的權重，同樣的v3也是，于是它們倆被雙雙标記為known。如下左圖所示。
緊接着走到了v7，同時v6下調到了5+1=6得到了如下右圖。至于為什麼要做這個調整，是因為此時v1到v7的權重為1+4=5，而v7到v6的權重為1，是以就有了這個調整。
最後便順勢走到了v6完成了整個dijkstra算法，它們都已被标記為known。
在後面還将會有一種斐波那契堆，針對dijkstra算法做了優化，歡迎大家的繼續關注。
而如果一個圖具有負的邊值，那麼dijkstra算法就行不通了。這是因為一個頂點u被聲明為known後，那就可能從某個另外的unknown頂點v有一條回到u的負的路徑。而“回到”就意味着循環，前面的例子中我們已經知道了循環是多麼的……
問題并非沒有解決的辦法，如果我們有一個常數x，将其加到每一條邊的值上，這樣除去負的邊，再計算新圖的最短路徑，最後把結果應用到原圖上。然後這個解決方案也是布滿了荊棘，因為居多許多條邊的路徑變得比那些具有很少邊的路徑權重更重了。如果我們将s放到隊列中，然後再每一個階段讓一個頂點v出隊，找出所有與v鄰接的頂點w，使得dw>dv+cv,w，然後更新到dw和pw，并在w不在隊列中時将它放到隊列中，可以為每一個頂點設定一個位（bit）以訓示它在隊列中出現的情況。
如果圖是無環的，則可以通過改變聲明頂點為known的順序，或者叫做頂點選取法則來改進dijkstra算法。這種方法通過拓撲排序來選擇頂點，由于選擇和更新可以在拓撲排序執行的過程中執行，是以新的算法隻需要一趟就可以完成。
通過下面這個動作結點圖（activity-node graph）來解釋什麼是關鍵路徑分析（critical path analysis）再合适不過了。一條邊（v，w）表示動作v必須在動作w開始前完成，如前面說描述的那樣，這就意味着圖必須是無環的。
為了進行這些運算，我們把動作結點圖轉化成事件結點圖（event-node graph），每個事件對應于一個動作和所有與它相關的動作完成。
是以現在我們需要找出事件的最早完成時間，隻要找出從第一個事件到最後一關事件的最長路徑的長。因為有正值回路（positive-cost cycle）的存在最長路徑問題常常是沒有意義的。而由于事件結點圖是無環圖，那就不需要擔心回路的問題了，這樣一來就不用有所顧忌了。
以下是最早完成時間。
以下是最晚完成時間。
借助頂點的拓撲排序計算最早完成時間，而最晚完成時間則通過倒轉拓撲排序來計算。
而事件結點圖中每條邊的松弛時間（slack time）代表對應動作可以被延遲而不推遲整體完成的時間量，最早完成時間、最晚完成時間和松弛時間如下所示。
某些動作的松弛時間為0，這些動作是關鍵性的動作，它們必須按計劃結束。至少存在一條完成零-松弛邊組成的路徑，這樣的路徑是關鍵路徑（critical path）。
如下左圖所示，有一個頂點s，稱為源點（source）；還有一個頂點t，稱為彙點（sink）。對于頂點c，它最大流出2，是以它的最大流入為2，如下右圖所示。而t的最大流也就是5。
要想計算最大流，同樣可是使用前面的思想——分階段進行。令開始時所有邊都沒有流，如下中間圖所示。我們可以用殘餘圖（residual graph）來表示對于每條邊還能再添加上多少流。對于每一條邊，可以從容量中減去目前的流而計算出殘留的流。
第一步：假設我們選擇s−b−d−t路徑，此時會發出2個機關的流通過這條路徑的每一邊，如下中間圖所示。對比左圖，我們做如下約定：一旦注滿（使飽和）一條邊，例如a到b和b到d，就将這條邊從殘餘圖（也就是中間圖）去掉，如下右圖所示。
第二步：接下來選擇s−a−c−t路徑，此時也會發出2個機關的流通過這條路徑的每一邊，如下中間圖所示（隻看s−a−c−t即可，s−b−d−t為上一步說走過的路徑）。同樣将殘餘圖更新如下右圖所示。
第三步：從上圖的殘餘圖中我們已經可以看出來最後一步的唯一一種走法了，也就是從s−a−d−t。做如下圖所示更新。
很顯然從t無法走到s，是以算法至此便終止了。是以正好5個機關的流是最大值。前面的三步我們走的如此順利，那麼問題真的如此簡單麼？
如果一開始我們選擇了s−a−d−t，那麼算法就會失敗了，因為路已經被堵死了。
為了使算法得以成功運作，那麼就要讓流圖中具有以相反方向發送流的路徑，如下所示。那麼對于如下右圖中的殘餘圖而言，從d傳回到a的便成了3而非4，這是因為從t流到d的流量是3個機關。現在在殘餘圖中就有a和d之間有2個方向，或者還有1個機關的流可以從a導向d，或者是3個機關的流導向相反的反向，當然，我們也可以撤銷流。
緊接着如果通過d到a導入2個機關的流，算法就會從邊（a，d）取走2個機關的流，更新流圖如下。
思考：找出下面網絡中的一個拓撲排序以及最大流。
除了一些不能再簡單的工程外，所有的工程都可以劃分為若幹個成為活動（activities）的子工程。比如說大學的課程，得修完了大學英語1才能修大學英語2，也得修完了高等數學才能修線性代數、機率論、離散數學等。将這些作為頂點标記為圖時，它便是一個有向圖。
頂點表示活動的網（activity on vertex network）或aov網，是用頂點表示活動或任務，邊表示活動或任務之間的優先關系的有向圖g。在aov網絡g中，當且僅當從頂點i到j存在一條有向路徑，則頂點i稱為頂點j的前驅（predecessor）；當且僅當<i,j> 是g中的一條邊，則稱頂點i為頂點j的直接前驅（immediate predecessor）。如果頂點i是頂點j的前驅，則稱頂點j為頂點i的後繼（successor）；如果頂點i是頂點j的直接前驅，則稱頂點j為頂點i的直接後繼。
拓撲排列是由有向圖中所有頂點形成一個線性序列，對圖中任意兩個頂點i和j，如果頂點i是頂點j的前驅，則頂點i在拓撲序列中排在頂點j的前面。
我們在前面已經介紹了拓撲排序，這裡給出它的僞代碼。
對于拓撲排序問題，所需的操作主要有：
1）判斷頂點是否有前驅；
2）删除頂點和關聯于該頂點的所有邊。
在操作1中，我們可以在每個頂點中都儲存其直接前驅個數的計數。對于操作2，可以使用前面介紹過的鄰接表來表示aov網絡。于是可以将其實作為以下c代碼：
在topsort的聲明中，count域用來儲存頂點的入度，而link域則是指向鄰接表首結點的指針。鄰接表中的每個結點又包含了兩個域：vertex和link。在輸入時，可以友善地設定count域的值。當輸入一條邊<i,j> 時，頂點j的count就會加1。用一個棧來儲存count值為0的頂點序列。當然也可以使用隊列，但棧更容易實作。由于在count域減至0以後，count域就沒有用了，是以通過頭結點的count域把棧中的各個結點連結起來。
對于topsort的分析：對于具有n個頂點和e條邊的aov網絡，第一個for循環的時間開銷為o(n)。而第二個for循環執行n次。if子句在常數時間内完成；else子句中的for循環時間開銷為o(di)，其中di是頂點i的出度。由于這個循環會在每個頂點輸出時執行一次，是以總時間為：
o((∑n−1i=odi)+n)=o(e+n)
是以這個算法的漸進時間為o(e+n)，與問題的規模呈線性關系。
aoe網絡就是邊表示活動的網絡（activity on edge network），它的有向邊表示在一個工程中所需完成的任務或活動，而頂點表示事件，用來辨別某些活動的完成。在aov網絡中，事件高數2完成意味着要先完成高數1；aoe網絡中，事件高數2完成意味着已經完成了高數1。也就是說在aoe中，當一個事件發生時，就表明觸發該事件的所有活動都已經完成。
在aoe網絡中，有些活動可以并行地進行，是以完成整個工程所需的最短時間是從開始頂點到終止頂點的最長路徑的長度。關鍵路徑（critical path）就是一條具有最長路徑長度的路徑。
一個事件vi可以發生的最早發生時間（earliest time），是從開始頂點vo到頂點vi的最長路徑的長度。活動vi的最遲開始時間（latest time），記作late(i)，是指在不增加工程工期的前提下，活動ai能夠最遲的開始時間。
關鍵網絡（critical activity）是指滿足early(i)=late(i)的活動，一個活動的最遲開始時間late(i)與最早開始時間early(i)之間的差說明了該活動的關鍵程度。
下面列出兩個比較常用的公式：
1）事件最早發生時間的計算
earliest[j]=maxi∈p(j){earliest[i]+<i,j>的持續時間}
2）事件最晚發生時間的計算
latest[j]=mini∈s(j){latest[i]−<j,i>的持續時間}
一個無向圖g的最小生成樹（minimum spanning tree）就是由該圖的那些連接配接g的所有頂點的邊構成的總值最低的樹。最小生成樹存在當且僅當g是連通的。
下面第二個圖是第一個圖的最小生成樹（碰巧是唯一的，但并不能代表一般情況）。最小生成樹是一棵樹；因為它無環；因為最小生成樹包含每一個頂點，是以它叫生成樹；此外，它顯然是包含所有頂點的最小的樹。
計算最小生成樹的一種方法是使其連續地一步一步成長，在每一步中，都要把一個結點當作根并且往上累加邊，于是就将關聯的頂點加到了增長中的樹上。
prim算法和前面求最短路徑的dijkstra算法思想類似，是以和前面一樣我們對每一個頂點保留值dv和pv以及一個标記頂點的known或unknown。
還是老辦法，在prim算法中也設定一個表的初始狀态如下。
将v1設定為known的，根據prim算法上一張圖所示，v1連接配接了v2、v3、v4，其dv分别為2、4、1，是以更新如下。
将v4聲明為known，更新如下。
将v2和v3先後聲明為known，更新如下。
将v7聲明為known後更新如下左圖，最後将v6和v5也更新為known後更新如下右圖。
下面是prim算法的僞代碼實作，其中t為生成樹的邊集，tv是目前生成樹t的頂點集合
第二種貪心政策是連續地按照最小的權選擇邊，并且當所選的邊不産生回路時就把它作為取定的邊。同樣是前面的示例，用kruskal算法執行如下。
形式上，kruskal算法是在處理一個森林——樹的集合。下圖展示了邊被添加到森林中的順序。
當添加到森林中的邊足夠多時，算法終止，這裡算法的作用在于決定邊（u，v）是應該添加還是舍棄。
在該算法執行的過程中，兩個頂點屬于同一個集合當且僅當它們在目前的生成森林（spanning forest）中連通。如果u和v在同一個集合中，那麼連接配接它們的邊就要放棄，因為當它們已經連接配接的情況下，再添加邊（u，v）就會形成一個回路。
如果這兩個頂點不在同一個集合中，就應該将這條邊加入，并對包含頂點u和v的兩個集合執行一次union操作。這樣将保持集合的不變性，因為一旦邊（u，v）添加到生成森林中，若w連通到u而x連通到v，這x和w必然是連通的，是以屬于相同的集合。雖然将邊排序便于選取，但用線性時間建立一個堆則是更好的想法，此時deletemin使得邊依次得到測試。
sollin算法在每一步都為生成樹遞歸地選取若幹條邊，在每一步處理開始時，說選取的邊與圖中的所有n個頂點形成一個生成森林。在執行過程中，為森林中的每棵樹都選取一條邊，與選取的邊都是恰有一個頂點在樹上且代價最小。由于森林中的兩棵樹可能選取同一條邊，是以需要去掉同一條邊被多次選取的情況。在開始時，說選取的邊集為空，當最後結果隻有一棵樹或者再沒有邊可供選取時，算法就此結束。
深度優先搜尋（depth-first search）是對前序周遊的推廣，對每一個頂點，字段visited被初始化成false，通過哪些尚未被通路的結點遞歸調用該過程，我們保證不會陷入無限循環。如果圖是無向且連通的，或是有向但非強連通的，這種方法可能會通路不到某些結點。此時我們搜尋一個未被标記的結點，然後應用深度優先周遊，并繼續這個過程直到不存在未标記的結點為止。因為該方法保證每一條邊隻被通路一次，是以隻要使用鄰接表，執行周遊的總時間就是o(|e|+|v|)。
深度優先搜尋的算法實作：
和上文中的廣搜一樣，我們也來對dfs進行分析。
如果采用鄰接表來存儲，就可以沿着頂點的連結清單來确定其所有鄰接頂點。是以在鄰接表中的每一個頂點都至多掃描一次，是以完成搜尋時間複雜性為o(e)。
如果采用鄰接矩陣來存儲，通路頂點的所有鄰接頂點的時間為o(n)，而整個過程至多通路n個頂點，是以完成搜尋時間複雜性為o(n2) 。
如下左圖中是一個無向圖，我們以此為例，假設從a開始，标記a為known并遞歸地調用dfs(b)。dfs(b)标記b為known并遞歸調用dfs(c)。dfs(c)标記c為known并遞歸調用dsf(d)。而後d的鄰接結點隻有c，但c已經是knwon的，這裡便無法再繼續遞歸下去，是以傳回到dfs(c)。dfs(c)看到已經标記為known的b鄰接點和d鄰接點，是以調用dfs(e)。dfs(e)标記e為known，同樣的它隻能傳回到dfs(c)，再傳回到dfs(b)，最後傳回到dfs(a)。實際上這裡接觸每條邊2次，一次是作為邊（v，w），另一次是作為邊（w，v）。
如下右圖展示了深度優先搜尋樹（depth-first spanning tree）的步驟。虛線表示向後邊（back edge），表示這條“邊”并不是樹的一部分。
樹将模拟我們執行的周遊，使用樹的邊對該樹的前序編号（preorder numbering）表示頂點被标記的順序；如果圖不是連通的，那麼處理所有的結點（以及邊）自然需要多次反複調用dfs，每次都生成一棵樹，整個集合就是深度優先生成森林（depth-first spanning forest）。
前面我們已經介紹過了雙連通圖，如果删除一個無向圖的仁一頂點後，剩下的圖仍然連通，那麼這樣的無向連通圖就稱為是雙連通的（biconnected）。
如果圖不是雙聯通的，那麼将其删除後不再連通的那些頂點叫做割點（articulation point）。
深度優先搜尋提供了一種找出連通圖中所有割點的線性時間算法。從圖中任一頂點開始，執行深度優先搜尋并在頂點被通路時給它們編号。對于每一個頂點v，我們稱其前序編号為num(v)。然後，對于深度優先搜尋生成樹中的每一個頂點v，計算編号最低的頂點，我們稱之為low(v)，該點可從v開始通過樹的零條或多條邊，且可能還有一條後向邊而以該序達到。
如前所述，如果圖不是強連通的，那麼從某個結點開始的深度優先搜尋可能通路不了所有的結點，這種情況下我們從某個未做标記的結點處開始，反複執行深度優先搜尋，直到所有的結點都被通路到為止。
對此我們從頂點b開始深度優先搜尋，依次通路b、c、a、d、e、f。而後從某個未被标記的頂點重新開始，比如h，然後通路j和i。最後從g開始，也從此結束。
深度優先生成森林中的虛線是一些（v，w）邊，其中的w在考察時已經做了标記。在無向圖中，它們總是一些向後邊，但是可以看到，存在三種類型的邊并不通向新的頂點。這裡有一些向後邊（back edge），如（a，b）；還有一些向前邊（forward edge），如（c，d）；最後還有一些交叉邊（cross edge），如（f，c），它們把不直接相關的兩個樹結點連接配接起來。深度優先搜尋森林一般通過把一些子結點和一些新的樹叢左到右添加到森林中形成。
深度優先搜尋還可以用來檢測一個有向圖是否是無環圖，因為一個有向圖是無環圖當且僅當它沒有向後邊。上面的例子明顯不是無環圖，因為它有向後邊。而拓撲排序也可以用來檢測一個圖是否是無環圖，進行拓撲排序的另一種方法是通過深度優先搜尋生成森林的後序周遊給頂點指定拓撲編号n，n−1，……，1。隻要圖是無環的，這種排序就是一緻的。
備注1：為保證權威性，所有定義、公式、圖檔均來自《資料結構（c語言版）》、《資料結構與算法分析 c++描述》、《離散數學》、《算法導論》、《挑戰程式設計競賽》等書籍和必應、維基百科等網絡。
備注2：希望不會因為參考了在備注1中提到的諸多書籍與網絡而被批判，畢竟這篇部落格也融合了我許多時間、精力和思考。我隻是希望像我所讀的所有外國書籍一般在書尾列出參考文獻一樣尊重原作者。
備注3：個人能力有限，暫時無力為圖論這一領域增加新算法，本文中所有算法均來自偉大的前輩們的著作，為表敬意，此處以金色顯示。
感謝您的通路，希望對您有所幫助。
歡迎大家關注或收藏、評論或點贊。
為使本文得到斧正和提問，轉載請注明出處：
http://blog.csdn.net/nomasp