數(shù)據(jù)結(jié)構(gòu)第七章圖

第七章圖(Graph)邏輯結(jié)構(gòu)與基本運(yùn)算1圖的存儲(chǔ)結(jié)構(gòu)2圖的遍歷3網(wǎng)的最短路徑4madebyXiong’enLiuSchoolofComputer&InformationScience,FAFU最小生成樹(shù)5有向無(wú)環(huán)圖及其應(yīng)用6【例1.3】鐵路客運(yùn)線路與站點(diǎn)

問(wèn)題1：如何存儲(chǔ)線路圖和站點(diǎn)信息？如何確定兩點(diǎn)間的最短路徑？1邏輯結(jié)構(gòu)與基本運(yùn)算

1.1定義與邏輯結(jié)構(gòu) 頂點(diǎn)：圖中某個(gè)數(shù)據(jù)元素 圖：頂點(diǎn)有窮非空集合和頂點(diǎn)間關(guān)系集合的二元組1.3圖的術(shù)語(yǔ)

邊：兩個(gè)頂點(diǎn)之間的一個(gè)雙向?qū)ΨQ關(guān)系 ?。簝蓚€(gè)頂點(diǎn)之間的一個(gè)單向關(guān)系 弧尾：依附于弧上的出發(fā)（初始）頂點(diǎn) 弧頭：依附于弧上的到達(dá)（終端）頂點(diǎn) 無(wú)向圖：由頂點(diǎn)和邊組成的圖 有向圖：由頂點(diǎn)和弧組成的圖問(wèn)題2：n個(gè)頂點(diǎn)的無(wú)向圖的邊至多是多少？無(wú)向完全圖：n個(gè)頂點(diǎn)的無(wú)向圖具有n(n-1)/2條邊有向完全圖：n個(gè)頂點(diǎn)的有向圖具有n(n-1)條弧稀疏圖：邊或弧的數(shù)量e<nlog2n稠密圖：邊或弧的數(shù)量e≥nlog2n子圖：由圖的部分頂點(diǎn)和邊或弧組成的圖邊或弧的權(quán)：量化的邊或弧的關(guān)系網(wǎng)：帶權(quán)的圖鄰接點(diǎn)：相對(duì)于某一頂點(diǎn)，依附于同一條邊的另一頂點(diǎn)； 或相對(duì)于弧尾，依附于同一條弧的弧頭逆鄰接點(diǎn)：相對(duì)于弧頭，依附于同一條弧的弧尾頂點(diǎn)的度：其鄰接點(diǎn)和逆鄰接點(diǎn)的個(gè)數(shù)，記作TD(v)入度：逆鄰接點(diǎn)的個(gè)數(shù)，記作ID(v)出度：鄰接點(diǎn)的個(gè)數(shù)，記作OD(v)路徑：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)歷的頂點(diǎn)序列路徑長(zhǎng)度：路徑上邊或弧的數(shù)量簡(jiǎn)單路徑：路徑上不出現(xiàn)重復(fù)頂點(diǎn)環(huán)或回路：路徑上的第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同連通圖：無(wú)向圖的任意兩個(gè)頂點(diǎn)之間存在路徑連通分量：無(wú)向圖中的極大連通子圖強(qiáng)連通圖：有向圖的任意兩個(gè)頂點(diǎn)之間存在路徑強(qiáng)連通分量：有向圖中的極大強(qiáng)連通子圖生成樹(shù)：連通圖的極小連通子圖，n個(gè)頂點(diǎn)和n-1條邊1.3圖基本運(yùn)算頂點(diǎn)定位locate(G,v)取頂點(diǎn)get_vex(G,i)求第一個(gè)鄰接點(diǎn)first_adj(G,v)求下一個(gè)鄰接點(diǎn)next_adj(G,v,w)求路徑path(G,v,w)插入頂點(diǎn)insert_vex(G,v)插入邊或弧insert_edge(G,v,w)刪除頂點(diǎn)delete_vex(G,v)刪除邊或弧delete_edge(G,v,w)遍歷圖traverse(G)2圖的存儲(chǔ)結(jié)構(gòu)問(wèn)題3：多重鏈表（結(jié)點(diǎn)上附設(shè)多個(gè)指針）合適嗎？頂點(diǎn)信息的存儲(chǔ)邊或弧信息的存儲(chǔ)2.1頂點(diǎn)順序表(sequentialvertexlist)頂點(diǎn)順序表結(jié)點(diǎn)數(shù)據(jù)類型typedef struct { elementvex; boolvisited; …… //accordingtotheproblem }vexnode;typedef structnode { vexnodedata[M]; intcount;

}vextable;2.2

