數(shù)據(jù)庫圖數(shù)據(jù)庫

數(shù)據(jù)庫圖數(shù)據(jù)庫第一頁，共一百一十二頁，編輯于2023年，星期三例245136G1圖G1中：V(G1)={1,2,3,4,5,6}E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}例157324G26圖G2中：V(G2)={1,2,3,4,5,6,7}E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}第二頁，共一百一十二頁，編輯于2023年，星期三有向完備圖——n個(gè)頂點(diǎn)的有向圖最大邊數(shù)是n(n-1)無向完備圖——n個(gè)頂點(diǎn)的無向圖最大邊數(shù)是n(n-1)/2權(quán)——與圖的邊或弧相關(guān)的數(shù)叫~網(wǎng)——帶權(quán)的圖叫~子圖——如果圖G(V,E)和圖G‘(V’,E‘),滿足：V’VE’E則稱G‘為G的子圖頂點(diǎn)的度無向圖中，頂點(diǎn)的度為與每個(gè)頂點(diǎn)相連的邊數(shù)有向圖中，頂點(diǎn)的度分成入度與出度入度：以該頂點(diǎn)為頭的弧的數(shù)目出度：以該頂點(diǎn)為尾的弧的數(shù)目路徑——路徑是頂點(diǎn)的序列V={Vi0,Vi1,……Vin}，滿足(Vij-1,Vij)E或<Vij-1,Vij>E,(1<jn)第三頁，共一百一十二頁，編輯于2023年，星期三路徑長度——沿路徑邊的數(shù)目或沿路徑各邊權(quán)值之和回路——第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑叫~簡單路徑——序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑叫~簡單回路——除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路叫~連通——從頂點(diǎn)V到頂點(diǎn)W有一條路徑，則說V和W是連通的連通圖——圖中任意兩個(gè)頂點(diǎn)都是連通的叫~連通分量——非連通圖的每一個(gè)連通部分叫~強(qiáng)連通圖——有向圖中，如果對(duì)每一對(duì)Vi,VjV,ViVj,從Vi到Vj和從Vj到

