基礎算法合集-圖論

?本文將介紹數據結構圖論部分中常見的算法

單源最短路徑問題(用來計算一個點到其他所有頂點的最短路徑)
Dijkstra(n*n)
1. 初始化: 先找出從源點V0到各終點Vk的直達路徑(V0,Vk), 即通過一條弧到達的路徑
2. 選擇: 從這些路徑中找出一條長度最短的路徑(V0,u)
3. 更新: 然后對其余各條路徑進行適當的調整
? ?若在圖中存在弧(u,Vk), ?且(Vo,u,Vk)<(Vo,Vk), 則以路徑(Vo,u,Vk) 代替(Vo,Vk)
4. 把V分成兩組:
? ?(1) S: 已求出最短路徑的頂點的集合
? ?(2) T=V-S: 尚未確定最短路徑的頂點集合
算法步驟:
1.初始時令S={V0}, T={其余頂點}
2.T中頂點對應的距離值用輔助數組D存放
? ?D[i] 初值: 若<V0,Vi>存在, 則為其權值; 否則為無窮 ?注: 從源點V0開始
3.從T中選取一個其距離值最小的頂點Vj, 加入S
4.對T中頂點的距離值進行修改: 若加進Vj 作中間頂點, 從V0到Vi的距離值比不加Vj的路徑要短, 則修改此距離值
重復上述步驟, 直到S=V為止
代碼實現：
輔助數組:?
-- 數組bool S[n]: 記錄相應頂點是否已被確定最短距離
-- 數組D[n]: 記錄源點到相應頂點路徑長度
-- 數組Path[n]: 記錄相應頂點的前驅頂點
1. 從D(T集合中)找最小值v ? 2. 將最小值對應的頂點, 加入S ? 3.更新D數組, Path數組
注：找最小值的時候要從D數組中為false的點中找, ?并且不能為源點

#include<iostream>
using namespace std;
#define MVNum 20
#define MAXNUM 32767
typedef char VerTexType;  //頂點類型
typedef int ArcType;      //弧類型 
typedef struct{VerTexType vexs[MVNum];   //vexs代表頂點,arcs代表鄰接矩陣ArcType arcs[MVNum][MVNum];int vexnum,arcnum;  //vexnum表示圖中頂點的數量，arcnum表示圖中邊的數量
}AMGraph;
int LocateVex(AMGraph G,VerTexType v){for(int i=0;i<G.vexnum;i++){if(v==G.vexs[i]){return i;}} return -1;
}
void CreateUDG(AMGraph &G){cin>>G.vexnum>>G.arcnum;for(int i=0;i<G.vexnum;i++){cin>>G.vexs[i];}for(int i=0;i<G.vexnum;i++){for(int j=0;j<G.vexnum;j++){G.arcs[i][j]=MAXNUM;}}VerTexType v1,v2;ArcType w;for(int k=0;k<G.arcnum;k++){cin>>v1>>v2>>w;int i=LocateVex(G,v1);int j=LocateVex(G,v2);G.arcs[i][j]=w;}
}
bool S[MVNum];
ArcType D[MVNum];
int Path[MVNum];
void ShortestPath_Dijkstra(AMGraph G,VerTexType u){int k=LocateVex(G,u);for(int i=0;i<G.vexnum;i++){S[i]=false;D[i]=G.arcs[k][i];if(D[i]<MAXNUM){Path[i]=k;}else{Path[i]=-1;}}S[k]=true;int min,v;for(int i=1;i<G.vexnum;i++){min=MAXNUM;for(int j=0;j<G.vexnum;j++){if(j!=k){if(!S[j]&&D[j]<min){min=D[j];v=j;}}}S[v]=true;for(int j=0;j<G.vexnum;j++){if(!S[j]&&D[v]+G.arcs[v][j]<D[j]){D[j]=D[v]+G.arcs[v][j];Path[j]=v; }}}}
int main(){AMGraph G;CreateUDG(G);char u;cin>>u;ShortestPath_Dijkstra(G,u);for(int i=0;i<G.vexnum;i++){cout<<D[i]<<" ";}return 0;
}

所有頂點間的最短路徑
方法一：每次以一個頂點源點, 重復執行Dijkstra算法n 次
方法二：floyd 算法(n*n*n)
以上兩種方法的時間復雜度是一樣的
1. 初始時設置一個n階方陣, 令其對角線元素為0, 若存在弧<Vi,Vj>, 則對應元素為權值; 否則為無窮
2. 逐步試著在原直接路徑中增加中間節點, 若加入中間節點后路徑變短, 則修改之; 否則, 維持原值. 所有頂點試探完畢, 算法結束
代碼實現：
path 數組初始時為-1, 存儲的是前驅節點
鄰接矩陣, 對角線存儲的是0, 有權值就存權值, 沒有權值就存儲無窮

