清北NOIP訓(xùn)練營(yíng)集訓(xùn)筆記——圖論（提高組精英班）

本文摘自清北學(xué)堂內(nèi)部圖論筆記，作者為潘愷璠，來(lái)自柳鐵一中曾參加過(guò)清北訓(xùn)練營(yíng)提高組精英班，筆記非常詳細(xì)，特分享給大家！更多信息學(xué)資源關(guān)注微信訂閱號(hào)noipnoi。

最短路徑：

1.Floyd算法（插點(diǎn)法）：

通過(guò)一個(gè)圖的權(quán)值矩陣求出它的每?jī)牲c(diǎn)間的最短路徑（多源最短路）。

算法描述：

一個(gè)十分暴力又經(jīng)典的DP，假設(shè)i到j(luò)的路徑有兩種狀態(tài)：

①i和j直接有路徑相連：

②i和j間接聯(lián)通，中間有k號(hào)節(jié)點(diǎn)聯(lián)通：

假設(shè)dis[i][j]表示從i到j(luò)的最短路徑，對(duì)于存在的每個(gè)節(jié)點(diǎn)k，我們檢查一遍dis[i][k]+dis[k][j]。

?

//Floyd算法，時(shí)間復(fù)雜度：O(n^3)?

//Floyd算法，時(shí)間復(fù)雜度：O(n^3)?

int dis[MAXN][MAXN];

for(k=1;k<=n;k++)//枚舉?

{

? ? for(i=1;i<=n;i++)

? ? {

? ? ? ? for(j=1;j<=n;j++)

? ? ? ? {

? ? ? ? ? ? dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);//DP

? ? ? ? }

? ? }

}

【清北2019NOIP夏令營(yíng)助你圓夢(mèng)OI】

2.Dijkstra算法（無(wú)向圖，無(wú)負(fù)權(quán)邊）：

算法描述：

多源最短路！

a.初始時(shí)，S只包含源點(diǎn)，即S＝{v}，v的距離為0。U包含除v外的其他頂點(diǎn)，即:U={其余頂點(diǎn)}，若v與U中頂點(diǎn)u有邊，則<u,v>正常有權(quán)值，若u不是v的出邊鄰接點(diǎn)，則<u,v>權(quán)值為∞。

b.從U中選取一個(gè)距離v最小的頂點(diǎn)k，把k，加入S中（該選定的距離就是v到k的最短路徑長(zhǎng)度）。

c.以k為新考慮的中間點(diǎn)，修改U中各頂點(diǎn)的距離；若從源點(diǎn)v到頂點(diǎn)u的距離（經(jīng)過(guò)頂點(diǎn)k）比原來(lái)距離（不經(jīng)過(guò)頂點(diǎn)k）短，則修改頂點(diǎn)u的距離值，修改后的距離值的頂點(diǎn)k的距離加上邊上的權(quán)。

d.重復(fù)步驟b和c直到所有頂點(diǎn)都包含在S中。

啊~上面的的亂七八糟的概念太難懂了，還是舉個(gè)例子吧！如下圖！

?

我們假設(shè)1號(hào)節(jié)點(diǎn)為原點(diǎn)。

第一輪，我們可以算出2,3,4,5,6號(hào)節(jié)點(diǎn)到原點(diǎn)1的距離為[7,9,∞,∞,14]，∞表示無(wú)窮大（節(jié)點(diǎn)間無(wú)法直接連通），取其中最小的7，就確定了1->1的最短路徑為0，1->2的最短路徑為7，同時(shí)取最短路徑最小的2節(jié)點(diǎn)為下一輪的前驅(qū)節(jié)點(diǎn)。

第二輪，取2節(jié)點(diǎn)為前驅(qū)節(jié)點(diǎn)，按照 前驅(qū)節(jié)點(diǎn)到原點(diǎn)的最短距離 + 新節(jié)點(diǎn)到前驅(qū)節(jié)點(diǎn)的距離 來(lái)計(jì)算新的最短距離，可以得到3,4,5,6號(hào)節(jié)點(diǎn)到原點(diǎn)1的距離為[17,22,∞,∞]（新節(jié)點(diǎn)必須經(jīng)過(guò)2號(hào)節(jié)點(diǎn)回到原點(diǎn)），這時(shí)候需要將新結(jié)果和上一輪計(jì)算的結(jié)果比較，3號(hào)節(jié)點(diǎn)：17>9，最短路徑仍然為9；4號(hào)節(jié)點(diǎn)：22<∞，更新4號(hào)節(jié)點(diǎn)的最短路徑為22,；5號(hào)節(jié)點(diǎn)：仍然不變?yōu)椤?#xff1b;6號(hào)節(jié)點(diǎn)：14<∞，更新6號(hào)節(jié)點(diǎn)的最短路徑為14。得到本輪的最短距離為[9,22,∞,14]，1->3的最短路徑為9，同時(shí)取最短路徑最小的3節(jié)點(diǎn)為下一輪的前驅(qū)節(jié)點(diǎn)。