Vi都存在路徑，則稱G是~第四頁，共一百一十二頁，編輯于2023年，星期三例213213有向完備圖無向完備圖356例245136圖與子圖例245136G1頂點(diǎn)2入度：1出度：3頂點(diǎn)4入度：1出度：0例157324G26頂點(diǎn)5的度：3頂點(diǎn)2的度：4第五頁，共一百一十二頁，編輯于2023年，星期三例157324G26例245136G1路徑：1，2，3，5，6，3路徑長度：5簡單路徑：1，2，3，5回路：1，2，3，5，6，3，1簡單回路：3，5，6，3路徑：1，2，5，7，6，5，2，3路徑長度：7簡單路徑：1，2，5，7，6回路：1，2，5，7，6，5，2，1簡單回路：1，2，3，1第六頁，共一百一十二頁，編輯于2023年，星期三連通圖例245136強(qiáng)連通圖356例非連通圖連通分量例245136第七頁，共一百一十二頁，編輯于2023年，星期三6.2圖的存儲(chǔ)結(jié)構(gòu)多重鏈表例G12413例15324G2V1V2^^V4^V3^^V1V2V4^V5^V3第八頁，共一百一十二頁，編輯于2023年，星期三鄰接矩陣——表示頂點(diǎn)間相聯(lián)關(guān)系的矩陣定義：設(shè)G=(V,E)是有n1個(gè)頂點(diǎn)的圖，G的鄰接矩陣A是具有以下性質(zhì)的n階方陣?yán)鼼12413例15324G2第九頁，共一百一十二頁，編輯于2023年，星期三特點(diǎn)：無向圖的鄰接矩陣對(duì)稱，可壓縮存儲(chǔ)；有n個(gè)頂點(diǎn)的無向圖需存儲(chǔ)空間為n(n+1)/2有向圖鄰接矩陣不一定對(duì)稱；有n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為n2無向圖中頂點(diǎn)Vi的度TD(Vi)是鄰接矩陣A中第i行元素之和有向圖中，頂點(diǎn)Vi的出度是A中第i行元素之和頂點(diǎn)Vi的入度是A中第i列元素之和網(wǎng)絡(luò)的鄰接矩陣可定義為：第十頁，共一百一十二頁，編輯于2023年，星期三例1452375318642第十一頁，共一百一十二頁，編輯于2023年，星期三關(guān)聯(lián)矩陣——表示頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系的矩陣定義：設(shè)G=(V,E)是有n1個(gè)頂點(diǎn)，e0條邊的圖，G的關(guān)聯(lián)矩陣A是具有以下性質(zhì)的ne階矩陣第十二頁，共一百一十二頁，編輯于2023年，星期三4321例G124131234例15324G2123456432156第十三頁，共一百一十二頁，編輯于2023年，星期三例BDAC123456ABCD432156第十四頁，共一百一十二頁，編輯于2023年，星期三特點(diǎn)關(guān)聯(lián)矩陣每列只有兩個(gè)非零元素，是稀疏矩陣；n越大，零元素比率越大無向圖中頂點(diǎn)Vi的度TD(Vi)是關(guān)聯(lián)矩陣A中第i行元素之和有向圖中，頂點(diǎn)Vi的出度是A中第i行中“1”的個(gè)數(shù)頂點(diǎn)Vi的入度是A中第i行中“-1”的個(gè)數(shù)第十五頁，共一百一十二頁，編輯于2023年，星期三鄰接表實(shí)現(xiàn)：為圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊（有向圖中指以Vi為尾的?。﹖ypedefstructnode{intadjvex;//鄰接點(diǎn)域，存放與Vi鄰接的點(diǎn)在表頭數(shù)組中的位置structnode*next;//鏈域，指示下一條邊或弧指向的點(diǎn)}JD;adjvexnext表頭接點(diǎn)：typedefstructtnode{intvexdata;//存放頂點(diǎn)信息structnode*firstarc;//指示第一個(gè)鄰接點(diǎn)}TD;TDga[M];//ga[0]不用vexdatafirstarc第十六頁，共一百一十二頁，編輯于2023年，星期三例G1bdac例aecbdG21234acdbvexdatafirstarc3241^^^^adjvexnext1234acdbvexdatafirstarc4212^^^adjvexnext5e435^15323^第十七頁，共一百一十二頁，編輯于2023年，星期三特點(diǎn)無向圖中頂點(diǎn)Vi的度為第i個(gè)單鏈表中的結(jié)點(diǎn)數(shù)有向圖中頂點(diǎn)Vi的出度為第i個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)頂點(diǎn)Vi的入度為整個(gè)單鏈表中鄰接點(diǎn)域值是i的結(jié)點(diǎn)個(gè)數(shù)逆鄰接表：有向圖中對(duì)每個(gè)結(jié)點(diǎn)建立以Vi為頭的弧的單鏈表例G1bdac1234acdbvexdatafirstarc41^1^^3^adjvexnext第十八頁，共一百一十二頁，編輯于2023年，星期三6.3圖的遍歷深度優(yōu)先遍歷(DFS)方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)；然后依次從V0的未被訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V7第十九頁，共一百一十二頁，編輯于2023年，星期三V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍歷：V1V2V4V8V5V6V3V7深度遍歷：V1V2V4V8V5V6V3V7第二十頁，共一百一十二頁，編輯于2023年，星期三V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V3V6V7V5第二十一頁，共一百一十二頁，編輯于2023年，星期三深度優(yōu)先遍歷算法遞歸算法開始訪問V0,置標(biāo)志求V0鄰接點(diǎn)有鄰接點(diǎn)w求下一鄰接點(diǎn)wV0W訪問過結(jié)束NYNYDFS開始標(biāo)志數(shù)組初始化Vi=1Vi訪問過DFSVi=Vi+1Vi==Vexnums結(jié)束NNYYCh6_1.c第二十二頁，共一百一十二頁，編輯于2023年，星期三V1V2V4V5V3V7V6V8例深度遍歷：V112341342vexdatafirstarc2783^^^adjvexnext55641^51282^678678736354^^^V3V7V6V2V5V8V4第二十三頁，共一百一十二頁，編輯于2023年，星期三voiddefarc(intx[M][M],intn,TDgs[]){inti,j;JD*w,*v;for(i=0;i<n;i++){gs[i].vexdata=i;gs[i].firstarc=NULL;for(j=0;j<n;j++){if((gs[i].firstarc==NULL)&&(x[i][j]!=0)){w=(JD*)malloc(sizeof(JD));w->adjvex=j;v=w;gs[i].firstarc=w;}elseif(gs[i].firstarc!=NULL&&x[i][j]!=0){w=(JD*)malloc(sizeof(JD));w->adjvex=j;v->next=w;v=w;}}}}123413422783^^^55641^51282^678678736354^^^V1V2V4V5V3V7V6V8第二十四頁，共一百一十二頁，編輯于2023年，星期三voidtraver(TDg[],intn){inti;staticintvisited[M];for(i=0;i<n;i++)visited[i]=0;for(i=0;i<n;i++)if(visited[i]==0) dfs(g,i,visited);}123413422783^^^55641^51282^678678736354^^^第二十五頁，共一百一十二頁，編輯于2023年，星期三voiddfs(TDg[],intv,intvisited[]){JD*w;inti;printf("%d",v+1);visited[v]=1;w=g[v].firstarc;while(w!=NULL){i=w->adjvex;if(visited[i]==0) dfs(g,i,visited);w=w->next;}}123413422783^^^55641^51282^678678736354^^^V1V2V4V5V3V7V6V8例第二十六頁，共一百一十二頁，編輯于2023年，星期三V1V2V4V5V3V7V6V8例12341342vexdatafirstarc2783^^^adjvexnext556^482^6786787^^^深度遍歷：V1V3V7V6V2V4V8V5第二十七頁，共一百一十二頁，編輯于2023年，星期三廣度優(yōu)先遍歷(BFS)方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)后，依次訪問V0的各個(gè)未曾訪問過的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止V1V2V4V5V3V7V6V8例廣度遍歷：V1V2V3V4V5V6V7V8第二十八頁，共一百一十二頁，編輯于2023年，星期三V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V8廣度遍歷：V1V2V3V4V5V6V7V8第二十九頁，共一百一十二頁，編輯于2023年，星期三V1V2V4V5V3V7V6V8例廣度遍歷：V1V2V3V4V6V7V8V5第三十頁，共一百一十二頁，編輯于2023年，星期三廣度優(yōu)先遍歷算法開始標(biāo)志數(shù)組初始化Vi=1Vi訪問過BFSVi=Vi+1Vi==Vexnums結(jié)束NNYYCh6_2.c第三十一頁，共一百一十二頁，編輯于2023年，星期三開始訪問V0,置標(biāo)志求V鄰接點(diǎn)ww存在嗎V下一鄰接點(diǎn)ww訪問過結(jié)束NYNYBFS初始化隊(duì)列V0入隊(duì)隊(duì)列空嗎隊(duì)頭V出隊(duì)訪問w,置標(biāo)志w入隊(duì)NaaY第三十二頁，共一百一十二頁，編輯于2023年，星期三voidtraver(TDg[],intn){inti;staticintvisited[M];for(i=0;i<n;i++)visited[i]=0;for(i=0;i<n;i++)if(visited[i]==0)bfs(g,i,visited);}}例1423512341342vexdatafirstarc1123^^^adjvexnext555^15523^44第三十三頁，共一百一十二頁，編輯于2023年，星期三例14235voidbfs(TDg[],intv,intvisited[]){intqu[M],f=0,r=0;JD*p;printf("%d\n",v+1);visited[v]=1;qu[0]=v;while(f<=r){v=qu[f++];p=g[v].firstarc;while(p!=NULL){v=p->adjvex;if(visited[v]==0){visited[v]=1;printf("%d\n",v+1);qu[++r]=v;}p=p->next;}}12341342vexdatafirstarc1123^^^adjvexnext555^15523^44第三十四頁，共一百一十二頁，編輯于2023年，星期三例1423512341342vexdatafirstarc1123^^^adjvexnext555^15523^440123451fr遍歷序列：10123452fr遍歷序列：1201234523fr遍歷序列：123第三十五頁，共一百一十二頁，編輯于2023年，星期三例1423512341342vexdatafirstarc1123^^^adjvexnext555^15523^44012345234fr遍歷序列：123401234534fr遍歷序列：1234012345345fr遍歷序列：12345第三十六頁，共一百一十二頁，編輯于2023年，星期三01234525fr遍歷序列：123450123455fr遍歷序列：12345012345

fr遍歷序列：12345例1423512341342vexdatafirstarc1123^^^adjvexnext555^15523^44第三十七頁，共一百一十二頁，編輯于2023年，星期三6.4生成樹生成樹定義：所有頂點(diǎn)均由邊連接在一起，但不存在回路的圖叫~深度優(yōu)先生成樹與廣度優(yōu)先生成樹生成森林：非連通圖每個(gè)連通分量的生成樹一起組成非連通圖的~說明一個(gè)圖可以有許多棵不同的生成樹所有生成樹具有以下共同特點(diǎn)：生成樹的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同生成樹是圖的極小連通子圖一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹有n-1條邊生成樹中任意兩個(gè)頂點(diǎn)間的路徑是唯一的在生成樹中再加一條邊必然形成回路含n個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹GHKI第三十八頁，共一百一十二頁，編輯于2023年，星期三V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度優(yōu)先生成樹V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V8第三十九頁，共一百一十二頁，編輯于2023年，星期三例ABLMCFDEGHKIJABLMCFJDEGHKI深度優(yōu)先生成森林第四十頁，共一百一十二頁，編輯于2023年，星期三最小生成樹問題提出要在n個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)，頂點(diǎn)——表示城市權(quán)——城市間建立通信線路所需花費(fèi)代價(jià)希望找到一棵生成樹，它的每條邊上的權(quán)值之和（即建立該通信網(wǎng)所需花費(fèi)的總代價(jià)）最小———最小代價(jià)生成樹問題分析1654327131791812752410n個(gè)城市間，最多可設(shè)置n(n-1)/2條線路n個(gè)城市間建立通信網(wǎng)，只需n-1條線路問題轉(zhuǎn)化為：如何在可能的線路中選擇n-1條，能把所有城市（頂點(diǎn)）均連起來，且總耗費(fèi)（各邊權(quán)值之和）最小第四十一頁，共一百一十二頁，編輯于2023年，星期三構(gòu)造最小生成樹方法方法一：普里姆(Prim)算法算法思想：設(shè)N=(V,{E})是連通網(wǎng)，TE是N上最小生成樹中邊的集合初始令U={u0},(u0V),TE=在所有uU,vV-U的邊(u,v)E中，找一條代價(jià)最小的邊(u0,v0)將(u0,v0)并入集合TE，同時(shí)v0并入U(xiǎn)重復(fù)上述操作直至U=V為止，則T=(V,{TE})為N的最小生成樹算法實(shí)現(xiàn)：圖用鄰接矩陣表示算法描述算法評(píng)價(jià)：T(n)=O(n2)Ch6_3.c第四十二頁，共一百一十二頁，編輯于2023年，星期三例1654326513566425131163141643142116432142516543214253第四十三頁，共一百一十二頁，編輯于2023年，星期三10123450123451-21-41-1例16543265135664251-51-3165432651356642516543214253第四十四頁，共一百一十二頁，編輯于2023年，星期三#defineM30#defineMAX100voidminispantree_PRIM(intad[][M],intn){inti,j,k,p,q,wm;q=p=n-1;ad[q][q]=1;for(k=0;k<(n-1);k++)//每次找一條邊,共需n-1條邊{wm=MAX;for(i=0;i<n;i++)//對(duì)n個(gè)點(diǎn)進(jìn)行掃描if(ad[i][i]==1)

