圖的定義和基本術(shù)語

1. 圖：有向圖、網(wǎng)，無向圖、網(wǎng)。
2. 頂點(diǎn)
3. 邊：有向圖圖稱作弧，分弧頭弧尾。
4. 依附：邊依附點(diǎn)，邊和點(diǎn)關(guān)聯(lián)
5. 鄰接：點(diǎn)鄰接點(diǎn)
6. 度：點(diǎn)關(guān)聯(lián)的邊的數(shù)目
7. 完全圖：
   無向：$C_n^2$條邊;
   有向：$2C_n^2$條邊
8. 連通：若干結(jié)點(diǎn)互相可以通信，用手提起一個(gè)結(jié)點(diǎn)可以順帶提起其他與之連通的結(jié)點(diǎn)。
9. 路徑：用一個(gè)頂點(diǎn)序列表示，注意與樹中的路徑區(qū)分，本質(zhì)是一樣的。
10. 強(qiáng)連通：有向圖各頂點(diǎn)相互可達(dá)
11. 單向連通：有向圖任意兩頂點(diǎn)至少一方可達(dá)
12. 弱連通：有向圖的弧去掉方向后得到的無向圖連通，稱之為弱連通。
    強(qiáng)連通 -> 單向連通 -> 弱連通
13. 連通分量（極大連通子圖）：一個(gè)連通的局部圖，并且所包含的頂點(diǎn)的所有關(guān)聯(lián)的邊都在此圖中。同時(shí)，再加入額外的任意頂點(diǎn)，此圖不連通。(換種表述，把原圖往天上一揚(yáng)，掉在地上的每部分都是連通分量)
14. 生成樹（極小聯(lián)通子圖）：包含原圖所有頂點(diǎn)的一棵樹。
    最小生成樹（MST）：各邊代價(jià)之和最小的一棵生成樹

圖的存儲結(jié)構(gòu)

• 鄰接矩陣

typedef struct {
	VexType vexs[MAXSIZE];	//頂點(diǎn)向量
	AdjMatrix arcs;	//邊矩陣
	int vexnum,arcnum;		//頂點(diǎn)數(shù)，邊數(shù)
	int kind;
}MGraph;
typedef int AdjMatrix[MAXSIZE][MAXSIZE];

• 鄰接表（孩子表示法，call back）

typedef struct{
	AdjList vertices;	//頭結(jié)點(diǎn)向量
	int vexnum,arcnum;
	int kind;
}ALGraph;
typedef struct{
	VexType data;	//存放頂點(diǎn)
	ArcNode *firstarc;	//指向邊結(jié)點(diǎn)
}VNode,AdjList[MAXSIZE];
typedef struct ArdNode{
	int adjvex;	//頂點(diǎn)所鄰接到的點(diǎn)
	struct ArcNode* next;
	//int weight; //網(wǎng)
}

鄰接表相對來說比較省空間，但實(shí)現(xiàn)麻煩一些。鄰接表求度的時(shí)候要遍歷整個(gè)鄰接表，可建立一個(gè)逆鄰接表解決。

圖的遍歷

• 廣度優(yōu)先遍歷（Broadth_First Search）
  輔助隊(duì)列

算法設(shè)計(jì)：
 起始頂點(diǎn)入隊(duì)。
 while 隊(duì)不空
 	頂點(diǎn)出隊(duì)
 	  訪問
 	所有鄰接點(diǎn)入隊(duì)
算法描述：
// BFS遍歷整個(gè)圖,需要再加一個(gè)visited數(shù)組記錄當(dāng)前結(jié)點(diǎn)是否已經(jīng)訪問過。
void BFSTraverse(MGraph G){	//鄰接矩陣存儲圖
	int visted[MAXSIZE] = {0};
	SqQueue Q;
	InitQueue(Q)；
	for(int u = 0; u < vexnum; u ++){
		if(!visited[u]){
			EnQueue(u);
			while(!QueueEmpty(Q)){
				int v; 
				DeQueue(Q,v)
				printf("%d",G.vexs[v]);		//訪問
				visited[v] = true;
				for(int w = 0; w < G.vexnum; w ++){	//鄰接點(diǎn)入隊(duì)
					if(G.arcs[v][w])
						EnQueue(Q,w);
				}
			}
		}
	}
}