#include<iostream>
using namespace std;
#define MVNum 20
#define MAXNUM 32767
typedef char VerTexType;  //頂點類型
typedef int ArcType;      //弧類型 
typedef struct{VerTexType vexs[MVNum];   //vexs代表頂點,arcs代表鄰接矩陣ArcType arcs[MVNum][MVNum];int vexnum,arcnum;  //vexnum表示圖中頂點的數量，arcnum表示圖中邊的數量
}AMGraph;
int LocateVex(AMGraph G,VerTexType v){for(int i=0;i<G.vexnum;i++){if(v==G.vexs[i]){return i;}} return -1;
}
void CreateUDG(AMGraph &G){cin>>G.vexnum>>G.arcnum;for(int i=0;i<G.vexnum;i++){cin>>G.vexs[i];}for(int i=0;i<G.vexnum;i++){for(int j=0;j<G.vexnum;j++){if(i!=j){G.arcs[i][j]=MAXNUM;}else{G.arcs[i][j]=0;}}}VerTexType v1,v2;ArcType w;for(int k=0;k<G.arcnum;k++){cin>>v1>>v2>>w;int i=LocateVex(G,v1);int j=LocateVex(G,v2);G.arcs[i][j]=w;}
}
ArcType D[MVNum][MVNum];
int P[MVNum][MVNum];
void ShortestPath_Floyd(AMGraph G){for(int i=0;i<G.vexnum;i++){for(int j=0;j<G.vexnum;j++){D[i][j]=G.arcs[i][j];if(D[i][j]<MAXNUM&&i!=j){P[i][j]=i;}else{P[i][j]=-1;}	 }}for(int k=0;k<G.vexnum;k++){  //我咧個n次嘗試 for(int i=0;i<G.vexnum;i++){for(int j=0;j<G.vexnum;j++){if(D[i][j]>D[i][k]+D[k][j]){D[i][j]=D[i][k]+D[k][j];P[i][j]=P[k][j];  //從上一個Path二維表里面找,永遠存儲的是距離終點最近的前驅頂點(因為k是按順序進行嘗試的) }}	}}
}
void Print(int n){for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(D[i][j]<MAXNUM){printf("%4d(%2d)",D[i][j],P[i][j]);}else{printf("%4c(%2d)",'#',P[i][j]);}}printf("\n");}
} 
int main(){AMGraph G;CreateUDG(G);int n=G.vexnum;ShortestPath_Floyd(G);Print(n);return 0;
}

?總結來說第一種算法就是先找最小值, 第二種算法就是n次嘗試

關鍵路徑問題：拓撲排序
把工程計劃表示為邊表示活動的網絡, 即AOE網, 用頂點表示事件, 弧表示活動, 弧的權表示活動持續時間
事件(頂點)表示在它之前的活動已經完成，在它之后的活動可以開始
源點：入度為0的頂點 ? 匯點：出度為0的頂點
關鍵路徑----路徑長度最長的路徑
路徑長度----路徑上各活動持續時間之和
ve(vj)----表示事件vj的最早發生時間
vl(vj)----表示事件vj的最遲發生時間
e(i)----表示活動ai的最早開始時間 ? l(i)----表示活動ai的最遲開始時間
l(i)-e(i)----表示完成活動ai的時間余量
關鍵活動----關鍵路徑上的活動，即l(i)==e(i)(即l(i)-e(i)==0) 的活動
如何找到l(i) == e(i) 的關鍵路徑？
? ? 設活動ai用弧<j,k>表示，其持續時間記為：Wj,k
? ? 則有：(1) e(i)==ve(j) ? ? ? ? ? -> 直接查弧尾的最早發生時間
? ? ? ? ? ? ?(2) l(i) = vl(k) - Wj,k ? -> 直接查弧頭的最遲發生時間- 權值w
如何求ve(j) 和 vl(j) ？
事件j的最早發生時間？
(1) 從ve(1) = 0 開始向前遞推
? ? ?ve(j) = Max{ve(i)+Wi,j},<i,j>->T, 2=<j<=n
? ? ?其中T是所有以j為頭的弧的集合
事件i的最晚發生時間?
(2) 從vl(n)==ve(n) 開始向后向后遞推
? ? ?vl(i)=Min{vl(j)-Wi,j}, <i,j>->S,1<=i<=n-1
? ? ?其中S是所有以i為尾的弧的集合
1.第一個是從源點往右算 ?2. 第二個是從匯點往左算?