for(j=0;j<n;j++)//查找與已聯(lián)入的點(diǎn)邊權(quán)值最小的邊if((ad[j][j]==0)&&(ad[i][j]<wm))

{wm=ad[i][j];p=i;q=j;}

ad[q][q]=1;printf("%d%d%d\n",p+1,q+1,ad[p][q]);if(p>q)ad[p][q]=-ad[p][q];elsead[q][p]=-ad[q][p];}}第四十五頁，共一百一十二頁，編輯于2023年，星期三方法二：克魯斯卡爾(Kruskal)算法算法思想：設(shè)連通網(wǎng)N=(V,{E})，令最小生成樹初始狀態(tài)為只有n個(gè)頂點(diǎn)而無邊的非連通圖T=(V,{})，每個(gè)頂點(diǎn)自成一個(gè)連通分量在E中選取代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價(jià)最小的邊依此類推，直至T中所有頂點(diǎn)都在同一連通分量上為止例165432651356642516543212345第四十六頁，共一百一十二頁，編輯于2023年，星期三（0）用頂點(diǎn)數(shù)組和邊數(shù)組存放頂點(diǎn)和邊信息（1）初始時(shí)，令每個(gè)頂點(diǎn)的jihe互不相同；每個(gè)邊的flag為0（2）選出權(quán)值最小且flag為0的邊（3）若該邊依附的兩個(gè)頂點(diǎn)的jihe值不同，即非連通，則令該邊的flag=1,選中該邊；再令該邊依附的兩頂點(diǎn)的jihe以及兩集合中所有頂點(diǎn)的jihe相同若該邊依附的兩個(gè)頂點(diǎn)的jihe值相同，即連通，則令該邊的flag=2,即舍去該邊（4）重復(fù)上述步驟，直到選出n-1條邊為止頂點(diǎn)結(jié)點(diǎn)：typedefstruct{intdata;//頂點(diǎn)信息intjihe;}VEX;邊結(jié)點(diǎn)：typedefstruct{intvexh,vext;//邊依附的兩頂點(diǎn)intweight;//邊的權(quán)值intflag;//標(biāo)志域}EDGE;算法實(shí)現(xiàn)：第四十七頁，共一百一十二頁，編輯于2023年，星期三例1654326513566425Ch6_30.c算法描述：datajihe124536124536124536vexhweight112213233544vextflag6153550000000134256789334556666426000011111421112222216543212345第四十八頁，共一百一十二頁，編輯于2023年，星期三voidminitree_KRUSKAL(void){intn,i,m,min,k,j;VEXt[M];EDGEe[M];printf("Inputnumberofvertexandedge:");scanf("%d%d",&n,&m);for(i=0;i<n;i++)//建立點(diǎn)的集合{printf("t[%d].data=:",i); scanf("%d",&t[i].data); t[i].jihe=i;}for(i=0;i<m;i++)//建立邊的集合{printf("vexh,vext,weight:"); scanf("%d%d%d",&e[i].vexh,&e[i].vext,&e[i].weight); e[i].flag=0;}第四十九頁，共一百一十二頁，編輯于2023年，星期三i=1;while(i<n)//找n-1條權(quán)值最小的邊,k值為邊的編號(hào){min=MAX; for(j=0;j<m;j++) {if(e[j].weight<min&&e[j].flag==0) {min=e[j].weight; k=j; } } if(t[e[k].vexh].jihe!=t[e[k].vext].jihe) {e[k].flag=1; for(j=0;j<n;j++)//所有集合相同的點(diǎn)都改為同一集合 if(t[j].jihe==t[e[k].vext].jihe) t[j].jihe=t[e[k].vexh].jihe; t[e[k].vext].jihe=t[e[k].vexh].jihe; i++; } else e[k].flag=2;}第五十頁，共一百一十二頁，編輯于2023年，星期三for(i=0;i<m;i++)//輸出所有的點(diǎn)和邊if(e[i].flag==1) printf("%d,%d:%d\n",e[i].vexh,e[i].vext,e[i].weight);}main(){minitree_KRUSKAL();}第五十一頁，共一百一十二頁，編輯于2023年，星期三6.5拓?fù)渑判虻谖迨摚惨话僖皇?，編輯?023年，星期三6.5拓?fù)渑判騿栴}提出：學(xué)生選修課程問題頂點(diǎn)——表示課程有向弧——表示先決條件，若課程i是課程j的先決條件，則圖中有弧<i,j>學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無矛盾、順利地完成學(xué)業(yè)——拓?fù)渑判?定義AOV網(wǎng)——用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)(ActivityOnVertexnetwork)，簡稱AOV網(wǎng)若<vi,vj>是圖中有向邊，則vi是vj的直接前驅(qū)；vj是vi的直接后繼AOV網(wǎng)中不允許有回路，這意味著某項(xiàng)活動(dòng)以自己為先決條件第五十三頁，共一百一十二頁，編輯于2023年，星期三拓?fù)渑判颉袮OV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間的優(yōu)先關(guān)系排列成一個(gè)線性序列的過程叫~檢測(cè)AOV網(wǎng)中是否存在環(huán)方法：對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄校瑒t該AOV網(wǎng)必定不存在環(huán)拓?fù)渑判虻姆椒ㄔ谟邢驁D中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之從圖中刪除該頂點(diǎn)和所有以它為尾的弧重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止第五十四頁，共一百一十二頁，編輯于2023年，星期三例課程代號(hào)課程名稱先修棵C1C2C3C4C5C6C7C8C9C10C11C12無C1C1,C2C1C3,C4C11C3.C5C3,C6無C9C9C1,C9,C10程序設(shè)計(jì)基礎(chǔ)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)匯編語言語言的設(shè)計(jì)和分析計(jì)算機(jī)原理編譯原理操作系統(tǒng)高等數(shù)學(xué)線性代數(shù)普通物理數(shù)值分析C1C2C3C4C5C6C7C8C9C10C11C12第五十五頁，共一百一十二頁，編輯于2023年，星期三C1C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8或：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏牡谖迨?，共一百一十二頁，編輯?023年，星期三C1C2C3C4C5C6C7C8C9C10C11C12第五十七頁，共一百一十二頁，編輯于2023年，星期三C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1（1）C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2（2）第五十八頁，共一百一十二頁，編輯于2023年，星期三C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3（3）C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4（4）第五十九頁，共一百一十二頁，編輯于2023年，星期三C6C8C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9C6C8C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10（8）C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5（5）C6C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7（6）第六十頁，共一百一十二頁，編輯于2023年，星期三C6C8C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11（9）C8C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6（10）C8拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12（11）拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8（12）第六十一頁，共一百一十二頁，編輯于2023年，星期三算法實(shí)現(xiàn)以鄰接表作存儲(chǔ)結(jié)構(gòu)把鄰接表中所有入度為0的頂點(diǎn)進(jìn)棧棧非空時(shí)，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進(jìn)棧重復(fù)上述操作直至棧空為止。若棧空時(shí)輸出的頂點(diǎn)個(gè)數(shù)不是n，則有向圖有環(huán)；否則，拓?fù)渑判蛲戤呧徑颖斫Y(jié)點(diǎn)：typedefstructnode{intvex;//頂點(diǎn)域structnode*next;//鏈域}JD;表頭結(jié)點(diǎn)：typedefstructtnode{intin;//入度域structnode*link;//鏈域}TD;TDg[M];//g[0]不用第六十二頁，共一百一十二頁，編輯于2023年，星期三32104算法描述例1234560122inlink5543^^^vexnext3^25^240123456^Ch6_40.ctop16toptop第六十三頁，共一百一十二頁，編輯于2023年，星期三0122inlink5543^^^vexnext3^25^240123456^輸出序列：63210416toptop第六十四頁，共一百一十二頁，編輯于2023年，星期三0122inlink5543^^^vexnext3^25^240123456^輸出序列：6321041topp第六十五頁，共一百一十二頁，編輯于2023年，星期三0122inlink5543^^^vexnext2^25^240123456^輸出序列：6321041topp第六十六頁，共一百一十二頁，編輯于2023年，星期三0122inlink5543^^^vexnext2^25^240123456^輸出序列：6321041topp第六十七頁，共一百一十二頁，編輯于2023年，星期三0112inlink5543^^^vexnext2^25^240123456^輸出序列：6321041topp第六十八頁，共一百一十二頁，編輯于2023年，星期三0112inlink5543^^^vexnext2^25^240123456^輸出序列：6321041topp=NULL第六十九頁，共一百一十二頁，編輯于2023年，星期三0112inlink5543^^^vexnext2^25^240123456^輸出序列：61321041toptop第七十頁，共一百一十二頁，編輯于2023年，星期三0112inlink5543^^^vexnext2^25^240123456^輸出序列：6132104topp第七十一頁，共一百一十二頁，編輯于2023年，星期三0102inlink5543^^^vexnext2^25^240123456^輸出序列：6132104topp4第七十二頁，共一百一十二頁，編輯于2023年，星期三0102inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top第七十三頁，共一百一十二頁，編輯于2023年，星期三0102inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top第七十四頁，共一百一十二頁，編輯于2023年，星期三0002inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top3第七十五頁，共一百一十二頁，編輯于2023年，星期三0002inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top3第七十六頁，共一百一十二頁，編輯于2023年，星期三0002inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top3第七十七頁，共一百一十二頁，編輯于2023年，星期三0001inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top3第七十八頁，共一百一十二頁，編輯于2023年，星期三0001inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p=NULL4top3第七十九頁，共一百一十二頁，編輯于2023年，星期三0001inlink5543^^^vexnext2^25^240123456^輸出序列：613321044top3第八十頁，共一百一十二頁，編輯于2023年，星期三0001inlink5543^^^vexnext2^25^240123456^輸出序列：613321044topp第八十一頁，共一百一十二頁，編輯于2023年，星期三0001inlink5543^^^vexnext1^25^240123456^輸出序列：613321044topp第八十二頁，共一百一十二頁，編輯于2023年，星期三0001inlink5543^^^vexnext1^25^240123456^輸出序列：613321044topp第八十三頁，共一百一十二頁，編輯于2023年，星期三0000inlink5543^^^vexnext1^25^240123456^輸出序列：613321044topp2第八十四頁，共一百一十二頁，編輯于2023年，星期三0000inlink5543^^^vexnext1^25^240123456^輸出序列：613321044topp2第八十五頁，共一百一十二頁，編輯于2023年，星期三0000inlink5543^^^vexnext1^25^240123456^輸出序列：613321044top2p=NULL第八十六頁，共一百一十二頁，編輯于2023年，星期三0000inlink5543^^^vexnext1^25^240123456^輸出序列：6132321044top2p=NULL第八十七頁，共一百一十二頁，編輯于2023年，星期三0000inlink5543^^^vexnext1^25^240123456^輸出序列：6132321044topp=NULL第八十八頁，共一百一十二頁，編輯于2023年，星期三0000inlink5543^^^vexnext1^25^240123456^輸出序列：61324321044top第八十九頁，共一百一十二頁，編輯于2023年，星期三0000inlink5543^^^vexnext1^25^240123456^輸出序列：6132432104topp第九十頁，共一百一十二頁，編輯于2023年，星期三0000inlink5543^^^vexnext0^25^240123456^輸出序列：6132432104topp5第九十一頁，共一百一十二頁，編輯于2023年，星期三0000inlink5543^^^vexnext0^25^240123456^輸出序列：6132432104topp=NULL5第九十二頁，共一百一十二頁，編輯于2023年，星期三0000inlink5543^^^vexnext0^25^240123456^輸出序列：61324532104top5第九十三頁，共一百一十二頁，編輯于2023年，星期三0000inlink5543^^^vexnext0^25^240123456^輸出序列：61324532104topp=NULL第九十四頁，共一百一十二頁，編輯于2023年，星期三voidtoposort(TDg[],intn){inttop,m,k,j,x;ints[M];//top:棧頂，s[]:棧，m：個(gè)數(shù)，k：鄰接點(diǎn)，x：中間變量JD*p;top=0;m=0;for(j=1;j<=n;j++)//入度為0的點(diǎn)入棧if(g[j].in==0)s[top++]=j;while(top>=0){x=s[top--];printf("%d\n",x);m++;p=g[x].link;

while(p!=NULL){k=p->vex;g[k].in--;if(g[k].in==0)s[top++]=k;p=p->next;}}printf("m=%d\n",m);if(m<n)printf("Thenetworkhasacycle\n");}第九十五頁，共一百一十二頁，編輯于2023年，星期三算法分析建鄰接表：T(n)=O(e)搜索入度為0的頂點(diǎn)的時(shí)間：T(n)=O(n)拓?fù)渑判颍篢(n)=O(n+e)Ch6_4.c第九十六頁，共一百一十二頁，編輯于2023年，星期三6.6關(guān)鍵路徑問題提出把工程計(jì)劃表示為有向圖，用頂點(diǎn)表示事件，弧表示活動(dòng)；每個(gè)事件表示在它之前的活動(dòng)已完成，在它之后的活動(dòng)可以開始例設(shè)一個(gè)工程有11項(xiàng)活動(dòng)，9個(gè)事件事件V1——表示整個(gè)工程開始事件V9——表示整個(gè)工程結(jié)束問題：（1）完成整項(xiàng)工程至少需要多少時(shí)間？（2）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4第九十七頁，共一百一十二頁，編輯于2023年，星期三定義AOE網(wǎng)(ActivityOnEdge)——也叫邊表示活動(dòng)的網(wǎng)。AOE網(wǎng)是一個(gè)帶權(quán)的有向無環(huán)圖，其中頂點(diǎn)表示事件，弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)時(shí)間路徑長度——路徑上各活動(dòng)持續(xù)時(shí)間之和關(guān)鍵路徑——路徑長度最長的路徑叫~Ve(j)——表示事件Vj的最早發(fā)生時(shí)間Vl(j)——表示事件Vj的最遲發(fā)生時(shí)間e(i)——表示活動(dòng)ai的最早開始時(shí)間l(i)——表示活動(dòng)ai的最遲開始時(shí)間l(i)-e(i)——表示完成活動(dòng)ai的時(shí)間余量關(guān)鍵活動(dòng)——關(guān)鍵路徑上的活動(dòng)叫~，即l(i)=e(i)的活動(dòng)第九十八頁，共一百一十二頁，編輯于2023年，星期三問題分析如何找e(i)=l(i)的關(guān)鍵活動(dòng)？設(shè)活動(dòng)ai用弧<j,k>表示，其持續(xù)時(shí)間記為：dut(<j,k>)則有：（1）e(i)=Ve(j)（2）l(i)=Vl(k)-dut(<j,k>)jkai如何求Ve(j)和Vl(j)？(1)從Ve(1)=0開始向前遞推(2)從Vl(n)=Ve(n)開始向后遞推第九十九頁，共一百一十二頁，編輯于2023年，星期三求關(guān)鍵路徑步驟求Ve(i)求Vl(j)求e(i)求l(i)計(jì)算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9頂點(diǎn)VeVl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動(dòng)ell-e00002266046258377077071031616014140033第一百頁，共一百一十二頁，編輯于2023年，星期三算法實(shí)現(xiàn)以鄰接表作存儲(chǔ)結(jié)構(gòu)從源點(diǎn)V1出發(fā)，令Ve[1]=0,按拓?fù)湫蛄星蟾黜旤c(diǎn)的Ve[i]從匯點(diǎn)Vn出發(fā)，令Vl[n]=Ve[n],按逆拓?fù)湫蛄星笃溆喔黜旤c(diǎn)的Vl[i]根據(jù)各頂點(diǎn)的Ve和Vl值，計(jì)算每條弧的e[i]和l[i],找出e[i]=l[i]的關(guān)鍵活動(dòng)鄰接表結(jié)點(diǎn)：typedefstructnode{intvex;//頂點(diǎn)域intlength;structnode*next;//鏈域}JD;表頭結(jié)點(diǎn)：typedefstructtnode{intvexdata;intin;//入度域structnode*link;//鏈域}TD;TDg[M];//g[0]不用第一百零一頁，共一百一十二頁，編輯于2023年，星期三算法描述輸入頂點(diǎn)和弧信息，建立其鄰接表計(jì)算每個(gè)頂點(diǎn)的入度對(duì)其進(jìn)行拓?fù)渑判蚺判蜻^程中求頂點(diǎn)的Ve[i]將得到的拓?fù)湫蛄羞M(jìn)棧按逆拓?fù)湫蛄星箜旤c(diǎn)的Vl[i]計(jì)算每條弧的e[i]和l[i],找出e[i]=l[i]的關(guān)鍵活動(dòng)Ch6_20.c987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4第一百零二頁，共一百一十二頁，編輯于2023年，星期三987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4inlinkvexnextvexdatalength123456789123456789011121122263445^79^51^62^51^87^84^910^94^第一百零三頁，共一百一十二頁，編輯于2023年，星期三6.7最短路徑問題提出用帶權(quán)的有向圖表示一個(gè)交通運(yùn)輸網(wǎng)，圖中：頂點(diǎn)——表示城市邊——表示城市間的交通聯(lián)系權(quán)——表示此線路的長度或沿此線路運(yùn)輸所花的時(shí)間或費(fèi)用等問題：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑——最短路徑從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑51643208562301371732913長度最短路徑<V0,V1><V0,V2><V0,V2,V3><V0,V2,V3,V4><V0,V2,V3,V4,V5><V0,V1,V6>813192120第一百零四頁，共一百一十二頁，編輯于2023年，星期三迪杰斯特拉(Dijkstra)算法思想按路徑長度遞增次序產(chǎn)生最短路徑算法：把V分成兩組：（1）S：已求出最短路徑的頂點(diǎn)的集合（2）V-S=T：尚未確定最短路徑的頂點(diǎn)集合將T中頂點(diǎn)按最短路徑遞增的次序加入到S中，保證：（1）從源點(diǎn)V0到S中各頂點(diǎn)的最短路徑長度都不大于從V0到T中任何頂點(diǎn)的最短路徑長度（2）每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離值S中頂點(diǎn)：從V0到此頂點(diǎn)的最短路徑長度T中頂點(diǎn)：從V0到此頂點(diǎn)的只包括S中頂點(diǎn)作中間頂點(diǎn)的最短路徑長度依據(jù)：可以證明V0到T中頂點(diǎn)Vk的最短路徑，或是從V0到Vk的直接路徑的權(quán)值；或是從V0經(jīng)S中頂點(diǎn)到Vk的路徑權(quán)值之和（反證法可證