• 深度優(yōu)先遍歷（Depth_First Search）
  利用遞歸的輔助函數(shù)棧

算法思想:
	int visited[MAXSIZE]
	void DFS(ALGraph G,int u){	//從某個(gè)頂點(diǎn)開始的DFS，鄰接表
		printf("%d",G.vertices[u].data);
		visitedp[u] = 1;
		for(ArcNode *w = G.vertices[u].firstarc; w; w = w->next){
			if(!visited[w->adjvex])
				DFS(G,w->adjvex);
		}
	}
	void DFSTraverse(ALGraph G,int u){	//保證遍歷全圖
		for(int v = 0; v < G.vexnum; v++){
			if(!visited[v])
				DFS(G,v);
		}
	}

最小生成樹（無向圖）

• 普里姆算法(Prim)
  從頂點(diǎn)的角度出發(fā)，適合稠密圖。借助closedge數(shù)組。
  O($n^2$)

struct {
	int adjvex; 	//記錄鄰接點(diǎn)
	int lowcost;	
} closedge[MAXSIZE];

算法思想：
求連通圖的最小生成樹，貪心思想。
1.頂點(diǎn)并入集合S
2.更新 V - S 到 S的距離
3.尋找最小邊
4.重復(fù)1,2,3

void Prim(MGraph G,int u){//從頂點(diǎn)u開始
	closedge[u].lowcost = 0;	 //頂點(diǎn)并入S
	printf("%c",G.vexs[u]);
	for(int  i = 0; i < G.vexnum; i ++){ //更新距離
		if(i!=u) closedge[i].lowcost = G.arcs[u][i];		
	}
	for(int i = 1; i <= n; i++){	//找其他 n - 1 個(gè)頂點(diǎn)
		int v = getMin(closedge);	//找到closedge 中的最小邊所鄰接到的頂點(diǎn)。注意lowcost = 0的頂點(diǎn)不被比較
		closedge[v].lowcost = 0;	//并入S
		printf("%c",G.vexs[v]);		//訪問
		for(int w = 0; w < G.vexnum; w++){	//更新lowcost
			if(G.arcs[v][w] < closedge[w].lowcost){
				closedge[w].adjvex = v;
				closedge[w].lowcost = G.arcs[v][w];
			}
		}
	}
}

• 克魯斯卡爾算法（Kruskal）
  適合稀疏圖,$O(eloge)$

算法思想：貪心
1. 遍歷所有邊找出最小邊
2. 此邊加入邊集合E
3. 檢查E中是否存在環(huán)
4. 存在則舍棄該邊
重復(fù)1,2,3,4

算法實(shí)現(xiàn)：
目前不會

最短路徑（帶權(quán)有向圖）

• 單源最短路徑
  Dijkstra算法
  算法思想： 貪心
  從頂點(diǎn)開始依次找頂點(diǎn)從開始的第k短路徑。0 < k < n;
  這樣每條路徑的終點(diǎn)各不相同，恰好對應(yīng)了剩余的n-1個(gè)頂點(diǎn)，求得的路徑也就是最短路徑。
  算法實(shí)現(xiàn)：
  和Prim算法及其相似。
  只需對Prim算法修改三條語句，見序號

