圖論的常用算法及應用

圖論的常用算法及應用基本概念和性質(zhì)1頂點集邊集鄰接與非鄰接點的度數(shù)完全圖與補圖同構基本概念和性質(zhì)2路徑v1,v2,…,vn開路回路真路環(huán)連接連通與非連通基本概念和性質(zhì)3割點割邊割邊連接的兩點是割點兩個割點之間的邊是割邊一個反例最短路徑路徑v1,v2,…,vn任意兩點的最短路徑長度小于n vi1,vi2,vi3,…,vimm>n任一環(huán)的長度不大于n其他一些圖多重圖偽圖有向圖帶權圖歐拉圖哈密頓圖平面圖圖的矩陣表示1圖的鄰接矩陣圖的矩陣表示2圖的鄰接向量矩陣圖的矩陣表示3圖的關聯(lián)矩陣例題1給出一張無向簡單圖的鄰接矩陣A以及正整數(shù)k，求任意兩點之間長度為k的路徑個數(shù)。例題1樣例K=5求從v1到v3長度為5的路徑個數(shù)例題1求解1利用圖的鄰接矩陣Ak(i,j)表示從i到j，長度為k的路徑個數(shù)例題1求解2遞推公式：例題1程序fork:=2to5dofori:=1tondoforj:=1tondoforl:=1tondoA[k,i,j]:=A[k,i,j]+A[k-1,i,l]*A[1,l,j];例題2判定圖的同構給出兩張圖的鄰接矩陣，判斷他們是否同構例題2樣例例題2解法1建立一一映射將圖1的頂點與圖2的頂點進行映射一個一維數(shù)組mm[i]表示圖1中的頂點i映射到圖2中的頂點m[i]例題2程序1varA,B:array[1..10,1..10]ofinteger;m:array[1..10]ofinteger;n:integer;例題2程序2functionjudge:boolean;vari,j:integer;beginjudge:=false;fori:=1tondoforj:=1tondoifA[i,j]<>B[m[i],m[j]]thenexit;judge:=true;end;例題2解法2如何產(chǎn)生這樣的一一映射呢？如何產(chǎn)生排列？例題2循環(huán)法form[1]:=1to4doform[2]:=1to4doifm[1]<>m[2]thenform[3]:=1to4doif(m[3]<>m[2])and(m[3]<>m[1])thenform[4]:=1to4doif(m[4]<>m[3])and(m[4]<>m[2])and(m[4]<>m[1])then調(diào)用judge且判斷;例題2用遞歸法模擬循環(huán)變量定義：var

m:array[1..10]ofinteger;used:array[1..10]ofinteger;n:integer;例題2遞歸子程序procedurework(d:integer);vari:integer;beginfori:=1tondoifused[i]=0thenbeginused[i]:=1;m[d]:=i;work(d+1);used[i]:=0;end;end;例題2遞歸終止條件ifd=n+1thenbegin

調(diào)用judge判斷;

exit;end;例題3最短路徑給出一張有向帶權圖以及兩個頂點a,b求從a到b的最短路徑長度數(shù)據(jù)規(guī)模：1000個頂點給出2000條邊的三元組形式例題3最短路徑算法迪卡斯特拉算法（標號法）適用范圍，算法復雜度Floyd–Warshall算法適用范圍，算法復雜度Bellman–Ford算法適用范圍，算法復雜度Bellman–Ford程序解答1變量定義constoo=15000;vars,e,l:array[1..2000]ofinteger;dist:array[1..1000]ofinteger;a,b,i,j,k,n,m:integer;Bellman–Ford程序解答2

fori:=1tondodist[i]:=oo;dist[a]:=0;fori:=1ton-1doforj:=1tomdoifdist[s[j]]+l[j]<dist[e[j]]thendist[e[j]]:=dist[s[j]]+l[j];Bellman–Ford思考題如何進一步提高算法的效率如何判斷一個圖存在負圈應用舉例兩個基本算法深度優(yōu)先搜索（DepthFirstSearch）廣度優(yōu)先搜索（BreadthFirstSearch）深度優(yōu)先搜索特點復雜度算法和數(shù)據(jù)結構的實現(xiàn)應用深度優(yōu)先搜索的搜索順序深度優(yōu)先搜索算法程序varn:integer;visited:array[1..100]ofinteger;data:array[1..100,1..100]ofinteger;深度優(yōu)先搜索算法程序proceduredfs(which:integer);vari:integer;beginvisited[which]:=1;fori:=1tondoif(visited[i]=0)and(data[which][i])thendfs(i);end;廣度優(yōu)先搜索特點復雜度算法和數(shù)據(jù)結構的實現(xiàn)應用廣度優(yōu)先搜索的搜索順序廣度優(yōu)先搜索算法程序varn:integer;visited:array[1..100]ofinteger;data:array[1..100,1..100]ofinteger;queue:array[1..100]ofinteger;qh,ql:integer;廣度優(yōu)先搜索算法程序1procedurebfs(which:integer);vari:integer;beginqueue[1]:=which;ql:=1;qh:=1;visited[which]:=1;

廣度優(yōu)先搜索算法程序2whileqh<=qldobeginfori:=1tondoif(visited[i]=0)and(data[queue[qh]][i])thenbegininc(ql);queue[ql]:=i;visited[i]:=1;end;inc(qh);end;end;例題4給出一張無向簡單圖，求此圖的割點經(jīng)典做法簡單做法例題4經(jīng)典做法使用深度優(yōu)先搜索在搜索過程中計算每個頂點的兩個值dfn

和low如何計算例題4簡單做法1刪除某個節(jié)點判斷是否仍然連通例題4簡單做法2問題的轉(zhuǎn)換1.是否真的需要刪除節(jié)點？2.是否真的需要求出所有連通分量？例題4簡單做法3問題的答案1.否，只要將visited數(shù)組初始賦12.否，只要dfs一個分量例題4解答程序functionjudge(which:integer):booleanvari:integer;beginfori:=1tondovisited[i]:=0;vi