鄰接矩陣(adjacencymatrix)鄰接矩陣的行列號(hào)取決于頂點(diǎn)順序表中的次序無(wú)向圖的鄰接矩陣是對(duì)稱矩陣；稀疏圖的是稀疏矩陣

有向圖的鄰接矩陣可能是不對(duì)稱的

網(wǎng)的鄰接矩陣中沒(méi)有關(guān)系的邊或弧記作0，或∞網(wǎng)及其鄰接矩陣2.3鄰接表(adjacencylist)問(wèn)題4：鄰接表上如何求給定頂點(diǎn)的逆鄰接點(diǎn)？問(wèn)題5：如上存儲(chǔ)結(jié)構(gòu)如何優(yōu)化？3圖遍歷3.1深度優(yōu)先搜索voidSearchDepthFirst(graph&G,intv) //連通分量上深度優(yōu)先搜索（遞歸算法）{ intw; visit(G.data[v].vex); //訪問(wèn)頂點(diǎn)

G.data[v].visited=1; w=first_adj(G,v); //求第一個(gè)鄰接點(diǎn)

while(w!=-1) { if(!G.data[w].visited) SearchDepthFirst(G,w); w=next_adj(G,v,w); //求下一個(gè)鄰接點(diǎn)

} }voidSearchDepthFirst(graph&G,intv) //連通分量上深度優(yōu)先搜索（非遞歸算法）{int*stack=newint[G.count],top=-1,w;visit(G.data[v].vex);G.data[v].visited=1;stack[++top]=v;while(top!=-1){v=stack[top];w=adj_first(G,v);while(w!=-1&&G.data[w].visited)w=adj_next(G,v,w);if(w!=-1){visit(G.data[w].vex);G.data[w].visited=1;stack[++top]=w;}elsetop--;}}voidTraverse(graph&G) //深度（或廣度）優(yōu)先搜索遍歷圖{ inti; for(i=0;i<G.count;i++) G.data[i].visited=0; for(i=0;i<G.count;i++) if(!G.data[i].visited) SearchDepthFirst(G,i);//深度搜索

//SearchBreadthFirst(G,i);//廣度搜索}問(wèn)題6：如何實(shí)現(xiàn)整個(gè)圖的遍歷？3.2廣度優(yōu)先搜索voidSearchBreadthFirst(graph&G,intv)//連通分量上廣度優(yōu)先搜索算法Ⅰ（訪問(wèn)后頂點(diǎn)地址入隊(duì)）{int*queue=newint[G.count],front=0,rear=0,w;visit(G.data[v].vex);G.data[v].visited=1;rear=(rear+1)%G.count;queue[rear]=v;while(front!=rear){front=(front+1)%G.count;v=queue[front];w=adj_first(G,v);while(w!=-1){if(!G.data[w].visited){visit(G.data[w].vex);G.data[w].visited=1;rear=(rear+1)%G.count;queue[rear]=w;}w=adj_next(G,v,w);}}}voidSearchBreadthFirst(graph&G,intv)//連通分量上廣度優(yōu)先搜索算法Ⅱ（待訪問(wèn)頂點(diǎn)地址入隊(duì)）{int*queue=newint[G.count],front=0,rear=1,w;queue[rear]=v;while(front!=rear){front=(front+1)%G.count;v=queue[front];visit(G.data[v].vex);G.data[v].visited=1;w=adj_first(G,v);while(w!=-1){if(!G.data[w].visited){rear=(rear+1)%G.count;queue[rear]=w;}w=adj_next(G,v,w);}}}問(wèn)題7：算法Ⅱ有bug嗎？圖遍歷算法的復(fù)雜度分析時(shí)間復(fù)雜度：以鄰接矩陣作為圖中頂點(diǎn)關(guān)系集合的存儲(chǔ)