void Dijkstra(MGraph G,int u){//從頂點(diǎn)u開始
	closedge[u].lowcost = 0;	 //頂點(diǎn)并入S
	//printf("%c",G.vexs[u]);	Dij不需要在這訪問		①
	for(int  i = 0; i < G.vexnum; i ++){ //更新距離
		if(i!=u) closedge[i].lowcost = G.arcs[u][i];		
	}
	for(int i = 1; i <= n; i++){	//找其他 n - 1 個(gè)頂點(diǎn)
		int v = getMin(closedge);	//找到closedge 中的最小邊所鄰接到的頂點(diǎn)。注意lowcost = 0的頂點(diǎn)不被比較
		closedge[v].lowcost = 0;	//并入S
		//printf("%c",G.vexs[v]);		//同①不需訪問
		for(int w = 0; w < G.vexnum; w++){	//更新lowcost
			if(G.arcs[v][w] + closedge[v].lowcost < closedge[w].lowcost){	② //這里改變判斷條件，看中轉(zhuǎn)到達(dá)和直達(dá)哪條路近。
				closedge[w].adjvex = v;
				closedge[w].lowcost = G.arcs[v][w] + closedge[v].lowcost;	    ③ //同上
			}
		}
	}
}

這樣實(shí)現(xiàn)后，closedge[i].lowcost 存放了從起點(diǎn)到該頂點(diǎn)的最短路徑。closedge[i]的adjvex存放了該頂點(diǎn)的鄰接點(diǎn)即弧尾，有了這個(gè)弧尾，可以很容易地寫一個(gè)遞歸函數(shù)，回溯到起點(diǎn)然后輸出該路徑。

• 任意一對頂點(diǎn)之間的最短路徑
  算法思想：
  1.可以調(diào)用n次Dijkstra算法,求每個(gè)頂點(diǎn)的單源最短路徑，時(shí)間復(fù)雜度為O($n^3$)。
  2.Floyd算法：動(dòng)態(tài)規(guī)劃
  另一種角度考慮，求該對頂點(diǎn)的間的最短路徑，即求以其他頂點(diǎn)為中轉(zhuǎn)點(diǎn)到達(dá)和直達(dá)所耗費(fèi)代價(jià)的最小值。
  如圖，求i->j的最短路徑，可以以k為中轉(zhuǎn)點(diǎn)。 其中i->k也是i->k的最短路徑，k->j也是k->j的最短路徑。
  

算法描述：

void Floyd(int n, int **cost,int **path){	//，Path[i][j]保存從i->j的最后中轉(zhuǎn)點(diǎn)k
	for(int k = 0;k < n; k++)	//每個(gè)結(jié)點(diǎn)都可能作為中轉(zhuǎn)點(diǎn)
		for(int i = 0;i < n; i++)
			for(int j = 0; j < n; j++){
				if(cost[i][k] + cost[k][j] < cost[i][j]){
					cost[i][j] = cost[i][k] + cost[k][j];
					path[i][j] = path[k][j];	//這里不是k，因?yàn)閗->j還可能中轉(zhuǎn)
				}
	}
}
int main(){
	int n,m,t1,t2,t3,u,v;
	int cost[MAXSIZE][MAXSIZE];	//cost[i][j]保存i->j的代價(jià)
	cin >> n;	//頂點(diǎn)數(shù)，默認(rèn)頂點(diǎn)為 0 - n-1
	cin >> m	//邊數(shù)
	for( i = 0; i < n; ++ i){	//初始化代價(jià)
		for(j = 0; j < n; j++){
			if(i==j)
				cost[i][j] = 0;
			else
				cost[i][j] = INFINITY;
		}
	}
	for(int i = 0; i < m; i++){	//輸入邊和代價(jià)
		cin >> t1 >> t2 >> t3;
		cost[t1][t2] = t3;
		path[t1][t2] = t1;
	}
	Floyd(n,cost,path);
	cin >> u >> v;
	printf("%d",cost[u][v]);
	ShowPath(path,u,v);	//同closedge數(shù)組的adjvex回溯方法
	return 0;
}

Floyd學(xué)自此處。

有向無環(huán)圖及其應(yīng)用

有向無環(huán)圖（Directed acyline graph）

• 拓?fù)渑判?br> 對于一個(gè)有向圖，進(jìn)行拓?fù)渑判虻牟襟E如下：
  1. 在圖中尋找入度為0的頂點(diǎn)。
  2. 從頂點(diǎn)集中刪除該頂點(diǎn)，訪問，把該點(diǎn)的鄰接點(diǎn)所對應(yīng)的入度-1
  3. 重復(fù)1,2
