圖的定義

背景知識

看到這篇博客相信一開始映入讀者眼簾的就是下面這幅圖了，這就是傳說中的七橋問題（哥尼斯堡橋問題）。在哥尼斯堡，普雷格爾河環(huán)繞著奈佛夫島（圖中的A島）。這條河將陸地分成了下面4個區(qū)域，該處還有著7座連接這些陸地的橋梁。

問題是如何從某地出發(fā)，依次沿著各個橋，必須經(jīng)過每座橋且每座橋只能經(jīng)過1次，最終回到原地。

不知道這個問題且好奇的童鞋現(xiàn)在肯定在忙活著找出來這道題的結果了。

是偉大的數(shù)學家歐拉（Leonhard Euler）在1736年首次使用圖的方法解決了該問題。

歐拉將上面的模型轉(zhuǎn)換成了下面這種”圖“的形式。

歐拉把頂點的度定義為與該頂點相關聯(lián)的邊的條數(shù)，并且他證明了存在從任意點出發(fā)，經(jīng)過所有邊恰好一次，并最終回到出發(fā)頂點的走法的充分必要條件是：每個頂點的度均為偶數(shù)。人們稱之為歐拉閉跡（Eulerian walk）。

簡要定義

圖（graph）G=（V，E）由頂點（vertex）的集V和邊（Edge）的集E組成。頂點代表了對象，在示意圖中我們使用點或圓來表示它；邊代表了兩個對象的連接關系，在示意圖中我們使用連接兩頂點的線段來表示。

有時也把邊稱作?。╝rc），如果點對（v，w）是有序的，那么圖就叫做有向的圖（有向圖）。如果點對(v,w)是無序的，那么圖就叫做無向的圖（無向圖）。簡單的講，邊沒有指向性的圖叫做無向圖，邊具有指向性的圖叫做有向圖。

頂點v和w鄰接（adjacent）當且僅當（v，w）屬于E。

我們可以給邊賦予各式的屬性，比如權值（cost）。權值可以表示從一個頂點到另一個頂點的距離，也可以表示一個頂點到另一個頂點說話費的代價（比如時間、金錢等）。一個邊上帶權值的圖稱為網(wǎng)絡（network）。

如果無向圖中從每一個頂點到其他每個頂點都存在一條路徑，則稱該無向圖是連通的（connected）。具有這樣性質(zhì)的有向圖稱為是強連通的的（strongly connected）。如果有向圖不是強連通的，但它的基礎圖（underlying graph）（也就是其弧上去掉方向說形成的圖）是連通的，那么稱該有向圖是弱連通的（weakly connected）。完全圖（complete graph）是其每一對頂點間都存在一條邊的圖。

所謂入度（indegree）是指的頂點v的邊（u，v）的條數(shù)。

如下表示了一個有著7個頂點和12條邊的有向圖。

如果具有n個頂點，e條邊的圖G的頂點i的度為di，則G的邊數(shù)為：

e=∑n?10di2

以上這個數(shù)學公式的markdown“源碼”：
$ e =frac { sum_{0}^{n-1} d_i} {2} $

現(xiàn)在將圖看作抽象數(shù)據(jù)類型，下面給出ADT圖的結構：

functions	對于所有的graph∈Graph，v，v1，v2∈Vertices
Graph Create()	return一個空圖
Graph InsertVertex (graph, v)	向圖graph中插入沒有關聯(lián)邊的新頂點v，return改變后的圖
Graph InsertEdge (graph,v1，v2)	在圖graph的頂點v1和v2之間插入一條邊，return改變后的圖
Graph DeleteVertex (graph, v)	刪除圖graph的頂點v及與其關聯(lián)的所有邊，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|的二維數(shù)組來表示圖。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的情況區(qū)分開來，因此選取適當?shù)妮^大的常數(shù)INF（只要能和普通的權值區(qū)別開來就可以了），然后令g[i][j]=INF就好了。當然，在無向圖中還是要保持g[i][j]=g[j][i]。在一條邊上有多種不帶權值的情況下，定義多個同樣的|V|?|V|數(shù)組，或者是使用結構體或類作為數(shù)組的元素，就可以和原來一樣對圖進行處理了。