結(jié)構(gòu)，T(n)=O(n2)

以鄰接表為存儲(chǔ)結(jié)構(gòu)，T(n,e)=O(n+e)空間復(fù)雜度：在最壞的情形下，深度優(yōu)先搜索的?？臻g

和廣度優(yōu)先搜索的隊(duì)列空間與頂點(diǎn)規(guī)模呈

線性關(guān)系 S(n)=O(n)3.3圖遍歷的應(yīng)用【例3.1】圖的連通性判定或連通分量數(shù)的計(jì)算intNumberOfConneted(graph&G) //遍歷圖計(jì)算連通分量數(shù)（無(wú)向圖）{ inti,num=0; for(i=0;i<G.count;i++)G.data[i].visited=0; for(i=0;i<G.count;i++) if(!G.data[i].visited) { SearchDepthFirst(G,i);

//SearchBreadthFrist(G,i); num++; } returnnum;}【例3.2】圖的生成樹(shù)與生成樹(shù)森林

非連通圖各連通分量的生成樹(shù)組成生成樹(shù)森林【例3.3】求兩個(gè)頂點(diǎn)之間的最短路徑及其長(zhǎng)度voidLengthOfPath(graph&G,intv,intw){int*Q=newint[G.count],front=0,rear=0,u,len=0;boolOK=false;int*pre=newint[G.count];pre[v]=-1;G.data[v].visited=true;Q[++rear]=v;while(front!=rear&&!OK){front=(front+1)%G.count;v=Q[front];u=adj_first(G,v);while(u!=-1){if(!G.data[u].visited){pre[u]=v;if(u==w){OK=true;break;}G.data[u].visited=true;rear(rear+1)%G.count;Q[rear]=u;}u=adj_next(G,v,u);}}if(!OK){cout<<“nopath!\n”;return;}int*stack=newint[G.count],top=-1;stack[++top]=w;while((w=pre[w])!=-1){stack[++top]=w;}while(top!=-1){w=stack[top--];cout<<G.data[w].vex<<‘,’;len++;}cout<<len-1<<endl;}【例3.4】不規(guī)則迷宮最短路徑的探索4網(wǎng)的最短路徑

4.1單源點(diǎn)最短路徑從源點(diǎn)到網(wǎng)中其它所有頂點(diǎn)的帶權(quán)路徑長(zhǎng)度最短的路徑【例4.1】源點(diǎn)V0的最短路徑

V0→V1：∞

V0→V2：10 V0→V4→V3：50 V0→V4：30 V0→V4→V3→V5：60Dijkstra算法（E.W.Dijkstra1959） ①設(shè)S為已知最短路徑的終點(diǎn)集合，初始化S={V0},且令T=V-S；初始化最短路徑長(zhǎng)度Di=(V0,Vi) ②選擇T中最小的Dk，將Vk并入S ③若T中Di>Dk+(Vk,Vi)，修正Di ④重復(fù)②,③，直到S=VEdsgerW.Dijkstra#defineINF9999voidDijkstra(graph&G,intv,floatdist[],intprev[]) //單源點(diǎn)最短路徑的Dijkstra算法{inti,j,u; floatmin;int*S=newint[G.count];for(i=0;i<G.count;i++){dist[i]=G.adjmat[v][i];prev[i]=v;S[i]=0;}S[v]=1;prev[v]=-1;for(i=1;i<G.count;i++){min=INF;for(j=0;j<G.count;j++)if(!S[j]&&dist[j]<min){min=dist[j];u=j;}if(min==INF)break;S[u]=1;for(j=0;j<G.count;j++)if(!S[j]&&dist[j]>dist[u]+G.adjmat[u][j]){dist[j]=dist[u]+G.adjmat[u][j];prev[j]=u;}} }問(wèn)題8：Dijkstra算法的時(shí)間復(fù)雜度？問(wèn)題9：如何輸出各最短路徑？4.2多源點(diǎn)最短路徑 算法1：每個(gè)頂點(diǎn)為出發(fā)點(diǎn)，n次調(diào)用Dijkstra算法

