目錄

一、最小生成樹(shù)

二、最短路徑

三、有向?環(huán)圖描述表達(dá)式

四、拓?fù)渑判?/p>

五、關(guān)鍵路徑

---

一、最小生成樹(shù)

1、最小生成樹(shù)的概念

對(duì)于一個(gè)帶權(quán)連通無(wú)向圖G = （V,E)，生成樹(shù)不，每棵樹(shù)的權(quán)(即樹(shù)中所有邊上的權(quán)值之和)也可能不同。設(shè)R為G的所有生成樹(shù)的集合，若T為R中邊的權(quán)值之和最小的生成樹(shù)，則T稱為G的最小生成樹(shù)(Minimum-Spannino-Tree,MST).。

• 最小生成樹(shù)可能有多個(gè)，但邊的權(quán)值之和總是唯一且最小的。
• 最小生成樹(shù)的邊數(shù) =頂點(diǎn)數(shù) -1?？车粢粭l則不連通，增加一條邊則會(huì)出現(xiàn)回路。
• 如果一個(gè)連通圖本身就是一棵樹(shù)，則其最小生成樹(shù)就是它本身。
• 只有連通圖才有生成樹(shù)，非連通圖只有生成森林。

2、求最小生成樹(shù)的兩種方法

• Prim算法
• Kruskal算法?

Prim算法(普里姆)：從某一個(gè)頂點(diǎn)開(kāi)始構(gòu)建生成樹(shù);每次將代價(jià)最小的新頂點(diǎn)納入生成樹(shù)，直到所有頂點(diǎn)都納入為止。時(shí)間復(fù)雜度: O(V2)適合用于邊稠密圖

Kruskal算法(克魯斯卡爾)：每次選擇一條權(quán)值最小的邊，使這條邊的兩頭連通(原本已經(jīng)連通的就不選)直到所有結(jié)點(diǎn)都連通。時(shí)間復(fù)雜度: O(lEllog2lEl )適合用于邊稀疏圖

二、最短路徑

1.無(wú)權(quán)圖的單源最短路徑問(wèn)題——BFS算法

使用 BFS算法求無(wú)權(quán)圖的最短路徑問(wèn)題，需要使用三個(gè)數(shù)組

• d[]數(shù)組用于記錄頂點(diǎn) u 到其他頂點(diǎn)的最短路徑。
• path[]數(shù)組用于記錄最短路徑從那個(gè)頂點(diǎn)過(guò)來(lái)。
• visited[]數(shù)組用于記錄是否被訪問(wèn)過(guò)。

代碼時(shí)間