第三輪：同理上，以3號(hào)節(jié)點(diǎn)為前驅(qū)節(jié)點(diǎn)，可以得到4,5,6號(hào)節(jié)點(diǎn)到原點(diǎn)1的距離為[20,∞,11]，根據(jù)最短路徑原則，和上一輪最短距離比較，刷新為[20,∞,11]，1->3->6的最短路徑為11，同時(shí)取最短路徑最小的6節(jié)點(diǎn)為下一輪的前驅(qū)節(jié)點(diǎn)。

第四輪：同理，得到4,5號(hào)節(jié)點(diǎn)最短距離為[20,20]，這兩個(gè)值相等，運(yùn)算結(jié)束，到達(dá)這兩個(gè)點(diǎn)的最短距離都是20，如果這兩個(gè)值不相等，還要進(jìn)行第五輪運(yùn)算！

#include<cstdio>

#include<cstring>

const int N=100500;

const int M=200500;

int point[N]={0},to[M]={0},next[M]={0},len[M]={0},cc=0;

int dis[N];//最短路長(zhǎng)度，dis[i]表示第i號(hào)點(diǎn)到源點(diǎn)（1號(hào)點(diǎn)）的最短距離

bool ever[N];//當(dāng)前節(jié)點(diǎn)最短路有沒(méi)有確定?

int n,m;?

void AddEdge(int x,int y,int z)//添加新的邊和節(jié)點(diǎn)：x到y(tǒng)邊長(zhǎng)z

{

? ? cc++;

? ? next[cc]=point[x];

? ? point[x]=cc;

? ? to[cc]=y;

? ? len[cc]=z;//len記錄x到y(tǒng)的邊長(zhǎng)?

}

int main()