生成樹：所有定點均由邊連接在一起, 但不存在回路的圖
? ? - 一個圖可以有許多棵不同的生成樹
? ? - 所有生成樹具有以下共同特點
1. 生成樹的頂點個數與圖的頂點個數相同
2. 生成樹是圖的極小連通子圖，去掉一條邊則非聯通
3. 一個有n個頂點的連通圖的生成樹有n-1 條邊
4. 在生成樹中再加一條邊必然形成回路
5. 生成樹中任意兩個頂點間的路徑是唯一的
最小生成樹：給定一個無向網絡，在該網的所有生成樹中，使得各邊權值之和最小的那顆生成樹稱為該網的最小生成樹，也叫最小代價生成樹
已上兩種定義簡單來說就是：1.生成樹就是連通但是內部沒有環，有n-1條邊. ?2. 最小生成樹就是權值最小的生成樹
MST性質：
在生成樹的構造過程中，圖中n個頂點分屬兩個集合：
? ? ?- 已落在生成樹上的頂點集: ?U
? ? ?- 尚未落在生成樹上的頂點集: ?V-U
接下來則應在所有連通U中頂點和V-U中頂點的邊種選取權值最小的邊(作為生成樹的一條邊,前提是不能有回路)
Prim 算法
設N={V,E} 是連通網, TE是N上最小生成樹中邊的集合 ? ? ? ?{a,b} a 代表點, b代表邊
1. 初始令U={u0},{u0->V},TE={ }
2. 在所有u->U, v->V-U的邊(u,v)->E中，找一條代價最小的邊(u0,v0). 注: 就是權值最小的邊
3. 將(u0,v0) 這條邊并入集合 TE, 同時 v0這個點并入U
4. 重復上述操作直至U=V為止, 則T=(V,TE) 為N 的最小生成樹 ?（意思就是把所有的點都選進集合U, 所以前面寫的是U=V）

通俗解釋：在U集合中選一個點和在U-V集合中選一個點, 使得這個權值的最小, 然后把弧上的頂點加入到集合U中, 直到U=T集合，得到的連通圖就是最小生成樹