#define MAX_LENGTH 2147483647			//地圖中最大距離，表示正無(wú)窮// 求頂點(diǎn)u到其他頂點(diǎn)的最短路徑
void BFS_MIN_Disrance(Graph G,int u){for(i=0; i<G.vexnum; i++){visited[i]=FALSE;				//初始化訪問(wèn)標(biāo)記數(shù)組d[i]=MAX_LENGTH;				//初始化路徑長(zhǎng)度path[i]=-1;						//初始化最短路徑記錄}InitQueue(Q);						//初始化輔助隊(duì)列d[u]=0;visites[u]=TREE;EnQueue(Q,u);while(!isEmpty[Q]){					//BFS算法主過(guò)程DeQueue(Q,u);					//隊(duì)頭元素出隊(duì)并賦給ufor(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)){if(!visited[w]){d[w]=d[u]+1;path[w]=u;visited[w]=TREE;EnQueue(Q,w);			//頂點(diǎn)w入隊(duì)}}}
}

2.單源最短路徑問(wèn)題——Dijkstra算法

1. BFS算法的局限性：BFS算法求單源最短路徑只適?于?權(quán)圖，或所有邊的權(quán)值都相同的圖。
2. Dijkstra算法能夠很好的處理帶權(quán)圖的單源最短路徑問(wèn)題，但不適?于有負(fù)權(quán)值的帶權(quán)圖。
3. 使用 Dijkstra算法求最短路徑問(wèn)題，需要使用三個(gè)數(shù)組：

• final[]數(shù)組用于標(biāo)記各頂點(diǎn)是否已找到最短路徑。
• dist[]數(shù)組用于記錄各頂點(diǎn)到源頂點(diǎn)的最短路徑長(zhǎng)度。
• path[]數(shù)組用于記錄各頂點(diǎn)現(xiàn)在最短路徑上的前驅(qū)。

代碼實(shí)現(xiàn)

#define MAX_LENGTH = 2147483647;// 求頂點(diǎn)u到其他頂點(diǎn)的最短路徑
void BFS_MIN_Disrance(Graph G,int u){for(int i=0; i<G.vexnum; i++){		//初始化數(shù)組final[i]=FALSE;dist[i]=G.edge[u][i];if(G.edge[u][i]==MAX_LENGTH || G.edge[u][i] == 0)path[i]=-1;elsepath[i]=u;final[u]=TREE;}for(int i=0; i<G.vexnum; i++){int MIN=MAX_LENGTH;int v;// 循環(huán)遍歷所有結(jié)點(diǎn)，找到還沒(méi)確定最短路徑，且dist最?的頂點(diǎn)vfor(int j=0; j<G.vexnum; j++){if(final[j]!=TREE && dist[j]<MIN){MIN = dist[j];v = j;}}final[v]=TREE;// 檢查所有鄰接?v的頂點(diǎn)路徑長(zhǎng)度是否最短for(int j=0; j<G.vexnum; j++){if(final[j]!=TREE && dist[j]>dist[v]+G.edge[v][j]){dist[j] = dist[v]+G.edge[v][j];path[j] = v;}}}
}

3.各頂點(diǎn)間的最短路徑問(wèn)題——Floyd算法

1. Floyd算法：求出每?對(duì)頂點(diǎn)之間的最短路徑，使?動(dòng)態(tài)規(guī)劃思想，將問(wèn)題的求解分為多個(gè)階段。

2. Floyd算法可以?于負(fù)權(quán)值帶權(quán)圖，但是不能解決帶有“負(fù)權(quán)回路”的圖（有負(fù)權(quán)值的邊組成回路），這種圖有可能沒(méi)有最短路徑。

3. Floyd算法使用到兩個(gè)矩陣：

   1. dist[][]：目前各頂點(diǎn)間的最短路徑。
   2. path[][]：兩個(gè)頂點(diǎn)之間的中轉(zhuǎn)點(diǎn)。

4. 代碼實(shí)現(xiàn)：

int dist[MaxVertexNum][MaxVertexNum];
int path[MaxVertexNum][MaxVertexNum];void Floyd(MGraph G){int i,j,k;// 初始化部分for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++){dist[i][j]=G.Edge[i][j];		path[i][j]=-1;}}// 算法核心部分for(k=0;k<G.vexnum;k++){for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++){if(dist[i][j]>dist[i][k]+dist[k][j]){dist[i][j]=dist[i][k]+dist[k][j];path[i][j]=k;}}}}
}

4.最短路徑算法比較：

	BFS算法	D?kstra算法	Floyd算法
無(wú)權(quán)圖	?	?	?
帶權(quán)圖	?	?	?
帶負(fù)權(quán)值的圖	?	?	?
帶負(fù)權(quán)回路的圖	?	?	?
時(shí)間復(fù)雜度	O(|V|^2)或(|V|+|E|)	O(|V|^2)	O(|V|^3)
通常?于	求?權(quán)圖的單源最短路徑	求帶權(quán)圖的單源最短路徑	求帶權(quán)圖中各頂點(diǎn)間的最短路徑

三、有向?環(huán)圖描述表達(dá)式

1.有向?環(huán)圖：若?個(gè)有向圖中不存在環(huán)，則稱為有向?環(huán)圖，簡(jiǎn)稱 DAG圖（Directed Acyclic Graph）。

DAG描述表達(dá)式：((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)

2.有向無(wú)環(huán)圖描述表達(dá)式的解題步驟：

• Step 1:把各個(gè)操作數(shù)不重復(fù)地排成一排
• Step 2:標(biāo)出各個(gè)運(yùn)算符的生效順序 (先后順序有點(diǎn)出入無(wú)所謂)
• Step 3:按順序加入運(yùn)算符，注意“分層”
• Step 4:從底向上逐層檢查同層的運(yùn)算符是否可以合體

四、拓?fù)渑判?/h2>

1.AOV網(wǎng)(Activity on Vertex Network，用頂點(diǎn)表示活動(dòng)的網(wǎng)):用DAG圖(有向無(wú)環(huán)圖)表示一個(gè)工程。頂點(diǎn)表示活動(dòng)，有向邊<Vi,Vj>表示活動(dòng)Vi必須先于活動(dòng)Vj進(jìn)行。

2.拓?fù)渑判?/strong>：在圖論中，由?個(gè)有向?環(huán)圖的頂點(diǎn)組成的序列，當(dāng)且僅當(dāng)滿?下列條件時(shí)，稱為該圖的?個(gè)拓?fù)渑判?#xff1a;

• 每個(gè)頂點(diǎn)出現(xiàn)且只出現(xiàn)?次；
• 若頂點(diǎn) A 在序列中排在頂點(diǎn) B 的前?，則在圖中不存在從頂點(diǎn) B 到頂點(diǎn) A 的路徑。
• 或定義為：拓?fù)渑判蚴菍?duì)有向?環(huán)圖的頂點(diǎn)的?種排序，它使得若存在?條從頂點(diǎn) A 到頂點(diǎn) B 的路徑，則在排序中頂點(diǎn) B 出現(xiàn)在頂點(diǎn) A 的后?。每個(gè) AOV ?都有?個(gè)或多個(gè)拓?fù)渑判蛐蛄小?br /> ?