{

? ? int i,j,k;

? ? scanf("%d%d",&n,&m);

? ? for(i=1;i<=m;i++)

? ? {

? ? ? ? int a,b,c;

? ? ? ? scanf("%d%d%d",&a,&b,&c);

? ? ? ? AddEdge(a,b,c);//無(wú)向圖，要加兩遍?

? ? ? ? AddEdge(b,a,c);

? ? }

? ? memset(dis,0x3f,sizeof dis);//用極大值來(lái)初始化?

? ? dis[1]=0;//1號(hào)節(jié)點(diǎn)到自己最短距離為0?

? ? for(k=1;k<=n;k++)

? ? {

? ? ? ? int minp,minz=123456789;

? ? ? ? for(i=1;i<=n;i++)

? ? ? ? {

? ? ? ? ? ? if(!ever[i])

? ? ? ? ? ? {

? ? ? ? ? ? ? ? if(dis[i]<minz)

? ? ? ? ? ? ? ? {

? ? ? ? ? ? ? ? ? ? minz=dis[i];

? ? ? ? ? ? ? ? ? ? minp=i;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? ever[minp]=1;

? ? ? ? int now=point[minp];

? ? ? ? while(now)

? ? ? ? {

? ? ? ? ? ? int tox=to[now];

? ? ? ? ? ? if(dis[tox]>dis[minp]+len[now])

? ? ? ? ? ? dis[tox]=dis[minp]+len[now];

? ? ? ? ? ? now=next[now];

? ? ? ? }

? ? }

? ? for(i=1;i<=n;i++)

? ? ? ? printf("%d\n",dis[i]);

return 0;

【清北2019NOIP夏令營(yíng)與你相隨OI之路】

?

3.SPFA算法（有負(fù)權(quán)邊，無(wú)負(fù)圈，能檢測(cè)負(fù)圈但不能輸出）：

多源最短路！

SPFA和Dijkstra極為相似，只是加了個(gè)隊(duì)列優(yōu)化來(lái)檢測(cè)負(fù)圈和負(fù)權(quán)邊。

算法描述：

建立一個(gè)隊(duì)列，初始時(shí)隊(duì)列里只有起始點(diǎn)，再建立一個(gè)表格記錄起始點(diǎn)到所有點(diǎn)的最短路徑（該表格的初始值要賦為極大值，該點(diǎn)到他本身的路徑賦為0）。然后執(zhí)行松弛操作，用隊(duì)列里有的點(diǎn)作為起始點(diǎn)去刷新到所有點(diǎn)的最短路，如果刷新成功且被刷新點(diǎn)不在隊(duì)列中則把該點(diǎn)加入到隊(duì)列最后。重復(fù)執(zhí)行直到隊(duì)列為空。

判斷有無(wú)負(fù)環(huán)：
如果某個(gè)點(diǎn)進(jìn)入隊(duì)列的次數(shù)超過(guò)N次則存在負(fù)環(huán)（SPFA無(wú)法處理帶負(fù)環(huán)的圖）

#include<cstdio>

#include<cstring>

const int N=100500;

const int M=200500;

int point[N]={0},to[M]={0},next[M]={0},len[M]={0},cc=0;

int dis[N];//最短路長(zhǎng)度

int queue[N],top,tail;//雙向隊(duì)列queue，隊(duì)頭，隊(duì)尾?

bool in[N];//記錄這個(gè)點(diǎn)在不在隊(duì)列中，1表示在，0表示不在?

int n,m; //n個(gè)節(jié)點(diǎn)，m條邊?

void AddEdge(int x,int y,int z)//x到y(tǒng)邊長(zhǎng)為z?

{

? ? cc++;

? ? next[cc]=point[x];

? ? point[x]=cc;

? ? to[cc]=y;

? ? len[cc]=z;

}

int main()

{

? ? int i,j;

? ? scanf("%d%d",&n,&m);

? ? for(i=1;i<=m;i++)

? ? {

? ? ? ? int a,b,c;

? ? ? ? scanf("%d%d%d",&a,&b,&c);

? ? ? ? AddEdge(a,b,c);//因?yàn)槭请p向隊(duì)列，左邊加一次，右邊加一次

? ? ? ? AddEdge(b,a,c);

? ? }

? ? memset(dis,0x3f,sizeof dis);//用極大值來(lái)初始化

? ? dis[1]=0;//1號(hào)節(jié)點(diǎn)到自己最短距離為0?

? ? top=0;tail=1;queue[1]=1;in[1]=1;//初始化，只有原點(diǎn)加入?

? ? while(top!=tail)

? ? {

? ? ? ? top++;

? ? ? ? top%=N;

? ? ? ? int now=queue[top];

? ? ? ? in[now]=0;

? ? ? ? int ed=point[now];

? ? ? ? while(ed)

? ? ? ? {

? ? ? ? ? ? int tox=to[ed];

? ? ? ? ? ? if(dis[tox]>dis[now]+len[ed])

? ? ? ? ? ? {

? ? ? ? ? ? ? ? dis[tox]=dis[now]+len[ed];

? ? ? ? ? ? ? ? if(!in[tox])

? ? ? ? ? ? ? ? {

? ? ? ? ? ? ? ? ? ? tail++;

? ? ? ? ? ? ? ? ? ? tail%=N;

? ? ? ? ? ? ? ? ? ? queue[tail]=tox;

? ? ? ? ? ? ? ? ? ? in[tox]=1;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? ? ? ed=next[ed];

? ? ? ? }

? ? }

? ? for(i=1;i<=n;i++)

? ? ? ? printf("%d\n",dis[i]);

? ? return 0;?

}

4.Bellman Ford算法（有負(fù)權(quán)邊，可能有負(fù)圈，能檢測(cè)負(fù)圈并輸出）：

單源最短路！

算法描述：

1.初始化：將除源點(diǎn)外的所有頂點(diǎn)的最短距離估計(jì)值 d[all]=+∞, d[start]=0;

2.迭代求解：反復(fù)對(duì)邊集E中的每條邊進(jìn)行松弛操作，使得頂點(diǎn)集V中的每個(gè)頂點(diǎn)v的最短距離估計(jì)值逐步逼近其最短距離；（運(yùn)行|v|-1次）

3.檢驗(yàn)負(fù)權(quán)回路：判斷邊集E中的每一條邊的兩個(gè)端點(diǎn)是否收斂。如果存在未收斂的頂點(diǎn)，則算法返回false，表明問(wèn)題無(wú)解；否則算法返回true，并且從源點(diǎn)可達(dá)的頂點(diǎn)v的最短距離保存在 d[v]中。

簡(jiǎn)單的說(shuō)，如下圖所示：

?

松弛計(jì)算之前，點(diǎn)B的值是8，但是點(diǎn)A的值加上邊上的權(quán)重2，得到5，比點(diǎn)B的值（8）小，所以，點(diǎn)B的值減小為5。這個(gè)過(guò)程的意義是，找到了一條通向B點(diǎn)更短的路線，且該路線是先經(jīng)過(guò)點(diǎn)A，然后通過(guò)權(quán)重為2的邊，到達(dá)點(diǎn)B

如果出現(xiàn)了以下情況：

?

松弛操作后，變?yōu)?,7>6，這樣就不修改（Bellman Frod算法的高妙之處就在這），保留原來(lái)的最短路徑就OK，代碼實(shí)現(xiàn)起來(lái)非常簡(jiǎn)單。

int n,m;//n個(gè)點(diǎn)，m條邊?

struct Edge//定義圖類型結(jié)構(gòu)體?

{

? ? int a,b,c;//a到b長(zhǎng)度為c?

}edge[];

int dis[];

memset(dis,0x3f,sizeof dis);

dis[1]=0;

for(int i=1;i<n;i++)

{

? ? for(int j=1;j<=m;j++)

? ? {

? ? ? ? if(dis[edge[j].b]>dis[edge[j].a]+edge[j].c)

? ? ? ? {

? ? ? ? ? ? dis[edge[j].b]=dis[edge[j].a]+edge[j].c;? ? ? ??

? ? ? ? }

? ? }

}

5.A*算法：

這玩意兒我是沒(méi)看懂，等以后我看懂了再更吧（無(wú)奈臉）~

七、拓?fù)渑判?#xff1a;

對(duì)一個(gè)有向無(wú)環(huán)圖(Directed Acyclic Graph簡(jiǎn)稱DAG)G進(jìn)行拓?fù)渑判?#xff0c;是將G中所有頂點(diǎn)排成一個(gè)線性序列，使得圖中任意一對(duì)頂點(diǎn)u和v，若邊(u,v)∈E(G)，則u在線性序列中出現(xiàn)在v之前。通常，這樣的線性序列稱為滿足拓?fù)浯涡?Topological Order)的序列，簡(jiǎn)稱拓?fù)湫蛄小?/p>

打個(gè)比喻：我們要做好一盤(pán)菜名字叫做紅燒茄子，那么第一步得買(mǎi)茄子和配料，第二步就是要洗茄子，第三步就是要開(kāi)始倒油進(jìn)鍋里啊什么七七八八的，第四步…，你不可能先洗茄子再買(mǎi)茄子和配料，這樣的一些事件必須是按照順序進(jìn)行的，這些依次進(jìn)行的事件就構(gòu)成了一個(gè)拓?fù)湫蛄小?/p>

算法描述：

我們需要一個(gè)棧或者隊(duì)列，兩者都可以無(wú)所謂，只是找個(gè)容器把入度為0的元素維護(hù)起來(lái)而已。

①?gòu)挠邢驁D中選擇一個(gè)入度為0（無(wú)前驅(qū)）的頂點(diǎn)，輸出它。

②從網(wǎng)中刪去該節(jié)點(diǎn)，并且刪去從該節(jié)點(diǎn)出發(fā)的所有有向邊。

③重復(fù)以上兩步，直到剩余的網(wǎng)中不再存在沒(méi)有前驅(qū)的節(jié)點(diǎn)為止。

具體操作過(guò)程如下：

若棧非空，則在棧中彈出一個(gè)元素，然后枚舉這個(gè)點(diǎn)能到的每一個(gè)點(diǎn)將它的入度-1（刪去一條邊），如果入度=0，則壓入棧中。?
如果沒(méi)有輸出所有的頂點(diǎn)，則有向圖中一定存在環(huán)

//拓?fù)渑判?#xff0c;時(shí)間復(fù)雜度：O(n+m)?

#include<cstdio>

#include<cstring>

const int N=100500;

const int M=200500;

int point[N]={0},to[M]={0},next[M]={0},cc=0;

int xu[N]={0};//棧，初始值為空，xu[0]表示棧的大小?

int in[N]={0};//入度，a可以到達(dá)b，in[b]++?

int ans[N]={0};//ans[0]整個(gè)拓?fù)湫蛄械拇笮?

int n,m;?

void AddEdge(int x,int y)//鄰接表a到b?

{

? ? cc++;

? ? next[cc]=point[x];

? ? point[x]=cc;

? ? to[cc]=y;

}

int main()

{

? ? int i,j;

? ? scanf("%d%d",&n,&m);

? ? for(i=1;i<=m;i++)

? ? {

? ? ? ? int a,b;

? ? ? ? scanf("%d%d",&a,&b);

? ? ? ? in[b]++;//統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的入度?

? ? ? ? AddEdge(a,b);

? ? }

? ? for(i=1;i<=n;i++)

? ? {

? ? ? ? if(in[i]==0)//這個(gè)節(jié)點(diǎn)入度為0，壓入棧?

? ? ? ? xu[++xu[0]]=i;

? ? }

? ? while(xu[0])

? ? {

? ? ? ? int now=xu[xu[0]];//出棧?

? ? ? ? xu[0]--;

? ? ? ? ans[++ans[0]]=now;

? ? ? ? int ed=point[now];

? ? ? ? while(ed)

? ? ? ? {

? ? ? ? ? ? int tox=to[ed];

? ? ? ? ? ? in[tox]--;

? ? ? ? ? ? if(!in[tox])

? ? ? ? ? ? xu[++xu[0]]=tox;

? ? ? ? ? ? ed=next[ed];//找下一個(gè)相鄰節(jié)點(diǎn)?

? ? ? ? }

? ? }

? ? if(ans[0]<n)//有向圖中一定存在環(huán)，無(wú)結(jié)果?

? ? printf("no solution");

? ? else

? ? {

? ? ? ? for(i=1;i<=n;i++)

? ? ? ? printf("%d ",ans[i]);

? ? }

? ? return 0;

}

?

?

聯(lián)通分量：

強(qiáng)連通：有向圖中，從a能到b并且從b可以到a，那么a和b強(qiáng)連通。

強(qiáng)連通圖：有向圖中，任意一對(duì)點(diǎn)都滿足強(qiáng)連通，則這個(gè)圖被稱為強(qiáng)連通圖。

強(qiáng)聯(lián)通分量：有向圖中的極大強(qiáng)連通子圖，就是強(qiáng)連通分量。

一般用Tarjan算法求有向圖強(qiáng)連通分量：

?

歐拉路徑與哈密頓路徑：

1.歐拉路徑：從某點(diǎn)出發(fā)一筆畫(huà)遍歷每一條邊形成的路徑。

歐拉回路：在歐拉路徑的基礎(chǔ)上回到起點(diǎn)的路徑（從起點(diǎn)出發(fā)一筆畫(huà)遍歷每一條邊）。

歐拉路徑存在：

無(wú)向圖：當(dāng)且僅當(dāng)該圖所有頂點(diǎn)的度數(shù)為偶數(shù) 或者 除了兩個(gè)度數(shù)為奇數(shù)外其余的全是偶數(shù)。

有向圖：當(dāng)且僅當(dāng)該圖所有頂點(diǎn) 出度=入度 或者 一個(gè)頂點(diǎn) 出度=入度+1，另一個(gè)頂點(diǎn) 入度=出度+1，其他頂點(diǎn) 出度=入度

歐拉回路存在：

無(wú)向圖：每個(gè)頂點(diǎn)的度數(shù)都是偶數(shù)，則存在歐拉回路。

有向圖：每個(gè)頂點(diǎn)的入度都等于出度，則存在歐拉回路。

求歐拉路徑/歐拉回路算法常常用Fleury算法：

在這里推薦一個(gè)不錯(cuò)的知乎作者:神秘OIer

2.哈密頓路徑：每個(gè)點(diǎn)恰好經(jīng)過(guò)一次的路徑是哈密頓路徑。

哈密頓回路：起點(diǎn)與終點(diǎn)之間有邊相連的哈密頓路徑是哈密頓回路。

?

轉(zhuǎn)載于:https://www.cnblogs.com/qbxt/p/10981407.html

總結(jié)

以上是生活随笔為你收集整理的清北NOIP训练营集训笔记——图论（提高组精英班）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。