圖論算法有圖有代碼

拓?fù)渑判颍╰opological sort）是對(duì)有向無(wú)環(huán)圖的頂點(diǎn)的一種排序，它使得如果存在一條從vi到vj的路徑，那么在排序中vj出現(xiàn)在vi的后面。正是由于這個(gè)特性，如果圖含有回路，那么拓?fù)渑判蚴遣豢赡艿摹?/p>

拓?fù)渑判蚝?jiǎn)單的說(shuō)，就是將上圖變成下圖。

求拓?fù)渑判蛩惴ǖ囊环N簡(jiǎn)單方式：選中一個(gè)沒(méi)有入邊的頂點(diǎn)，顯示出該點(diǎn)，并將它和它的邊一起從圖中刪除，然后對(duì)圖的其余部分應(yīng)用同樣的方法處理。

假設(shè)每一個(gè)頂點(diǎn)的入度被存儲(chǔ)且圖被讀入一個(gè)鄰接表中，下面的代碼則可以生成一個(gè)拓?fù)渑判颉?/p>

對(duì)上圖應(yīng)用拓?fù)渑判虻慕Y(jié)果如下：

最短路徑算法

單源最短路徑問(wèn)題：給定一個(gè)加權(quán)圖G=（V，E）和一個(gè)特定頂點(diǎn)s作為輸入，找出從s到G中每一個(gè)其他點(diǎn)的最短加權(quán)路徑。

如下圖所示，從v1到v6的最短加權(quán)路徑的值為6（v1?v4?v7?v6）

從v2到v5的最短加權(quán)路徑的值為5（v2?v4?v5）。

下面這個(gè)圖從v5到v4的最短加權(quán)路徑可就有意思了，它是1么？不是。按照v5?v4?v2?v5?v4的路徑走則是一條更短的路徑了，因?yàn)檫@是帶負(fù)值回路的圖。而由于帶負(fù)值而引入的循環(huán)，這個(gè)循環(huán)叫做負(fù)值回路（negative-cost cycle），當(dāng)它出現(xiàn)在圖中時(shí)，最短路徑問(wèn)題就是不確定的了。有負(fù)值的邊未必不好，但它們明顯使問(wèn)題更加難了。

當(dāng)未指明所討論的是加權(quán)路徑還是無(wú)權(quán)路徑時(shí)，如果圖是加權(quán)的，那么路徑就是加權(quá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到所有其他頂點(diǎn)的最短路徑以及B到所有其他頂點(diǎn)的最短無(wú)權(quán)路徑。

如果要求所有頂點(diǎn)對(duì)之間的最短路徑，可以用下面這個(gè)算法：

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è)問(wèn)題引入傳遞閉包的概念。有一個(gè)邊不帶權(quán)值的有向圖G，要判斷任意兩個(gè)頂點(diǎn)i 和j 之間是否存在一條路徑，此處有兩種情況，一種是路徑長(zhǎng)度為正數(shù)，一種是路徑長(zhǎng)度為非負(fù)。以上兩種情況分別被稱為圖的傳遞閉包（transitive closure），和自反傳遞閉包（reflexive transitive closure）。

傳遞閉包矩陣（transitive closure matrix）是一個(gè)矩陣，記作A+，如果從頂點(diǎn)i到j(luò)存在一條長(zhǎng)度大于0的路徑，則A+[i][j]=1，否則A+[i][j]=0。

自反傳遞閉包矩陣是一個(gè)矩陣，記作A?，如果從頂點(diǎn)i到j(luò)存在一條長(zhǎng)度大于0的路徑，則A?[i][j]=1，否則A?[i][j]=0。

Dijkstra算法

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

對(duì)于每個(gè)頂點(diǎn)，我們標(biāo)記為known以及unknown，和上面一樣，還得有一個(gè)距離的dv。與無(wú)權(quán)最短路徑一樣，Dijkstra算法也是按階段進(jìn)行，在每個(gè)階段選擇一個(gè)頂點(diǎn)v，它在所有unknown頂點(diǎn)中具有最小的dv，同時(shí)算法聲明從s到v的最短路徑是known的。然后緊接著，不斷的進(jìn)行下去即可。

那么這個(gè)算法到底是怎么回事了？請(qǐng)看下圖。

圖中已經(jīng)對(duì)權(quán)重做好了標(biāo)記，以v1作為切入點(diǎn)，因此初始情況如下左圖。

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

毫無(wú)疑問(wèn)這里會(huì)接下來(lái)走到v4去，因?yàn)関4的權(quán)重為1比v2的權(quán)重為2要小。調(diào)整為如下左圖。

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

下一步便走到了v5，因?yàn)橹挥兄禐?的權(quán)重，同樣的v3也是，于是它們倆被雙雙標(biāo)記為known。如下左圖所示。

緊接著走到了v7，同時(shí)v6下調(diào)到了5+1=6得到了如下右圖。至于為什么要做這個(gè)調(diào)整，是因?yàn)榇藭r(shí)v1到v7的加權(quán)為1+4=5，而v7到v6的加權(quán)為1，所以就有了這個(gè)調(diào)整。

最后便順勢(shì)走到了v6完成了整個(gè)Dijkstra算法，它們都已被標(biāo)記為known。

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