使用這種存儲方式，可以很方便地判斷任意兩個頂點之間是否有邊以及確定頂點的度，這也是這種表示法最大的優(yōu)勢。任意一個頂點i的度等于其鄰接矩陣中頂點i所對應的行中的數(shù)字之和：

∑n?1j=0adjmat[i][j]

以上這個數(shù)學公式的markdown“源碼”：

$ sum_{j=0}^{n-1} g[i][j] $

在這種表示法中掃描所有邊至少需要O(n2)時間，因為必須檢查矩陣中的n2?n個元素才能確定圖中邊的條數(shù)（鄰接矩陣對角線上的n個元素都是0，因此不用檢查。又因為無向圖的鄰接矩陣是對稱的，實際只需檢查鄰接矩陣的一半元素）。通常把邊很少的圖成為稀疏圖（sparse graphs）。

鄰接表

如果用鄰接矩陣表示稀疏圖就會浪費大量內(nèi)存空間，而用鏈接表，則是通過把頂點所能到的頂點的邊保存在鏈表中來表示圖，這樣就只需要O(|V|+|E|)的內(nèi)存空間。

而所謂的鄰接表，就是用n個鏈表代替鄰接矩陣中的n行。鏈表中的結點結構至少要包含一個頂點域和一個鏈域。對于任意給定的鏈表i，鏈表中的結點就是與頂點i相鄰的所有頂點。鄰接表存儲聲明的C語言聲明如下：

#define MAX_VERTICES 50

typedef struct node *node-pointer;

typedef struct node

{

int vertex;

struct node *link;

};

node_pointer graph[MAX_VERTICES];

int n=0;

鄰接多重表

在無向圖的鄰接表存儲表示中，每一條邊(vi，vj)都表示為兩項：一項在頂點vi的鄰接表中，而另一項在頂點vj的鄰接表中。在多重表中，各鏈表中的結點可以被幾個鏈表共享，此時圖中的每一條邊只對應于一個結點，而這個結點出現(xiàn)在該邊所關聯(lián)的兩個頂點的每個鄰接鏈表中。如下圖所示：

鄰接多重表結點結構的C語言聲明為：

typedef struct edge *edge-pointer

typedef struct edge

{

short int marked;

int vertex1;

int vertex2;

edge_pointer path1;

edge_pointer path2;

};

圖的基本操作和算法

廣度優(yōu)先搜索

請先忽視下圖中所有的下標，讓我們從頭開始。隨意選擇一個點，此處選擇v3，作為切入點。因此到v3的距離為0。從v3出發(fā)，距離為1的結點是v1和v6；繼續(xù)下一步，v6已經(jīng)無路可走，而與v1距離為1的是v2和v4，因此對它們標記上2；繼續(xù)下去，v2和v4走一步都可以到v5，v4走一步可以到v7，因此v5和v7被標記為3。至此搜索便結束了。

這就是廣度優(yōu)先搜索（breadth-first search），該方法按層處理頂點。距起始點最近的那些頂點首先被求值，最遠點則最后被求值，這很像對樹的層序遍歷（level-order traversal）。

為了實現(xiàn)廣度優(yōu)先搜索，可以使用動態(tài)鏈接隊列。在隊列中的每個頂點都包含兩個域：頂點的序號和鏈接指針。

函數(shù)bfs所使用的隊列的定義和函數(shù)原型聲明為：

typedef struct queue *queue_pointer;

typedef struct queue

{

int vertex;

queue_pointer link;

};

void addq(queue_pointer *, queue_pointer *,int);

int deleteq(queue_pointer *);

圖的廣度優(yōu)先搜索算法：

void bfs(int v)

{

node_pointer w;

queue_pointer front,rear;

front=rear=NULL;

printf("%5d",v);

visited[v]=TRUE;

addq(&front,&rear,v);

while(front)

{

v=deleteq(&front);

for(w=graph[v];w;w=w->link)

{

if(!visited[w->vertex])

{

printf("%5d",w->vertex);

addq(&front,&rear,w->vertex);

visited[w->vertex]=TRUE;

}

}

}

}

圖中每個頂點都被存入隊列一次，所以該算法中的while循環(huán)至多重復n次。如果采用鄰接表存儲表示，那么該算法所需要的時間為：

d0+d1+…+dn?1=O(e)

其中di為頂點vi的度。