• AOV-網(wǎng) (Activity On Vertex Network)
  在頂點(diǎn)表示活動(dòng)的網(wǎng),弧表示優(yōu)先關(guān)系。
  
  要進(jìn)行C活動(dòng)，必須以完成A&B活動(dòng)為前提。
  
  上圖不是一個(gè)AOV-網(wǎng)，A頂點(diǎn)進(jìn)行活動(dòng)不能以完成A頂點(diǎn)為前提。
  判斷一個(gè)圖是不是AOV-網(wǎng)：
  1. 拓?fù)渑判?，記錄排序的活?dòng)數(shù)目
  2. 活動(dòng)數(shù)目小于頂點(diǎn)數(shù)則代表存在環(huán)。
  3. 2成立則返回0，否則返回1

int indegree[MAXSIZE];	//保存各頂點(diǎn)入度的向量,假設(shè)已在其他函數(shù)中賦值
int TopoSort(ALGraph G){
	int cnt = 0;
	SqStack S;
	InitStack(S);
	for(int i = 0; i < G.vexnum; i++){
		if(!indegree[i])Push(S,i);	//初始入度為0的結(jié)點(diǎn)入棧
	}
	while(!StackEmpty()){
		int u;
		Pop(S,u);
		cnt ++；
		printf("%c",G.vertices[u].data);
		for(ArcNode*w = G.vertices[u].firstarc; w; w = w->next){
			indegree[w->adjvex]--;	//入度-1
			if(indegree[w->adjvex]==0)Push(S,w->adjvex);	//是否入棧
		}
	}
	return G.vexnum==cnt?1:0;
}

• AOE-網(wǎng)(Activity on Edge Network)
  用弧表示活動(dòng)的網(wǎng)，是一個(gè)帶權(quán)的有向無環(huán)圖，頂點(diǎn)表示事件（Event）。通?？捎脕砉浪愎こ痰耐瓿蓵r(shí)間。
  源點(diǎn)：入度為0，工程開始
  匯點(diǎn)：出度為0，工程結(jié)束
  關(guān)鍵活動(dòng)：e(i) = l(i)
  關(guān)鍵路徑：從源點(diǎn)到匯點(diǎn)代價(jià)最高的路徑。
  關(guān)鍵路徑求解
  
  e(i):活動(dòng)開始的最早時(shí)間
  l(i):活動(dòng)開始的最晚時(shí)間
  ve(i):事件i發(fā)生的最早時(shí)間
  vl(i):事件i發(fā)生的最晚時(shí)間
  以$v_3$為例，ve(3) = Max{ve(5)+$a_3$,ve(4)+$a_4$},再往前遞推求ve(5),ve(4)。
  以$v_4$為例，vl(4) = Min{vl(3)-$a_4$,vl(2)-$a_6$}，再往后遞推求vl(3),vl(2)。
  以$a_3$為例，e(3) = ve(5),l(3) = vl(3) - $a_3$
  根據(jù)上述過程，可知先求ve、vl再求e，l?？傻萌缦卤砀?br> 表格的填充過程為先從左到右填ve,再從右到左填vl

???????顯然ve(i)=vl(i)的事件被限定死了發(fā)生時(shí)間，那么｛$vi|ve(i)=vl(i)$｝這個(gè)頂點(diǎn)序列，就構(gòu)成了一條關(guān)鍵路徑，路徑上的活動(dòng)都是關(guān)鍵活動(dòng)。
注意：
關(guān)鍵路徑可能有多條，只縮短某條關(guān)鍵路徑上的某個(gè)活動(dòng)的工期并不能提前整個(gè)工程的完成時(shí)間，只有這個(gè)關(guān)鍵活動(dòng)屬于所有關(guān)鍵路徑，才能提高完成時(shí)間。文章來源地址http://www.zghlxwxcb.cn/news/detail-790144.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】第七章-圖【期末復(fù)習(xí)】的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！