前言
這期是基礎算法篇的第三節，其中的dijkstra算法更是藍橋杯中的高頻考點
圖的基本相關概念
有向圖和無向圖 自環和重邊 稠密圖和稀疏圖
對于不帶權的圖，一條路徑的路徑長度是指該路徑上各邊權值的總和
對于帶權的圖，一條路徑長度時指該路徑上各個邊權值得總和
頂點的度是指和它相關聯的邊的條數，由該頂點發出的邊稱為頂點的出度，到達該頂點的邊稱為頂點的入度
無向圖中才有聯通圖和聯通分量這些概念
考的時候:有些數據輸入格式就是按圖給的
（eg:u和v之間有一條長度為k的邊）
如果沒有說圖沒有重邊和自環，一般默認測試點的圖會有重邊和自環
有向無環圖可以搭配上動態規劃用(eg：拓撲+動態規劃)(在問最短路有幾條時，常要用到動態規劃)
圖的存儲
有兩種方式:鄰接矩陣和鄰接表
1.鄰接表的存儲方式和樹的孩子表示法一樣，用vector數組和鏈式前向星都可以實現
2.鄰接矩陣是用一個二維數組，其中edge[i][j]存儲頂點i與頂點j之間的邊的信息
鄰接矩陣:
1.對于帶權圖而言，若頂點i和頂點j之間有邊相連，則鄰接矩陣中對應項存放著該邊對應的權值若頂點i和頂點j之間不相連，則用無窮大(有時用其他)代表這兩頂點間無邊
2.對于不帶權的圖，可以創建一個二維的bool類型的數組，來標記頂點i和j之間有邊相連
時間復雜度為:O(n平方)，因此適合存稠密圖
注意:鄰接矩陣如果有重邊，一般存其最小值
代碼展示:int edges[N][N];//一般需要初始化，vector那個則不用for(int i = 1;i<=m;i++)
{int a,b,c;cin>>a>>b>>c;//a和b之間有一條邊，權值為cedges[a][b] = c;//如果是無向邊，需要反過來再存一下edges[b][a] = c;}
鄰接表:
自己一般喜歡使用vector數組去存
如果存在邊權的話，vector數組里面需要放結構體或者pair
pair自己喜歡第一個數據記錄邊的終點，第二個數據記錄邊權值
vector數組的下標表示邊的起點代碼展示:vector<pair<int,int>> edges[N];for(int i=1;i<=m;i++)
{int a,b,c;cin>>a>>b>>c;//a和b之間有一條邊，權值為cedges[a].push_back{(b,c)};//如果是無向邊，需要反過來再存一下edges[b].push_back{(a,c)};}
圖的遍歷
圖的遍歷有DFS和BFS，和樹的遍歷的實現方法一樣
自己常用dfs來搞:
1.鄰接矩陣：void dfs(int u)
{cout<<u<<endl;st[u] = true;for(int v =1;v<=n;v++){//如果存在u->v的邊，并且沒有遍歷過if(edges[u][v]!=-1&&st[v])dfs(v);}}main函數里面有memset(edges,-1,sizeof edges);2.vector數組:void dfs(int u){cout<<u<<endl;st[u] = true;for(auto&t:edges[u]){//u->v的一條邊，權值為wint v = t.first,w=t.second;if(!st[v]){ dfs[v];}}}
最小生成樹
一般用普利姆(Prim)算法和克魯斯卡爾(Kruskal)算法去構造最小生成樹
最小生成樹面向的是無向圖，如果有向圖有無向圖返回的性質，也可以用此
Prim算法:
核心:不斷加點
步驟:
1.從任意一點開始構造最小生成樹（一般選1為起點,dist[1] = 0）
2.將距離該樹權值最小且不在樹中的頂點，加入到生成樹中。（記得判斷是否聯通）然后更新與該點相連的點到生成樹的最短距離(不要忘了考慮重邊和自環!)
3.重復2操作n次，直到所有頂點都加入為此Kruskal算法:(運行時間和空間時間允許的話，建議用這個)
核心:不斷加邊
步驟:
1.所有邊按照權值排序
2.每次選出權值最小且兩端頂點不連通的一條邊，直到所有頂點都聯通
時間復雜度:m*logm(m是邊數)
這個算法不用圖，只用存邊，用結構體存即可(也不算鄰接表)
定理：最小生成樹就是瓶頸生成樹
瓶頸生成樹:所有生成樹中，最大的邊權的值最小的那棵樹
拓撲排序
拓撲排序的目標是將有向無環圖中的所有結點排序
適用于有要完成了前置項才能走的點的圖(AOV網)
(eg:一個攝像頭能被砸毀的條件是該攝像頭所在位置不被其他攝像頭監視）
實現方法:
1.將圖中所有入度為0的點，加入到隊列中2.取出隊頭元素，刪除與該點相連的邊。如果刪除之后的后繼結點入度變為0，加入到隊列中
3.重復2操作，直到圖中沒有點或者沒有入度為0的點為止
需要搞個vectoredges[N]存N的后繼
int in[N]存入度信息eg: edges[i].push_back(j);//i的后繼為j
in[j]++;//統計入度信息例題: 洛谷 B3644 【模板】拓撲排序/家譜樹
拓撲排序判斷是否有環:
跑一遍拓撲排序，如果有結點沒有進隊，那么表明有環
單源最短路
概念:圖中一個頂點到其他各頂點的最短路徑
有向圖，無向圖都能用
常見版dijkstra算法：
流程:
1.創建一個長度為n的dist數組，其中dist[i]表示從起點到i結點的最短路
2.創建一個長度為n的bool數組st，其中st[i]表示i點是否已經確定了最短路
3.初始化:dist[i] = 0,其余結點的dist值為無窮大，表示還沒有找到最短路
4.在所有沒有確定最短路的點中，找出最短路長度最小的點u。打上確定最短路的標記，然后對u的出邊進行松弛操作松弛操作:if(dist[u]+w<dist[v])dist[v] = dist[u]+w;堆優化版的dijkstra算法:
1.創建一個長度為n的dist數組，其中dist[i]表示從起點到i結點的最短路創建一個長度為n的bool數組st，其中st[i]表示i點是否已經確定了最短路創建一個小根堆，維護更新后的結點.（也就是需要確定最短路的結點）
eg:priority_queue<PII,vector<PII>,greater<PII>>heap
2.初始化:dist[i]=0，然后講{0,s}加到堆里，其余結點的dist值為無窮大，表示還找到最短路
3.彈出堆頂元素，如果該元素已經標記過，就跳過；如果沒有，打上標記，進行松弛操作bellman-ford算法（簡稱BF算法）:
核心思想:不斷嘗試對圖上的每一條邊進行松弛，直到所有的點都無法松弛為止
1.創建一個長度為n的dist數組，其中dist[i]表示從起點到i結點的最短路
2.初始化:dist[i]=0，其余結點的dist值為無窮大，表示還沒有找到最短路
3.每次都對所有的邊進行一次松弛操作(一般按結點編號順序來找邊去松弛)
4.重復上述操作，直到所有邊都不需要松弛為止
這個算法也不需要存圖spfa算法:(本質是用隊列對BF算法做優化)
1.創建一個長度為n的dist數組，其中dist[i]表示從起點到i結點的最短路創建一個長度為n的bool數組st,其中st[i]表示i點是否已經在隊列中
2.初始化:標記dist[i]=0,同時1入隊；其余結點的dist值無窮大，表示還沒找到最短路
3.每次拿出隊頭元素u，去掉在隊列中的標記，同時對u所有相連的點v進行松弛操作如果結點v被松弛，那就放進隊列中
4.重復上述操作，直到隊列中沒有結點為止
例題:洛谷 P3385 【模板】負環1.BF判斷負環:執行n輪松弛操作，如果第n輪還存在松弛操作，那么就有負環2.spfa算法判斷負環:維護一個cnt數組記錄從起點到該點所經過的邊數，如果cnt[i]>=m，說明有負環
單源路算法總結:（n為結點個數，m為邊數)
1.dijkstra算法:時間復雜度:O(n平方)
2.堆優化的dijkstra算法: 時間復雜度:O（m*logm，m為邊數）
沒有負邊權的話用這倆
有負邊權就用BF算法和spfa算法
3.BF算法：時間復雜度:nm
4.spfa算法:時間復雜度:km~nm(k要具體題去分析)
5.普通BFS：處理邊權全部相同并且非負的單源最短路
6.01BFS：處理邊權要么為0，要么為1的單元最短路
問最短路有幾條的問題:
例題: 洛谷 P1144 最短路計數
1.這里的松弛操作和上面的有些不同:(要分情況了)dist[u]+w<dist[v]的話:f[v] = f[u]dist[u]+w=dist[v]的話f[v]+=f[u]
2.而且這里的BFS不能用st數組了，其他算法可以
一般做法使用dijkstra算法或者BFS（邊權相等才可BFS這個方法）+動態規劃
多源最短路
和搜索那里的多源最短路區分(那里是多個起點)
這里是分階段求最短路(加點求，加點求)–用floyd算法解決
floyd算法適用于任何圖，但是不能含負環
floyd算法:其本質是動態規劃。其實就是分階段，逐步更新出我們的最終結果
思路:
1.狀態表示:
f[k][i][j]表示:
僅僅經過[1,k]這些點，結點i走到結點j的最短路徑的長度
2.狀態轉移方程:
第一種情況，不選新來的點:f[k][i][j]=f[k-1][i][j]
第二種情況，選擇新來的點:f[k][i][j]=f[k-1][i][j]+f[k-1][i][j]
取這兩種的min
3.空間優化:可以優化掉第一維
4.初始化:
f[i][i]=0;
f[i][j]為初始狀態下i到j的距離，如果沒有邊則為無窮
5.填表順序:
一定要先枚舉j，再枚舉i和j例題: 洛谷 B3647 【模板】Floyd如果題目有限制加點的時機，那就把floyd算法里面的k那一層循環拆了改成判斷條件即可
例題: 洛谷 P1119 災后重建
無向圖的最小環問題:
例題:洛谷 P6175 ?向圖的最?環問題
floyd算法循環到k的時候，這個環的最小長度為f[i][j]+e[i][k]+e[k][j]核心部分:
for(int k =1;k<=n;k++)
{//最小環for(int i=1;i<k;i++)for(int j=i=1，j<k,j++)ret = min(ret,f[i][j]+e[i][k]+e[k][j]);//最短距離
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[i][j]=min(f[i][j],f[i][k]+f[k][j]);}
例題的跳轉鏈接匯總
洛谷 B3644 【模板】拓撲排序/家譜樹
洛谷 P3385 【模板】負環
洛谷 P1144 最短路計數
洛谷 B3647 【模板】Floyd
洛谷 P1119 災后重建
洛谷 P6175 ?向圖的最?環問題
＞)
