|
一、圖的存儲(chǔ)
1、鄰接矩陣
假設(shè)有n個(gè)節(jié)點(diǎn)，建立一個(gè)n×n的矩陣，第i號(hào)節(jié)點(diǎn)能到達(dá)第j號(hào)節(jié)點(diǎn)就將[i][j]標(biāo)記為1（有權(quán)值標(biāo)記為權(quán)值）， 樣例如下圖：
/*無(wú)向圖，無(wú)權(quán)值*/ int a[MAXN][MAXN];//鄰接矩陣 int x,y;//兩座城市 for(int i=1;i<> { for(intj=1;j<> { scanf('%d%d',&x,&y);//能到達(dá)，互相標(biāo)記為1 a[x][y]=1; a[y][x]=1; } } /*無(wú)向圖，有權(quán)值*/ int a[MAXN][MAXN];//鄰接矩陣 int x,y,w;//兩座城市，路徑長(zhǎng)度 for(int i=1;i<> { for(intj=1;j<> { scanf('%d%d%d',&x,&y,&w);//能到達(dá)，互相標(biāo)記為權(quán)值w a[x][y]=w; a[y][x]=w; } } /*有向圖，無(wú)權(quán)值*/ int a[MAXN][MAXN];//鄰接矩陣 int x,y;//兩座城市 for(int i=1;i<> { for(intj=1;j<> { scanf('%d%d',&x,&y);//能到達(dá)，僅僅是x到y標(biāo)記為1 a[x][y]=1; } } /*有向圖，有權(quán)值*/ int a[MAXN][MAXN];//鄰接矩陣 int x,y,w;//兩座城市，路徑長(zhǎng)度 for(int i=1;i<> { for(intj=1;j<> { scanf('%d%d%d',&x,&y,&w);//能到達(dá)，僅僅是x到y標(biāo)記為權(quán)值w a[x][y]=w; } }
鄰接矩陣很方便，但是在n過(guò)大或者為稀疏圖時(shí)，就會(huì)很損耗時(shí)空，不建議使用！
2.鄰接表
鄰接表是一個(gè)二維容器，第一維描述某個(gè)點(diǎn)，第二維描述這個(gè)點(diǎn)所對(duì)應(yīng)的邊集們。 鄰接表由表頭point，鏈點(diǎn)構(gòu)成，如下圖是一個(gè)簡(jiǎn)單無(wú)向圖構(gòu)成的鄰接表：
我們可以用指針來(lái)創(chuàng)建鏈表，當(dāng)然，這是很復(fù)雜也很麻煩的事情，下面來(lái)介紹一種用數(shù)組模擬鏈表的方法：
//有向圖鄰接表存儲(chǔ) const int N=1005; const int M=10050; int point[N]={0};//i節(jié)點(diǎn)所對(duì)應(yīng)鏈表起始位置（表頭） int to[M]={0}; int next[M]={0};//i節(jié)點(diǎn)下一個(gè)所指的節(jié)點(diǎn) int cc=0;//計(jì)數(shù)器（表示第幾條邊） void AddEdge(int x,int y)//節(jié)點(diǎn)x到y { cc++; to[cc]=y; next[cc]=point[x]; point[x]=cc; } void find(int x) { int now=point[x]; while(now) { printf('%d\n',to[now]); now=next[now]; } } int main() {
} 如果要加強(qiáng)記憶的話可以用我所給的例子模擬一下point[],to[],next[]，然后再調(diào)用函數(shù)find(x)來(lái)輸出x這個(gè)節(jié)點(diǎn)能到的點(diǎn)，大概就能YY到數(shù)組是怎么存儲(chǔ)鄰接表的了。 還是不理解的話，推一個(gè)blog，這里面說(shuō)的和我這里給出的思路很相似：http://developer.51cto.com/art/201404/435072.htm
二、樹(shù)的遍歷
1.BFS 運(yùn)用隊(duì)列，一開(kāi)始隊(duì)列中有一個(gè)點(diǎn)，將一個(gè)點(diǎn)出隊(duì)，將它的子結(jié)點(diǎn)全都入隊(duì)。 算法會(huì)在遍歷完一棵樹(shù)中每一層的每個(gè)結(jié)點(diǎn)之后，才會(huì)轉(zhuǎn)到下一層繼續(xù)，在這一基礎(chǔ)上，隊(duì)列將會(huì)對(duì)算法起到很大的幫助： //廣度優(yōu)先搜索 void BreadthFirstSearch(BitNode *root) { queue nodeQueue.push(root);//將根節(jié)點(diǎn)壓入隊(duì)列 while(!nodeQueue.empty())//隊(duì)列不為空，繼續(xù)壓入隊(duì)列 { BitNode *node =nodeQueue.front(); nodeQueue.pop();//彈出根節(jié)點(diǎn) if(node->left)//左兒子不為空 { nodeQueue.push(node->left);//壓入隊(duì)列 } if(node->right)//右兒子不為空 { nodeQueue.push(node->right);//壓入隊(duì)列 } } } 2.DFS 運(yùn)用棧，遞歸到一個(gè)點(diǎn)時(shí)，依次遞歸它的子結(jié)點(diǎn)。 還可以利用堆棧的先進(jìn)后出的特點(diǎn)，現(xiàn)將右子樹(shù)壓棧，再將左子樹(shù)壓棧，這樣左子樹(shù)就位于棧頂，可以保證結(jié)點(diǎn)的左子樹(shù)先與右子樹(shù)被遍歷： //深度優(yōu)先搜索 //利用棧，現(xiàn)將右子樹(shù)壓棧再將左子樹(shù)壓棧 void DepthFirstSearch(BitNode *root) { stack nodeStack.push(root);//將根節(jié)點(diǎn)壓棧 while(!nodeStack.empty())//棧不為空，繼續(xù)壓棧 { BitNode *node =nodeStack.top();//引用棧頂 cout nodeStack.pop();//彈出根節(jié)點(diǎn) if(node->right)//優(yōu)先遍歷右子樹(shù) { nodeStack.push(node->right); } if (node->left) { nodeStack.push(node->left); } } } 三、無(wú)根樹(shù)變成有根樹(shù)
選擇一個(gè)點(diǎn)作為根結(jié)點(diǎn)，開(kāi)始遍歷。 遍歷到一個(gè)點(diǎn)時(shí)，枚舉每一條連接它和另一個(gè)點(diǎn)的邊。若另一個(gè)點(diǎn)不是它的父結(jié)點(diǎn)，那就是它的子結(jié)點(diǎn)。遞歸到子結(jié)點(diǎn)。 我們可以更加形象的比喻為：抓住一個(gè)點(diǎn)，把它拎起來(lái)構(gòu)成一棵新的樹(shù)。
四、并查集
這是我學(xué)OI這么久以來(lái)覺(jué)得性?xún)r(jià)比最高的算法（簡(jiǎn)單又實(shí)用?。。。?/span>,用來(lái)處理不相交合并和查詢(xún)問(wèn)題。 給大家推個(gè)超超超超級(jí)易懂的blog，保證一看就懂，這里我就不再詳解了：http://blog.csdn.net/dellaserss/article/details/7724401
五、最小生成樹(shù)
1.Prim算法（適用于稠密圖） 算法描述： 1).輸入：一個(gè)加權(quán)連通圖，其中頂點(diǎn)集合為V，邊集合為E； 2).初始化：Vnew = {x}，其中x為集合V中的任一節(jié)點(diǎn)（起始點(diǎn)），Enew = {},為空； 3).重復(fù)下列操作，直到Vnew = V： a.在集合E中選取權(quán)值最小的邊 b.將v加入集合Vnew中，將 4).輸出：使用集合Vnew和Enew來(lái)描述所得到的最小生成樹(shù)。 #include const int N=1050; const int M=10050; struct Edge//定義圖類(lèi)型結(jié)構(gòu)體，a到b權(quán)值為c { int a,b,c; }edge[M]; int n,m;//n個(gè)點(diǎn)，m條邊 bool black[N];//染黑這個(gè)點(diǎn)，表示這個(gè)點(diǎn)已經(jīng)被選過(guò)了 int ans=0;//最小生成樹(shù)權(quán)值和 int main() { int i,j,k; scanf('%d%d',&n,&m); for(i=1;i<> scanf('%d%d%d',&edge[i].a,&edge[i].b,&edge[i].c); black[1]=1;//把第一個(gè)點(diǎn)染黑 for(k=1;k<> { intmind,minz=123456789; for(i=1;i<=m;i++)>開(kāi)始！ { if(black[edge[i].a]!=black[edge[i].b]&&edge[i].c<> { mind=i; minz=edge[i].c; } } ans+=minz; black[edge[mind].a]=1;//染黑兩個(gè)節(jié)點(diǎn) black[edge[mind].b]=1; } printf('%d\n',ans);//輸出答案 return 0; } 2.kruskal算法（適用于稀疏圖）
算法描述： 克魯斯卡爾算法從另一途徑求網(wǎng)的最小生成樹(shù)。 假設(shè)連通網(wǎng)N=（V，{E}），則令最小生成樹(shù)的初始狀態(tài)為只有n個(gè)頂點(diǎn)而無(wú)邊的非連通圖T=（V，{∮}），圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。 在E中選擇代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條代價(jià)最小的邊。 依次類(lèi)推，直至T中所有頂點(diǎn)都在同一連通分量上為止。
#include #include #include using namespace std; const int N=1050; const int M=10050; struct Edge//定義圖類(lèi)型結(jié)構(gòu)體 { int a,b,c;//a到b的權(quán)值為c }edge[M]; int fa[N];//父親數(shù)組 int n,m;//n個(gè)節(jié)點(diǎn)，m條邊 int ans=0;//最小生成樹(shù)權(quán)值和 bool cmp(Edge x,Edge y)//比較權(quán)值大小 { return (x.c<> } int getf(int x)//尋找x的最原始祖先（并查集） { if(fa[x]!=x) fa[x]=getf(fa[x]); return fa[x];//返回最原始祖先 } int main() { int i,j; scanf('%d%d',&n,&m); for(i=1;i<> scanf('%d%d%d',&edge[i].a,&edge[i].b,&edge[i].c); sort(edge+1,edge+m+1,cmp);//從小到大排序邊數(shù)組 for(i=1;i<> fa[i]=i;//初始值，每個(gè)節(jié)點(diǎn)的父親就是自己 for(i=1;i<> { int a=edge[i].a; int b=edge[i].b; a=getf(a);//尋找a的最原始祖先 b=getf(b);//尋找b的最原始祖先 if(a!=b)//如果兩個(gè)的最終祖先不相同（不會(huì)構(gòu)成回路） { ans+=edge[i].c;//加入 fa[a]=b;//加入當(dāng)前父親的兒子們中（合并并查集） } } printf('%d\n',ans); return 0; } 經(jīng)典例題：繁忙的都市（Luogu 2330） 城市C是一個(gè)非常繁忙的大都市，城市中的道路十分的擁擠，于是市長(zhǎng)決定對(duì)其中的道路進(jìn)行改造。城市C的道路是這樣分布的：城市中有n個(gè)交叉路口，有些交叉路口之間有道路相連，兩個(gè)交叉路口之間最多有一條道路相連接。這些道路是雙向的，且把所有的交叉路口直接或間接的連接起來(lái)了。每條道路都有一個(gè)分值，分值越小表示這個(gè)道路越繁忙，越需要進(jìn)行改造。但是市政府的資金有限，市長(zhǎng)希望進(jìn)行改造的道路越少越好，于是他提出下面的要求： 1．改造的那些道路能夠把所有的交叉路口直接或間接的連通起來(lái)。 2．在滿足要求1的情況下，改造的道路盡量少。 3．在滿足要求1、2的情況下，改造的那些道路中分值最大的道路分值盡量小。 任務(wù)：作為市規(guī)劃局的你，應(yīng)當(dāng)作出最佳的決策，選擇那些道路應(yīng)當(dāng)被修建。 這題是經(jīng)典的最小瓶頸生成樹(shù)問(wèn)題：只用邊權(quán)小于等于x的邊，看看能不能構(gòu)成最小生成樹(shù)。 在kruskal算法中，我們已經(jīng)對(duì)邊從小到大排過(guò)序了，所以只要用≤x的前若干條邊即可。
3.最小生成樹(shù)計(jì)數(shù)問(wèn)題
題目：現(xiàn)在給出了一個(gè)簡(jiǎn)單無(wú)向加權(quán)圖。你不滿足于求出這個(gè)圖的最小生成樹(shù)，而希望知道這個(gè)圖中有多少個(gè)不同的最小生成樹(shù)。（如果兩顆最小生成樹(shù)中至少有一條邊不同，則這兩個(gè)最小生成樹(shù)就是不同的）。 解法：按邊權(quán)排序，先選小的，相同邊權(quán)的暴力求出有幾種方案，將邊按照權(quán)值大小排序，將權(quán)值相同的邊分到一組，統(tǒng)計(jì)下每組分別用了多少條邊。然后對(duì)于每一組進(jìn)行dfs，判斷是否能夠用這一組中的其他邊達(dá)到相同的效果。最后把每一組的方案數(shù)相乘就是答案。 換句話說(shuō)：就是不同的最小生成樹(shù)方案，每種權(quán)值的邊的數(shù)量是確定的，每種權(quán)值的邊的作用是確定的, 排序以后先做一遍最小生成樹(shù)，得出每種權(quán)值的邊使用的數(shù)量x然后對(duì)于每一種權(quán)值的邊搜索，得出每一種權(quán)值的邊選擇方案。
#include #include #define N 105 #define M 1005 #define MOD 31011 using namespace std; struct node//定義圖類(lèi)型結(jié)構(gòu)體 { int a,b;//節(jié)點(diǎn)a，b int zhi;//a到b的權(quán)值 }xu[M]; int n,m; int fa[N]; int lian[N]; int ans=1; int cmp(struct node x,struct node y)//從小到大排序函數(shù) { return(x.zhi<> } int getf(int x) { if(fa[x]!=x) fa[x]=getf(fa[x]); return(fa[x]); } int getlian(int x) { if(lian[x]==x) return x; return (getlian(lian[x]) ); } int dfs(int now,int end,int last) { if(now==end) { if(last==0) return 1; return 0; } intres=dfs(now+1,end,last); ints=getlian(xu[now].a); intt=getlian(xu[now].b); if(s!=t) { lian[s]=t; res+=dfs(now+1,end,last-1); lian[s]=s; } return res; } int main() { int i,j,k; int s,t; int now; int sum=0; scanf('%d%d',&n,&m); for(i=1;i<=n;i++)>初始化，每個(gè)節(jié)點(diǎn)的父親就是自己 fa[i]=i; for(i=1;i<> scanf('%d%d%d',&xu[i].a,&xu[i].b,&xu[i].zhi); sort(xu+1,xu+m+1,cmp);//從小到大排序邊數(shù)組 for(i=1;i<> { for(j=1;j<> lian[j]=j; k=i; while(i<> { xu[i].a=getf(xu[i].a); xu[i].b=getf(xu[i].b); i++; } now=sum; for(j=k;j<> { s=getf(xu[j].a); t=getf(xu[j].b); if(s!=t) { sum++; fa[s]=t; } } ans*=dfs(k,i,sum-now); ans%=MOD;//防止溢出 } if(sum!=n-1) ans=0; printf('%d\n',ans); return 0; } 六、最短路徑
1.Floyd算法（插點(diǎn)法） 通過(guò)一個(gè)圖的權(quán)值矩陣求出它的每?jī)牲c(diǎn)間的最短路徑（多源最短路）。 算法描述： 一個(gè)十分暴力又經(jīng)典的DP，假設(shè)i到j的路徑有兩種狀態(tài)： ①i和j直接有路徑相連： ②i和j間接聯(lián)通，中間有k號(hào)節(jié)點(diǎn)聯(lián)通： 假設(shè)dis[i][j]表示從i到j的最短路徑，對(duì)于存在的每個(gè)節(jié)點(diǎn)k，我們檢查一遍dis[i][k]+dis[k][j]。 //Floyd算法，時(shí)間復(fù)雜度：O(n^3) int dis[MAXN][MAXN]; for(k=1;k<=n;k++)> { for(i=1;i<> { for(j=1;j<> { dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);//DP } } }
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有邊，則 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)?/span>∞；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 #include 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)度 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邊長(zhǎng)z { cc++; next[cc]=point[x]; point[x]=cc; to[cc]=y; len[cc]=z;//len記錄x到y的邊長(zhǎng) } int main() { int i,j,k; scanf('%d%d',&n,&m); for(i=1;i<> { int a,b,c; scanf('%d%d%d',&a,&b,&c); AddEdge(a,b,c);//無(wú)向圖，要加兩遍 AddEdge(b,a,c); } memset(dis,0x3f,sizeofdis);//用極大值來(lái)初始化 dis[1]=0;//1號(hào)節(jié)點(diǎn)到自己最短距離為0 for(k=1;k<> { intminp,minz=123456789; for(i=1;i<> { if(!ever[i]) { if(dis[i]<> { minz=dis[i]; minp=i; } } } ever[minp]=1; intnow=point[minp]; while(now) { inttox=to[now]; if(dis[tox]>dis[minp]+len[now]) dis[tox]=dis[minp]+len[now]; now=next[now]; } } for(i=1;i<> printf('%d\n',dis[i]); return 0; } 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 #include 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邊長(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<> { 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,sizeofdis);//用極大值來(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; intnow=queue[top]; in[now]=0; int ed=point[now]; while(ed) { inttox=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<> printf('%d\n',dis[i]); return 0; } 4.BellmanFord算法（有負(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)?/span>7,7>6，這樣就不修改（Bellman Frod算法的高妙之處就在這），保留原來(lái)的最短路徑就OK，代碼實(shí)現(xiàn)起來(lái)非常簡(jiǎn)單。
int n,m;//n個(gè)點(diǎn)，m條邊 struct Edge//定義圖類(lèi)型結(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<> { for(intj=1;j<> { if(dis[edge[j].b]>dis[edge[j].a]+edge[j].c) { dis[edge[j].b]=dis[edge[j].a]+edge[j].c; } } }
七、拓?fù)渑判?/span>
對(duì)一個(gè)有向無(wú)環(huán)圖(Directed Acyclic Graph簡(jiǎn)稱(chēng)DAG)G進(jìn)行拓?fù)渑判?，是?/span>G中所有頂點(diǎn)排成一個(gè)線性序列，使得圖中任意一對(duì)頂點(diǎn)u和v，若邊(u,v)∈E(G)，則u在線性序列中出現(xiàn)在v之前。通常，這樣的線性序列稱(chēng)為滿足拓?fù)浯涡?/span>(Topological Order)的序列，簡(jiǎn)稱(chēng)拓?fù)湫蛄小?/span> 打個(gè)比喻：我們要做好一盤(pán)菜名字叫做紅燒茄子，那么第一步得買(mǎi)茄子和配料，第二步就是要洗茄子，第三步就是要開(kāi)始倒油進(jìn)鍋里啊什么七七八八的，第四步…，你不可能先洗茄子再買(mǎi)茄子和配料，這樣的一些事件必須是按照順序進(jìn)行的，這些依次進(jìn)行的事件就構(gòu)成了一個(gè)拓?fù)湫蛄小?/span>
算法描述： 我們需要一個(gè)棧或者隊(duì)列，兩者都可以無(wú)所謂，只是找個(gè)容器把入度為0的元素維護(hù)起來(lái)而已。 ①從有向圖中選擇一個(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ù)渑判颍瑫r(shí)間復(fù)雜度：O(n+m) #include #include 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ù)湫蛄械拇笮?/span> 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<> { int a,b; scanf('%d%d',&a,&b); in[b]++;//統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的入度 AddEdge(a,b); } for(i=1;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) { inttox=to[ed]; in[tox]--; if(!in[tox]) xu[++xu[0]]=tox; ed=next[ed];//找下一個(gè)相鄰節(jié)點(diǎn) } } if(ans[0] printf('nosolution'); else { for(i=1;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è)圖被稱(chēng)為強(qiáng)連通圖。 強(qiáng)聯(lián)通分量：有向圖中的極大強(qiáng)連通子圖，就是強(qiáng)連通分量。 一般用Tarjan算法求有向圖強(qiáng)連通分量： 推一個(gè)蠻容易理解的blog：http://www.cnblogs.com/uncle-lu/p/5876729.html
九、歐拉路徑與哈密頓路徑
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è)蠻容易理解的blog：http://www.cnblogs.com/Lyush/archive/2013/04/22/3036659.html
2.哈密頓路徑：每個(gè)點(diǎn)恰好經(jīng)過(guò)一次的路徑是哈密頓路徑。 哈密頓回路：起點(diǎn)與終點(diǎn)之間有邊相連的哈密頓路徑是哈密頓回路。 |
|
|
來(lái)自： 長(zhǎng)沙7喜 > 《信息課》
