圖算法之個(gè)人整理總結(jié)

《圖算法之個(gè)人整理總結(jié)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、陳江勇整理2021-7-15圖算法實(shí)例1.Dijkstra算法求最短路算法22.求所有點(diǎn)最短路的Dijkstra算法33.歐拉路徑44.最大的流85.有向圖的強(qiáng)連通分量和2-sat的判定問(wèn)題106.求圖中不含有割點(diǎn)（關(guān)結(jié)點(diǎn)）的塊187.圖的奇環(huán)的判斷,是否為二分圖的判斷198.二分圖的匹配209.prim算法求最小生成樹(shù)2010.給有有向圖最少加邊使圖中沒(méi)有橋2111.套匯問(wèn)題2412.差分系統(tǒng)2413.二分圖加權(quán)匹配--KM算法3214.floyed算法36第37頁(yè)陳江勇整理2021-7-151.Dij

2、kstra算法求最短路算法用堆來(lái)實(shí)現(xiàn)輸入輸出說(shuō)明：N,M然后M條邊即相應(yīng)的邊的長(zhǎng)22125214#include#include#include#includeusingnamespacestd;#defineINFINT_MAX#definemaxn30000structNODE{intv;intweight;};intwt[maxn],heap[maxn*2],r,N,M;//wt[i]保存從開(kāi)始節(jié)點(diǎn)到節(jié)點(diǎn)i的最短路，heap的

3、大小不確定boolvisit[maxn];//一般開(kāi)到節(jié)點(diǎn)數(shù)目?jī)傻饺?。這是因?yàn)槎阎袝?huì)有相同的節(jié)點(diǎn)，但他們的權(quán)重vectorG[maxn];//不一樣intcmp(inta,intb){returnwt[a]>wt[b];}intdijkstra(ints,intt){inti,u;for(i=0;i=0){u=heap[0];p

4、op_heap(heap,heap+r,cmp);第37頁(yè)陳江勇整理2021-7-15r--;if(visit[u]){continue;}visit[u]=1;if(u==t){returnwt[t];}for(i=0;i

5、;push_heap(heap,heap+r,cmp);}}}return-1;}intmain(){NODEtemp;inti,A,B,c;scanf("%d%d",&N,&M);for(i=0;i

6、ints){inti,u,j,min;第37頁(yè)陳江勇整理2021-7-15memset(visit,0,sizeof(visit));for(i=1;i<=F;i++){if(G[s][i])//存在著邊{dist[i]=G[s][i];}else{dist[i]=INT_MAX;}}dist[s]=0;visit[s]=1;for(i=1;i<=F;i++){u=-1;min=INT_MAX;for(j=1;j<=F;j++){if(dist[j]

7、;u=j;}}if(u==-1){break;}visit[u]=1;for(j=1;j<=F;j++){if(G[u][j]&&!visit[j]&&dist[j]>dist[u]+G[u][j]){dist[j]=dist[u]+G[u][j];}}}}1.歐拉路徑判斷歐拉路徑時(shí)要注意有向圖無(wú)圖的區(qū)別。第37頁(yè)陳江勇整理2021-7-15以下是鏈表形式structNODE{intv,id;NODE*next;};voidpath(intu,intid){linkp;intvv,dd;while(adj

8、[u]){p=adj[u];vv=p->v;dd=p->id;adj[u]=p->next;deletep;path(vv,dd);}ans[top++]=id;}注意這邊ans是反序存結(jié)果。SampleInput26alohaarachniddoggopherrattiger3oakmapleelmSampleOutputaloha.arachnid.dog.gopher.rat.tiger***#include