#include<stdio.h>
#define max 32767
typedef struct
{char *date;int **array;int nodenumber,edgenumber;
} Graph;
struct close   //保存節點的權值和字符
{char date;int wed;
};
int LocateNode(Graph L,char ch)
{for(int i=0; i<L.nodenumber; i++)if(L.date[i]==ch) return i;return -1;
}
void CreatUDG(Graph &L)
{scanf("%d %d",&L.nodenumber,&L.edgenumber);//輸入圖的節點數和邊數getchar();L.date=new char[L.nodenumber];   //節點數組L.array=new int*[L.nodenumber];  //鄰接矩陣for(int i=0; i<L.nodenumber; i++){L.date[i]=getchar();getchar();L.array[i]=new int[L.nodenumber];}for(int i=0; i<L.nodenumber; i++)for(int j=0; j<L.nodenumber; j++)L.array[i][j]=max;for(int k=0; k<L.edgenumber; k++){char ch1,ch2;int w;scanf("%c %c %d",&ch1,&ch2,&w);getchar();int i=LocateNode(L,ch1);int j=LocateNode(L,ch2);L.array[i][j]=w;L.array[j][i]=w;}
}
int min(struct close *clos,int n)
{int k;for(int i=1; i<n; i++)if(clos[k].wed==0||(clos[i].wed!=0&&clos[i].wed<clos[k].wed)) k=i;return k;
}
void Prim(Graph L,char v)
{struct close clos[L.nodenumber];int k=LocateNode(L,v);for(int i=0; i<L.nodenumber; i++){clos[i].date=v; 	//類似于一種前驅節點的感覺clos[i].wed=L.array[k][i];}//起始節點與其他節點建立聯系clos[k].wed=0; //將起始節點的權值設置為0，表示起始節點已經被選中for(int i=1; i<L.nodenumber; i++){k=min(clos,L.nodenumber);char u0=clos[k].date;   //存儲的是k的前驅節點char v0=L.date[k];      //索引k下的節點字符printf("(%c,%c)\n",u0,v0);clos[k].wed=0;          //將選中節點的權值設置為0,表示已經加入到最小生成樹for(int j=0; j<L.nodenumber; j++)  //這個循環遍歷圖中的所有節點。變量 j 表示當前正在檢查的節點的索引//如果當前被選中的節點(索引為k),到其他(未被選入最小生成樹)節點的權值比原來更小,那么if(L.array[k][j]<clos[j].wed)  {clos[j].date=L.date[k];  //更新前驅// 更新 clos 數組中節點 j 的字符為當前選中節點的字符clos[j].wed=L.array[k][j]; //更新權值//更新 clos 數組中節點 j 的權值為當前選中節點與節點 j 之間的邊的權重}}
}
int main(){Graph L;CreatUDG(L);Prim(L,L.date[0]);  //傳到Prim函數集合U中起始節點U0return 0;
}

?Kruskal算法
1.設連通網 N=(V,E), 令最小生成樹初始化狀態為只有n個頂點而無邊的非聯通圖 T={V,{ }}, 每個頂點自成一個聯通分量
2. 在E中選取代價最小的邊, 若該邊依附的頂點落在 T中不同的連通分量上(即: 不能成環), 則將此邊加入到T中; 否則, 舍去此邊, 選取下一條代價最小的邊
3.依次類推, 直至T中所有頂點都在同一連通分量上為止
注：通俗來講就是, 直接把所有頂點都先加入到生成樹T中, 然后從所有的邊中一次找最短, 次短的邊....進行連通,(但是不能成環)

注：最小生成樹可能有很多個，同時Kruskal算法在尋找最小邊的時候, 可以使用小頂堆{priority_queue<int,vector<int>,greater<int>> pq}, s所以Kruskal算法的時間復雜度就是堆排序的時間復雜度
兩種算法比較:
算法名 ? ? ? ? Prim算法 ? ? ? ? ? ? ? ? ? ? Kruskal算法
算法思想 ? ? ?選擇點 ? ? ? ? ? ? ? ? ? ? ? ? 選擇邊
時間復雜度 ? O(n^2)(n為頂點數) ? ? O(eloge)(e為邊數)
適應范圍 ? ? ?(稠密圖)(點多的) ? ? ? ? ?稀疏圖(邊多的)

#include<algorithm>
#include<iostream>
using namesapce std;
#define MVNum 20    //定點數的最大值
#define MANum 20    //邊數的最大值
typedef char VerTexType;
typedef int ArcType;
typedef struct{VerTexType vexs[MVNum];int vexnum,arcnum;
}AMGraph;
typedef struct{VerTexType Head; //邊的起始點VerTexType Tail; //邊的終止點ArcType lowcost; //邊上的權值
}Edge; //邊的類型
Edge edges[MANum] //存儲邊信息的輔助數組
//輔助數組 VexSet,記錄每個頂點所在聯通分量編號
int VexSet[MVNum];
//確定頂點v在G中位置, 即頂點數組的下標
int LocateVex(AMGraph G,VerTexType v){for(int i=0;i<G.vexnum;i++){if(v==G.vexs[i]){return i;}}return -1;
}
void CreateAMGraph(AMGraph &G){cin>>G.vexnum>>G.arcnum;for (int i = 0; i <G.vexnum; i+){cin>>G.vexs[i];}VerTexType v1,v2;ArcType w;for(int k=0;k<G.arcnum;k++){cin>>v1>>v2>>w;edges[k].Head=v1;edges[k].Tail=v2;edges[k].lowcost=w;}
}
//按邊上的權值Lowcost進行排序
bool cmp(Edge a,Edge b){if(a.lowcost<b.lowcost){return true;}
}
void MiniSpanTree_Kruskal(AMGraph G){//按邊上的權值Lowcost進行排序sort(edges,edges+G.arcnum,cmp);//初始化,每個頂點都是一個獨立的連通分量for(int i=0;i<G.vexnum;i++){VexSet[i]=i;}//反復執行，獲取G.vexnum-1邊for(int i=0;i<G.arcnum;i++){int v1=LocateVex(G.edges[i].Head); //邊的起始頂點存儲位置的序號,那個頂點    通俗講：就是找頂點存儲在數組的那個位置int v2=LocateVex(G.edges[i].Tail); //邊的終止頂點存儲位置的序號,那個頂點int vs1=VexSet[v1];  //邊的起始頂點所在聯通分量的編號int vs1=VexSet[V2];  //邊的終止頂點所在連通分量的編號if(vs1!=vs2){printf("(%c,%c)\n",edges[i].Head,edges[i].Tail);//同時將起始頂點所在聯通分量和終止頂點所在的連通分量進行(合并)統一編號，變為起始頂點所在連通分量//經過多次統一編號之后, 每個連通分量中就會包含多個頂點for(int j=0;j<G.vexnum;j++){if(VexSet[j]==vs2){VexSet[j]=vs1;}}}}
}
int main(){AMGraph G;CreateAMGraph(G);MiniSpanTree_Kruskal(G)return 0;
}