而如果采用鄰接矩陣來實現(xiàn)，那么對于每個頂點的訪問，while循環(huán)的時間為O(n)，所以算法的總耗時為O(n2)。和接下來的深度優(yōu)先搜索一樣，一次廣度優(yōu)先搜索訪問到的頂點以及與這些頂點相關聯(lián)的邊形成的圖G的一個連通分支。

深度優(yōu)先搜索

深度優(yōu)先搜索內(nèi)容較多，已經(jīng)在下文中單獨列出。

連通圖

使用以上的兩種搜索算法也可以用來判斷一個無向圖是否是連通的。具體步驟如下：

1.調(diào)用bfs(0)或dfs(0)

2.檢查是否存在未被訪問過的頂點

具體代碼如下：

void connected(void)

{

int i;

for(i=0;i

{

if(!visited[i])

{

dfs(i);

printf(" ");

}

}

}

算法分析：如果采用鄰接表存儲，那么函數(shù)dfs時間開銷為O(e)。這里for循環(huán)的時間開銷為O(n)，所以整個算法的時間復雜性為O(n+e)。

雙連通圖

雙聯(lián)通圖（biconnected graph）是沒有關節(jié)點的連通圖。對此有一個比較重要的公式如下：

low(u) = min{dfn(u), min{low(w)|w是u的兒子}, min{dfn(w)|(u,w)是一條回退邊} }

回退邊也叫back edge，大家顧名思義就好，下面有更多應用。

下面來段求解圖的雙連通分支的算法：

void bicon(int u, int v)

{

node_pointer ptr;

int w,x,y;

dfn[u]=low[u]=num++;

for(ptr=graph[u];ptr;ptr=ptr->link)

{

w=ptr->vertex;

if(v!=w && dfn[w]

add(&top,u,w);

if(dfn[w]<0)

{

bicon(w,u);

low[u]=MIN2(low[u],low[w]);

if(low[w]>=dfn[u])

{

printf("New biconnected component: ");

do

{

delete(&top,&x,&y);

printf(" <%d,%d>",x,y);

}while(!((x==u)&&(y==w)));

printf(" ");

}

}

else if(w!=v)

low[u]=MIN2(low[u],dfn[w]);

}

}

拓撲排序

拓撲排序（topological sort）是對有向無環(huán)圖的頂點的一種排序，它使得如果存在一條從vi到vj的路徑，那么在排序中vj出現(xiàn)在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的路徑走則是一條更短的路徑了，因為這是帶負值回路的圖。而由于帶負值而引入的循環(huán)，這個循環(huán)叫做負值回路（negative-cost cycle），當它出現(xiàn)在圖中時，最短路徑問題就是不確定的了。有負值的邊未必不好，但它們明顯使問題更加難了。

當未指明所討論的是加權路徑還是無權路徑時，如果圖是加權的，那么路徑就是加權的。

下面列出單源最短路徑算法：

void shortestpath(int v,int cost[][MAX_VERTICES],int distance[],int n,short int found[])

{

int i,u,w;

for(i=0;i

{

found[i]=FALSE;

distance[i]=cost[v][i];

}

found[v]=TRUE;

distance[v]=0;

for(i=0;i

{

u=choose(distance,n,found);

found[u]=TRUE;

for(w=0;w

if(!found[w])

if(distance[u]+cost[u][w]

distance[w]=cost[u][w]+distance[u];

}

}

int choose(int distance[],int n,short int found[])

{

int i,min,minpos;

min=INT_MAX;

minpos=-1;

for(i=0;i

if(distance[i]

{

min=distance[i];

minpos=i;

}

return minpos;

}

思考：找出A到所有其他頂點的最短路徑以及B到所有其他頂點的最短無權路徑。

如果要求所有頂點對之間的最短路徑，可以用下面這個算法：

void allcosts(int cost[][MAX_VERTICES],int distance[][MAX_VERTICES],int n)

{

int i,j,k;

for(i=0;i

for(j=0;j

distance[i][j]=cost[i][j];

for(k=0;k

for(i=0;i

for(j=0;j

if(distance[i][k]+distance[k][j]

distance[i][j]=distance[i][k]+distance[k][j];

}

傳遞閉包

我們由一個問題引入傳遞閉包的概念。有一個邊不帶權值的有向圖G，要判斷任意兩個頂點i 和j 之間是否存在一條路徑，此處有兩種情況，一種是路徑長度為正數(shù)，一種是路徑長度為非負。以上兩種情況分別被稱為圖的傳遞閉包（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。

Dijkstra算法

前面的廣度優(yōu)先搜索中的圖是無權圖，而如果一旦變成了加權圖，那么問題就變得困難起來了。

對于每個頂點，我們標記為known以及unknown，和上面一樣，還得有一個距離的dv。與無權最短路徑一樣，Dijkstra算法也是按階段進行，在每個階段選擇一個頂點v，它在所有unknown頂點中具有最小的dv，同時算法聲明從s到v的最短路徑是known的。然后緊接著，不斷的進行下去即可。

那么這個算法到底是怎么回事了？請看下圖。

圖中已經(jīng)對權重做好了標記，以v1作為切入點，因此初始情況如下左圖。

v1此時已經(jīng)是known的了，而其有2個鄰接點v2和v4，因此可以調(diào)整為如下右圖。正無窮圖標標識沒有連通。pv表示前一個鄰接點。

毫無疑問這里會接下來走到v4去，因為v4的權重為1比v2的權重為2要小。調(diào)整為如下左圖。

可能你已經(jīng)看到了上圖中的右圖而好奇為什么下一步是v2，但是v4根本不能走到v2。因為v4能夠走到的，比如v3，權重從v1開始一共是3，這比從v1到v2還要大。于是就跳轉(zhuǎn)回到了v2。

下一步便走到了v5，因為只有值為3的權重，同樣的v3也是，于是它們倆被雙雙標記為known。如下左圖所示。

緊接著走到了v7，同時v6下調(diào)到了5+1=6得到了如下右圖。至于為什么要做這個調(diào)整，是因為此時v1到v7的加權為1+4=5，而v7到v6的加權為1，所以就有了這個調(diào)整。

最后便順勢走到了v6完成了整個Dijkstra算法，它們都已被標記為known。

在后面還將會有一種斐波那契堆，針對Dijkstra算法做了優(yōu)化，歡迎大家的繼續(xù)關注。

具有負邊值得圖

而如果一個圖具有負的邊值，那么Dijkstra算法就行不通了。這是因為一個頂點u被聲明為known后，那就可能從某個另外的unknown頂點v有一條回到u的負的路徑。而“回到”就意味著循環(huán)，前面的例子中我們已經(jīng)知道了循環(huán)是多么的……

問題并非沒有解決的辦法，如果我們有一個常數(shù)X，將其加到每一條邊的值上，這樣除去負的邊，再計算新圖的最短路徑，最后把結果應用到原圖上。然后這個解決方案也是布滿了荊棘，因為居多許多條邊的路徑變得比那些具有很少邊的路徑權重更重了。如果我們將s放到隊列中，然后再每一個階段讓一個頂點v出隊，找出所有與v鄰接的頂點w，使得dw>dv+cv,w，然后更新到dw和pw，并在w不在隊列中時將它放到隊列中，可以為每一個頂點設置一個位（bit）以指示它在隊列中出現(xiàn)的情況。

無環(huán)圖

如果圖是無環(huán)的，則可以通過改變聲明頂點為known的順序，或者叫做頂點選取法則來改進Dijkstra算法。這種方法通過拓撲排序來選擇頂點，由于選擇和更新可以在拓撲排序執(zhí)行的過程中執(zhí)行，因此新的算法只需要一趟就可以完成。

通過下面這個動作結點圖（activity-node graph）來解釋什么是關鍵路徑分析（critical path analysis）再合適不過了。一條邊（v，w）表示動作v必須在動作w開始前完成，如前面說描述的那樣，這就意味著圖必須是無環(huán)的。

為了進行這些運算，我們把動作結點圖轉(zhuǎn)化成事件結點圖（event-node graph），每個事件對應于一個動作和所有與它相關的動作完成。

所以現(xiàn)在我們需要找出事件的最早完成時間，只要找出從第一個事件到最后一關事件的最長路徑的長。因為有正值回路（positive-cost cycle）的存在最長路徑問題常常是沒有意義的。而由于事件結點圖是無環(huán)圖，那就不需要擔心回路的問題了，這樣一來就不用有所顧忌了。

以下是最早完成時間。

以下是最晚完成時間。

借助頂點的拓撲排序計算最早完成時間，而最晚完成時間則通過倒轉(zhuǎn)拓撲排序來計算。

而事件結點圖中每條邊的松弛時間（slack time）代表對應動作可以被延遲而不推遲整體完成的時間量，最早完成時間、最晚完成時間和松弛時間如下所示。

某些動作的松弛時間為0，這些動作是關鍵性的動作，它們必須按計劃結束。至少存在一條完成零-松弛邊組成的路徑，這樣的路徑是關鍵路徑（critical path）。

網(wǎng)絡流問題

如下左圖所示，有一個頂點s，稱為源點（source）；還有一個頂點t，稱為匯點（sink）。對于頂點c，它最大流出2，因此它的最大流入為2，如下右圖所示。而t的最大流也就是5。

要想計算最大流，同樣可是使用前面的思想——分階段進行。令開始時所有邊都沒有流，如下中間圖所示。我們可以用殘余圖（residual graph）來表示對于每條邊還能再添加上多少流。對于每一條邊，可以從容量中減去當前的流而計算出殘留的流。

第一步：假設我們選擇s?b?d?t路徑，此時會發(fā)出2個單位的流通過這條路徑的每一邊，如下中間圖所示。對比左圖，我們做如下約定：一旦注滿（使飽和）一條邊，例如a到b和b到d，就將這條邊從殘余圖（也就是中間圖）去掉，如下右圖所示。

第二步：接下來選擇s?a?c?t路徑，此時也會發(fā)出2個單位的流通過這條路徑的每一邊，如下中間圖所示（只看s?a?c?t即可，s?b?d?t為上一步說走過的路徑）。同樣將殘余圖更新如下右圖所示。

第三步：從上圖的殘余圖中我們已經(jīng)可以看出來最后一步的唯一一種走法了，也就是從s?a?d?t。做如下圖所示更新。

很顯然從t無法走到s，因此算法至此便終止了。因此正好5個單位的流是最大值。前面的三步我們走的如此順利，那么問題真的如此簡單么？

如果一開始我們選擇了s?a?d?t，那么算法就會失敗了，因為路已經(jīng)被堵死了。

為了使算法得以成功運作，那么就要讓流圖中具有以相反方向發(fā)送流的路徑，如下所示。那么對于如下右圖中的殘余圖而言，從d返回到a的便成了3而非4，這是因為從t流到d的流量是3個單位?，F(xiàn)在在殘余圖中就有a和d之間有2個方向，或者還有1個單位的流可以從a導向d，或者是3個單位的流導向相反的反向，當然，我們也可以撤銷流。

緊接著如果通過d到a導入2個單位的流，算法就會從邊（a，d）取走2個單位的流，更新流圖如下。

思考：找出下面網(wǎng)絡中的一個拓撲排序以及最大流。

活動網(wǎng)絡

AOV網(wǎng)絡

除了一些不能再簡單的工程外，所有的工程都可以劃分為若干個成為活動（activities）的子工程。比如說大學的課程，得修完了大學英語1才能修大學英語2，也得修完了高等數(shù)學才能修線性代數(shù)、概率論、離散數(shù)學等。將這些作為頂點標記為圖時，它便是一個有向圖。

頂點表示活動的網(wǎng)（activity on vertex network）或AOV網(wǎng)，是用頂點表示活動或任務，邊表示活動或任務之間的優(yōu)先關系的有向圖G。在AOV網(wǎng)絡G中，當且僅當從頂點i到j存在一條有向路徑，則頂點i稱為頂點j的前驅(qū)（predecessor）；當且僅當是G中的一條邊，則稱頂點i為頂點j的直接前驅(qū)（immediate predecessor）。如果頂點i是頂點j的前驅(qū)，則稱頂點j為頂點i的后繼（successor）；如果頂點i是頂點j的直接前驅(qū)，則稱頂點j為頂點i的直接后繼。

拓撲排列是由有向圖中所有頂點形成一個線性序列，對圖中任意兩個頂點i和j，如果頂點i是頂點j的前驅(qū)，則頂點i在拓撲序列中排在頂點j的前面。

我們在前面已經(jīng)介紹了拓撲排序，這里給出它的偽代碼。

for(i=0;i

{

if every vertex has a predecessor

{

fprintf(stderr,"Network has a cycle. ");

exit(1);

}

pick a vertex v that has no predecessors;

output v;

delete v and all edges leading out of v from the netwok;

}

對于拓撲排序問題，所需的操作主要有：

1）判斷頂點是否有前驅(qū)；
2）刪除頂點和關聯(lián)于該頂點的所有邊。

在操作1中，我們可以在每個頂點中都保存其直接前驅(qū)個數(shù)的計數(shù)。對于操作2，可以使用前面介紹過的鄰接表來表示AOV網(wǎng)絡。于是可以將其實現(xiàn)為以下C代碼：

// 聲明

typedef struct node *node_pointer;

typedef struct node

{

int vertex;

node_pointer link;

};

typedef struct

{

int count;

node_pointer link;

}hdnodes;

hdnodes graph[MAX_VERTICES];

// 函數(shù)

void topsort(hdnodes graph[],int n)

{

int i,j,k,top;

node_pointer ptr;

top=-1;

for(i=0;i

{

if(!graph[i].count)

{

graph[i].count=top;

top=i;

}

}

for(i=0;i

{

if(top==-1)

{

fprintf(stderr," Network has a cycle. Sort terminated. ");

exit(1);

}

else

{

j=top;

top=graph[top].count;

printf("v%d, ",j);

for(ptr=graph[j].link;ptr;ptr=ptr->link)

{

k=ptr->vertex;

graph[k].count--;

if(!graph[k].count)

{

graph[k].count=top;

top=k;

}

}

}

}

}

在topsort的聲明中，count域用來保存頂點的入度，而link域則是指向鄰接表首結點的指針。鄰接表中的每個結點又包含了兩個域：vertex和link。在輸入時，可以方便地設置count域的值。當輸入一條邊時，頂點j的count就會加1。用一個棧來保存count值為0的頂點序列。當然也可以使用隊列，但棧更容易實現(xiàn)。由于在count域減至0以后，count域就沒有用了，所以通過頭結點的count域把棧中的各個結點鏈接起來。

對于topsort的分析：對于具有n個頂點和e條邊的AOV網(wǎng)絡，第一個for循環(huán)的時間開銷為O(n)。而第二個for循環(huán)執(zhí)行n次。if子句在常數(shù)時間內(nèi)完成；else子句中的for循環(huán)時間開銷為O(di)，其中di是頂點i的出度。由于這個循環(huán)會在每個頂點輸出時執(zhí)行一次，所以總時間為：

O((∑n?1i=odi)+n)=O(e+n)

因此這個算法的漸進時間為O(e+n)，與問題的規(guī)模呈線性關系。

AOE網(wǎng)絡

AOE網(wǎng)絡就是邊表示活動的網(wǎng)絡（activity on edge network），它的有向邊表示在一個工程中所需完成的任務或活動，而頂點表示事件，用來標識某些活動的完成。在AOV網(wǎng)絡中，事件高數(shù)2完成意味著要先完成高數(shù)1；AOE網(wǎng)絡中，事件高數(shù)2完成意味著已經(jīng)完成了高數(shù)1。也就是說在AOE中，當一個事件發(fā)生時，就表明觸發(fā)該事件的所有活動都已經(jīng)完成。

在AOE網(wǎng)絡中，有些活動可以并行地進行，所以完成整個工程所需的最短時間是從開始頂點到終止頂點的最長路徑的長度。關鍵路徑（critical path）就是一條具有最長路徑長度的路徑。

一個事件vi可以發(fā)生的最早發(fā)生時間（earliest time），是從開始頂點vo到頂點vi的最長路徑的長度?；顒觱i的最遲開始時間（latest time），記作late(i)，是指在不增加工程工期的前提下，活動ai能夠最遲的開始時間。

關鍵網(wǎng)絡（critical activity）是指滿足early(i)=late(i)的活動，一個活動的最遲開始時間late(i)與最早開始時間early(i)之間的差說明了該活動的關鍵程度。

下面列出兩個比較常用的公式：

1）事件最早發(fā)生時間的計算

earliest[j]=maxi∈P(j){earliest[i]+的持續(xù)時間}

以上這個數(shù)學公式的markdown“源碼”：

$ earliest[j] = displaystyle max_{x in {P(j)}} { earliest[i] + 的持續(xù)時間 } $

2）事件最晚發(fā)生時間的計算

latest[j]=mini∈S(j){latest[i]?的持續(xù)時間}

最小生成樹

一個無向圖G的最小生成樹（minimum spanning tree）就是由該圖的那些連接G的所有頂點的邊構成的總值最低的樹。最小生成樹存在當且僅當G是連通的。

下面第二個圖是第一個圖的最小生成樹（碰巧是唯一的，但并不能代表一般情況）。最小生成樹是一棵樹；因為它無環(huán)；因為最小生成樹包含每一個頂點，所以它叫生成樹；此外，它顯然是包含所有頂點的最小的樹。

Prim算法

計算最小生成樹的一種方法是使其連續(xù)地一步一步成長，在每一步中，都要把一個結點當作根并且往上累加邊，于是就將關聯(lián)的頂點加到了增長中的樹上。

Prim算法和前面求最短路徑的Dijkstra算法思想類似，因此和前面一樣我們對每一個頂點保留值dv和pv以及一個標記頂點的known或unknown。

還是老辦法，在Prim算法中也設定一個表的初始狀態(tài)如下。

將v1設置為known的，根據(jù)Prim算法上一張圖所示，v1連接了v2、v3、v4，其dv分別為2、4、1，因此更新如下。

將v4聲明為known，更新如下。

將v2和v3先后聲明為known，更新如下。

將v7聲明為known后更新如下左圖，最后將v6和v5也更新為known后更新如下右圖。

下面是Prim算法的偽代碼實現(xiàn)，其中T為生成樹的邊集，TV是當前生成樹T的頂點集合

Kruskal算法

第二種貪心策略是連續(xù)地按照最小的權選擇邊，并且當所選的邊不產(chǎn)生回路時就把它作為取定的邊。同樣是前面的示例，用Kruskal算法執(zhí)行如下。

形式上，Kruskal算法是在處理一個森林——樹的集合。下圖展示了邊被添加到森林中的順序。

當添加到森林中的邊足夠多時，算法終止，這里算法的作用在于決定邊（u，v）是應該添加還是舍棄。

在該算法執(zhí)行的過程中，兩個頂點屬于同一個集合當且僅當它們在當前的生成森林（spanning forest）中連通。如果u和v在同一個集合中，那么連接它們的邊就要放棄，因為當它們已經(jīng)連接的情況下，再添加邊（u，v）就會形成一個回路。

如果這兩個頂點不在同一個集合中，就應該將這條邊加入，并對包含頂點u和v的兩個集合執(zhí)行一次union操作。這樣將保持集合的不變性，因為一旦邊（u，v）添加到生成森林中，若w連通到u而x連通到v，這x和w必然是連通的，因此屬于相同的集合。雖然將邊排序便于選取，但用線性時間建立一個堆則是更好的想法，此時deleteMin使得邊依次得到測試。

Sollin算法

Sollin算法在每一步都為生成樹遞歸地選取若干條邊，在每一步處理開始時，說選取的邊與圖中的所有n個頂點形成一個生成森林。在執(zhí)行過程中，為森林中的每棵樹都選取一條邊，與選取的邊都是恰有一個頂點在樹上且代價最小。由于森林中的兩棵樹可能選取同一條邊，所以需要去掉同一條邊被多次選取的情況。在開始時，說選取的邊集為空，當最后結果只有一棵樹或者再沒有邊可供選取時，算法就此結束。

深度優(yōu)先搜索

深度優(yōu)先搜索（depth-first search）是對前序遍歷的推廣，對每一個頂點，字段visited被初始化成false，通過哪些尚未被訪問的結點遞歸調(diào)用該過程，我們保證不會陷入無限循環(huán)。如果圖是無向且連通的，或是有向但非強連通的，這種方法可能會訪問不到某些結點。此時我們搜索一個未被標記的結點，然后應用深度優(yōu)先遍歷，并繼續(xù)這個過程直到不存在未標記的結點為止。因為該方法保證每一條邊只被訪問一次，所以只要使用鄰接表，執(zhí)行遍歷的總時間就是O(|E|+|V|)。

深度優(yōu)先搜索的算法實現(xiàn)：

#define FALSE 0

#define TRUE 1

short int visited[MAX_VERTICES]

void dfs(int v)

{

node_pointer w;

visited[v]=TRUE;

printf("%5d",v);

for(w=graph[v];w;w=w->link);

if(!visited[w->vertex])

dfs(w->vertex);

}

和上文中的廣搜一樣，我們也來對dfs進行分析。

如果采用鄰接表來存儲，就可以沿著頂點的鏈表來確定其所有鄰接頂點。因此在鄰接表中的每一個頂點都至多掃描一次，所以完成搜索時間復雜性為O(e)。

如果采用鄰接矩陣來存儲，訪問頂點的所有鄰接頂點的時間為O(n)，而整個過程至多訪問n個頂點，因此完成搜索時間復雜性為O(n2)。

無向圖

如下左圖中是一個無向圖，我們以此為例，假設從A開始，標記A為known并遞歸地調(diào)用dfs(B)。dfs(B)標記B為known并遞歸調(diào)用dfs(C)。dfs(C)標記C為known并遞歸調(diào)用dsf(D)。而后D的鄰接結點只有C，但C已經(jīng)是knwon的，這里便無法再繼續(xù)遞歸下去，因此返回到dfs(C)。dfs(C)看到已經(jīng)標記為known的B鄰接點和D鄰接點，因此調(diào)用dfs(E)。dfs(E)標記E為known，同樣的它只能返回到dfs(C)，再返回到dfs(B)，最后返回到dfs(A)。實際上這里接觸每條邊2次，一次是作為邊（v，w），另一次是作為邊（w，v）。

如下右圖展示了深度優(yōu)先搜索樹（depth-first spanning tree）的步驟。虛線表示向后邊（back edge），表示這條“邊”并不是樹的一部分。

樹將模擬我們執(zhí)行的遍歷，使用樹的邊對該樹的前序編號（preorder numbering）表示頂點被標記的順序；如果圖不是連通的，那么處理所有的結點（以及邊）自然需要多次反復調(diào)用dfs，每次都生成一棵樹，整個集合就是深度優(yōu)先生成森林（depth-first spanning forest）。

雙連通性

前面我們已經(jīng)介紹過了雙連通圖，如果刪除一個無向圖的仁一頂點后，剩下的圖仍然連通，那么這樣的無向連通圖就稱為是雙連通的（biconnected）。

如果圖不是雙聯(lián)通的，那么將其刪除后不再連通的那些頂點叫做割點（articulation point）。

深度優(yōu)先搜索提供了一種找出連通圖中所有割點的線性時間算法。從圖中任一頂點開始，執(zhí)行深度優(yōu)先搜索并在頂點被訪問時給它們編號。對于每一個頂點v，我們稱其前序編號為Num(V)。然后，對于深度優(yōu)先搜索生成樹中的每一個頂點v，計算編號最低的頂點，我們稱之為Low(V)，該點可從v開始通過樹的零條或多條邊，且可能還有一條后向邊而以該序達到。

有向圖

如前所述，如果圖不是強連通的，那么從某個結點開始的深度優(yōu)先搜索可能訪問不了所有的結點，這種情況下我們從某個未做標記的結點處開始，反復執(zhí)行深度優(yōu)先搜索，直到所有的結點都被訪問到為止。

對此我們從頂點B開始深度優(yōu)先搜索，依次訪問B、C、A、D、E、F。而后從某個未被標記的頂點重新開始，比如H，然后訪問J和I。最后從G開始，也從此結束。

深度優(yōu)先生成森林中的虛線是一些（v，w）邊，其中的w在考察時已經(jīng)做了標記。在無向圖中，它們總是一些向后邊，但是可以看到，存在三種類型的邊并不通向新的頂點。這里有一些向后邊（back edge），如（A，B）；還有一些向前邊（forward edge），如（C，D）；最后還有一些交叉邊（cross edge），如（F，C），它們把不直接相關的兩個樹結點連接起來。深度優(yōu)先搜索森林一般通過把一些子結點和一些新的樹叢左到右添加到森林中形成。

深度優(yōu)先搜索還可以用來檢測一個有向圖是否是無環(huán)圖，因為一個有向圖是無環(huán)圖當且僅當它沒有向后邊。上面的例子明顯不是無環(huán)圖，因為它有向后邊。而拓撲排序也可以用來檢測一個圖是否是無環(huán)圖，進行拓撲排序的另一種方法是通過深度優(yōu)先搜索生成森林的后序遍歷給頂點指定拓撲編號N，N?1，……，1。只要圖是無環(huán)的，這種排序就是一致的。