具有負(fù)邊值得圖

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

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

無(wú)環(huán)圖

如果圖是無(wú)環(huán)的，則可以通過(guò)改變聲明頂點(diǎn)為known的順序，或者叫做頂點(diǎn)選取法則來(lái)改進(jìn)Dijkstra算法。這種方法通過(guò)拓?fù)渑判騺?lái)選擇頂點(diǎn)，由于選擇和更新可以在拓?fù)渑判驁?zhí)行的過(guò)程中執(zhí)行，因此新的算法只需要一趟就可以完成。

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

為了進(jìn)行這些運(yùn)算，我們把動(dòng)作結(jié)點(diǎn)圖轉(zhuǎn)化成事件結(jié)點(diǎn)圖（event-node graph），每個(gè)事件對(duì)應(yīng)于一個(gè)動(dòng)作和所有與它相關(guān)的動(dòng)作完成。

所以現(xiàn)在我們需要找出事件的最早完成時(shí)間，只要找出從第一個(gè)事件到最后一關(guān)事件的最長(zhǎng)路徑的長(zhǎng)。因?yàn)橛姓祷芈罚╬ositive-cost cycle）的存在最長(zhǎng)路徑問(wèn)題常常是沒(méi)有意義的。而由于事件結(jié)點(diǎn)圖是無(wú)環(huán)圖，那就不需要擔(dān)心回路的問(wèn)題了，這樣一來(lái)就不用有所顧忌了。

以下是最早完成時(shí)間。

以下是最晚完成時(shí)間。

借助頂點(diǎn)的拓?fù)渑判蛴?jì)算最早完成時(shí)間，而最晚完成時(shí)間則通過(guò)倒轉(zhuǎn)拓?fù)渑判騺?lái)計(jì)算。

而事件結(jié)點(diǎn)圖中每條邊的松弛時(shí)間（slack time）代表對(duì)應(yīng)動(dòng)作可以被延遲而不推遲整體完成的時(shí)間量，最早完成時(shí)間、最晚完成時(shí)間和松弛時(shí)間如下所示。

某些動(dòng)作的松弛時(shí)間為0，這些動(dòng)作是關(guān)鍵性的動(dòng)作，它們必須按計(jì)劃結(jié)束。至少存在一條完成零-松弛邊組成的路徑，這樣的路徑是關(guān)鍵路徑（critical path）。

網(wǎng)絡(luò)流問(wèn)題

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

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

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

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

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

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

如果一開始我們選擇了s?a?d?t，那么算法就會(huì)失敗了，因?yàn)槁芬呀?jīng)被堵死了。

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

緊接著如果通過(guò)d到a導(dǎo)入2個(gè)單位的流，算法就會(huì)從邊（a，d）取走2個(gè)單位的流，更新流圖如下。

思考：找出下面網(wǎng)絡(luò)中的一個(gè)拓?fù)渑判蛞约白畲罅鳌?/p>

活動(dòng)網(wǎng)絡(luò)

AOV網(wǎng)絡(luò)

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

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

拓?fù)渑帕惺怯捎邢驁D中所有頂點(diǎn)形成一個(gè)線性序列，對(duì)圖中任意兩個(gè)頂點(diǎn)i和j，如果頂點(diǎn)i是頂點(diǎn)j的前驅(qū)，則頂點(diǎn)i在拓?fù)湫蛄兄信旁陧旤c(diǎn)j的前面。

我們?cè)谇懊嬉呀?jīng)介紹了拓?fù)渑判颍@里給出它的偽代碼。

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;

}

對(duì)于拓?fù)渑判騿?wèn)題，所需的操作主要有：

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

在操作1中，我們可以在每個(gè)頂點(diǎn)中都保存其直接前驅(qū)個(gè)數(shù)的計(jì)數(shù)。對(duì)于操作2，可以使用前面介紹過(guò)的鄰接表來(lái)表示AOV網(wǎng)絡(luò)。于是可以將其實(shí)現(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域用來(lái)保存頂點(diǎn)的入度，而link域則是指向鄰接表首結(jié)點(diǎn)的指針。鄰接表中的每個(gè)結(jié)點(diǎn)又包含了兩個(gè)域：vertex和link。在輸入時(shí)，可以方便地設(shè)置count域的值。當(dāng)輸入一條邊時(shí)，頂點(diǎn)j的count就會(huì)加1。用一個(gè)棧來(lái)保存count值為0的頂點(diǎn)序列。當(dāng)然也可以使用隊(duì)列，但棧更容易實(shí)現(xiàn)。由于在count域減至0以后，count域就沒(méi)有用了，所以通過(guò)頭結(jié)點(diǎn)的count域把棧中的各個(gè)結(jié)點(diǎn)鏈接起來(lái)。

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

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

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

AOE網(wǎng)絡(luò)

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

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

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

關(guān)鍵網(wǎng)絡(luò)（critical activity）是指滿足early(i)=late(i)的活動(dòng)，一個(gè)活動(dòng)的最遲開始時(shí)間late(i)與最早開始時(shí)間early(i)之間的差說(shuō)明了該活動(dòng)的關(guān)鍵程度。

下面列出兩個(gè)比較常用的公式：

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

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

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

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