問(wèn)題10：算法1的時(shí)間復(fù)雜度？ 算法2：Floyd算法（R.W.Floyd1962） ①初始化Dij=(Vi,Vj) ②對(duì)任意兩個(gè)頂點(diǎn)Vi與Vj，搜索所有的中間頂點(diǎn)k，若Dij>Dik+Dkj，則修正DijRobertW.FloydvoidFloyd(graph&G,floatdist[][],intpath[][]) //多源點(diǎn)最短路徑的Floyd算法{inti,j,k;for(i=0;i<G.count;i++)for(j=0;j<G.count;j++){dist[i][j]=G.adjMat[i][j];path[i][j]=-1;}for(k=0;k<G.count;k++)for(i=0;i<G.count;i++)for(j=0;j<G.count;j++)if(dist[i][j]>dist[i][k]+dist[k][j]){dist[i][j]=dist[i][k]+dist[k][j];path[i][j]=k;}}5最小生成樹(shù)(MST)

定義：圖的所有生成樹(shù)中，邊的權(quán)值總和最小的樹(shù)

最小生成樹(shù)(MST)性質(zhì) 設(shè)G=(V,E)是一個(gè)連通網(wǎng)，U是頂點(diǎn)集V的一個(gè)非空真子集。若G中的一條邊(u,v)權(quán)值最小，且滿足u∈U和v∈V-U，則G的最小生成樹(shù)包含此邊。問(wèn)題11：如何證明最小生成樹(shù)性質(zhì)？5.1Prim算法（V.Jarník1930,R.C.Prim1957,E.W.Dijkstra1959） ①任選圖G=(V,E)中一個(gè)頂點(diǎn)v0并入生成樹(shù)頂點(diǎn)集合U={v0}，初始化生成樹(shù)邊的集合F=?

②在所有u∈U和v∈V-U鄰接的邊中選擇一條權(quán)值最小的(u’,v’)并入F,v’并入U(xiǎn) ③若v’與v∈V-U鄰接的邊的權(quán)值小于已知的(u,v),則修正(u,v)為(v’,v) ④重復(fù)②,③，直到U=V 問(wèn)題12：Prim算法的時(shí)間復(fù)雜度？#defineINF9999voidPrim(constgraph&G,intv) //Prim算法{inti,j,u; floatmin;int*Uvex=newint[G.count]; //記錄U集上的鄰接點(diǎn)

float*MinEdge=floatint[G.count];//記錄(u,v)權(quán)值

for(i=0;i<G.count;i++) //初始化

{Uvex[i]=v;MinEdge[i]=G.adjmat[v][i];}MinEdge[v]=0; //出發(fā)點(diǎn)v并入U(xiǎn)集

for(i=1;i<G.count;i++)

//n-1趟貪心選擇