3.拓?fù)渑判虻膶?shí)現(xiàn):

• 從AoV網(wǎng)中選擇一個(gè)沒(méi)有前驅(qū) (入度為0) 的頂點(diǎn)并輸出
• 從網(wǎng)中刪除該頂點(diǎn)和所有以它為起點(diǎn)的有向邊。
• 重復(fù)D和2直到當(dāng)前的AOV網(wǎng)為空或當(dāng)前網(wǎng)中不存在無(wú)前驅(qū)的頂點(diǎn)為止

4.代碼實(shí)現(xiàn)拓?fù)渑判?#xff08;鄰接表實(shí)現(xiàn)）：

#define MaxVertexNum 100			//圖中頂點(diǎn)數(shù)目最大值typedef struct ArcNode{				//邊表結(jié)點(diǎn)int adjvex;						//該弧所指向的頂點(diǎn)位置struct ArcNode *nextarc;		//指向下一條弧的指針
}ArcNode;typedef struct VNode{				//頂點(diǎn)表結(jié)點(diǎn)VertexType data;				//頂點(diǎn)信息ArcNode *firstarc;				//指向第一條依附該頂點(diǎn)的弧的指針
}VNode,AdjList[MaxVertexNum];typedef struct{AdjList vertices;				//鄰接表int vexnum,arcnum;				//圖的頂點(diǎn)數(shù)和弧數(shù)
}Graph;								//Graph是以鄰接表存儲(chǔ)的圖類型// 對(duì)圖G進(jìn)行拓?fù)渑判?bool TopologicalSort(Graph G){InitStack(S);					//初始化棧，存儲(chǔ)入度為0的頂點(diǎn)for(int i=0;i<g.vexnum;i++){if(indegree[i]==0)Push(S,i);				//將所有入度為0的頂點(diǎn)進(jìn)棧}int count=0;					//計(jì)數(shù)，記錄當(dāng)前已經(jīng)輸出的頂點(diǎn)數(shù)while(!IsEmpty(S)){				//棧不空，則存入Pop(S,i);					//棧頂元素出棧print[count++]=i;			//輸出頂點(diǎn)ifor(p=G.vertices[i].firstarc;p;p=p=->nextarc){//將所有i指向的頂點(diǎn)的入度減1，并將入度為0的頂點(diǎn)壓入棧v=p->adjvex;if(!(--indegree[v]))Push(S,v);			//入度為0，則入棧}}if(count<G.vexnum)return false;				//排序失敗elsereturn true;				//排序成功
}

五、關(guān)鍵路徑

1.AOE 網(wǎng)：在帶權(quán)有向圖中，以頂點(diǎn)表示事件，以有向邊表示活動(dòng)，以邊上的權(quán)值表示完成該活動(dòng)的開(kāi)銷（如 完成活動(dòng)所需的時(shí)間），稱之為?邊表示活動(dòng)的?絡(luò)，簡(jiǎn)稱 AOE ? (Activity On Edge NetWork)。

2.AOE?具有以下兩個(gè)性質(zhì)：

1. 只有在某頂點(diǎn)所代表的事件發(fā)?后，從該頂點(diǎn)出發(fā)的各有向邊所代表的活動(dòng)才能開(kāi)始；
2. 只有在進(jìn)?某頂點(diǎn)的各有向邊所代表的活動(dòng)都已結(jié)束時(shí)，該頂點(diǎn)所代表的事件才能發(fā)?。 另外，有些活動(dòng)是可以并?進(jìn)?的。

3.在 AOE ?中僅有?個(gè)?度為 0 的頂點(diǎn)，稱為開(kāi)始頂點(diǎn)（源點(diǎn)），它表示整個(gè)?程的開(kāi)始； 也僅有?個(gè)出度為 0 的頂點(diǎn)，稱為結(jié)束頂點(diǎn)（匯點(diǎn)），它表示整個(gè)?程的結(jié)束。

• 從源點(diǎn)到匯點(diǎn)的有向路徑可能有多條，所有路徑中，具有最?路徑?度的路徑稱為關(guān)鍵路徑，?把關(guān)鍵路徑上的活動(dòng)稱為關(guān)鍵活動(dòng)。
• 完成整個(gè)?程的最短時(shí)間就是關(guān)鍵路徑的?度，若關(guān)鍵活動(dòng)不能按時(shí)完成，則整個(gè) ?程的完成時(shí)間就會(huì)延?。