{min=INF;for(j=0;j<G.count;j++)if(MinEdge[j]!=0&&min>MinEdge[j]){u=j;min=MinEdge[j];}if(min==INF){cout<<“Thegraphisnotconnected\n”;break; //

return;}cout<<G.data[Uvex[u]].vex<<‘-’<<G.data[u].vex;cout<<“：”<<min<<endl;MinEdge[u]=0; //u并入U(xiǎn)集

for(j=0;j<G.count;j++) //修正(u,v)權(quán)值

if(G.adjmat[u][j]<MinEdge[j]){MinEdge[j]=G.adjmat[u][j];Uvex[j]=u;}} }5.2Kruskal算法（J.Kruskal1956） ①令連通網(wǎng)G=(V,E)的生成樹(shù)為T(mén)=(V,E’)，初始化E’=?

②在E-E’中選擇一條權(quán)值最小的邊(u,v) ③若u和v在T中不連通，則(u,v)并入E’，否則重復(fù)步驟② ④重復(fù)②,③，直到T中所有頂點(diǎn)處于同一連通分量問(wèn)題13：Kruskal算法的時(shí)間復(fù)雜度？#defineINF9999typedefstruct {intv1,v2; //依附于邊的兩個(gè)頂點(diǎn)

floatweight; //邊的權(quán)值

}edge;voidKruskal(constgraph&G)//Kruskal算法(無(wú)向連通網(wǎng)){inti,j,num=0,p=0;edge*eList=newedge[G.count*(G.count-1)/2];for(i=0;i<G.count-1;i++)for(j=i+1;j<G.count;j++)if(G.adjmat[i][j]<INF){eList[num].v1=i;eList[num].v2=j;eList[num].weight=G.adjmat[i][j];num++;}QuickSort(elist,num); //按權(quán)值升序排序eListfloat**T=newfloat[G.count]; //生成樹(shù)鄰接矩陣

for(i=0;i<G.count;i++)T[i]=newfloat[G.count];for(i=0;i<G.count;i++){for(j=0;j<G.count;j++)T[i][j]=INF;T[i][i]=0;}while(p<num&&!AllConneted(T)){if(!isConneted(T,eList[p].v1,eList[p].v2)){T[eList[p].v1][eList[p].v2]=eList[p].weight;T[eList[p].v2][eList[p].v1]=eList[p].weight;cout<<G.data[eList[p].v1].vex<<‘-’<<G.data[eList[p].v2].vex<<‘:’<<G.data[eList[p].weight<<endl;}p++;}}6有向無(wú)環(huán)圖及其應(yīng)用

6.1有向無(wú)環(huán)圖定義（無(wú)環(huán)的有向圖）問(wèn)題14：如何檢測(cè)有向圖中是否存在環(huán)？6.2有向無(wú)環(huán)圖的應(yīng)用【例6.1】含有公共子式表達(dá)式的表示，如((a+b)×(b×(c+d))+(c+d)×e)×((c+d)×e)

消除空間冗余消除計(jì)算冗余AOV網(wǎng)與拓?fù)渑判?活動(dòng)：組成工程（系統(tǒng)）的若干子工程（子系統(tǒng)） 活動(dòng)之間：①先后關(guān)系 ②沒(méi)有關(guān)系

AOV網(wǎng)：由活動(dòng)和關(guān)系構(gòu)成的有向無(wú)環(huán)圖問(wèn)題15：如何安排活動(dòng)次序，使工程順利完成？問(wèn)題16：估算完成工程需要的最短時(shí)間（關(guān)鍵路徑）拓?fù)湫蛄校簼M足任一路徑(vi,vj)上vi

位于vj

之前的 頂點(diǎn)序列v1,v2,…,vn(vi∈V,1≤i≤n)拓?fù)渑判颍涸谟邢驁D中找出一個(gè)拓?fù)湫蛄械倪^(guò)程【例6.2】計(jì)算機(jī)專業(yè)部分課程安排課程代號(hào)課程名稱前導(dǎo)課程C1高等數(shù)學(xué)無(wú)C2程序設(shè)計(jì)基礎(chǔ)無(wú)C3數(shù)據(jù)結(jié)構(gòu)C2C4編譯原理C2,C3C5操作系統(tǒng)C3,C6C6計(jì)算機(jī)組成原理C7C7普通物理學(xué)