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

Vi都存在路徑，則稱G是~第四頁，共一百一十二頁，編輯于2023年，星期三例213213有向完備圖無向完備圖356例245136圖與子圖例245136G1頂點2入度：1出度：3頂點4入度：1出度：0例157324G26頂點5的度：3頂點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強連通圖356例非連通圖連通分量例245136第七頁，共一百一十二頁，編輯于2023年，星期三6.2圖的存儲結構多重鏈表例G12413例15324G2V1V2^^V4^V3^^V1V2V4^V5^V3第八頁，共一百一十二頁，編輯于2023年，星期三鄰接矩陣——表示頂點間相聯(lián)關系的矩陣定義：設G=(V,E)是有n1個頂點的圖，G的鄰接矩陣A是具有以下性質的n階方陣例G12413例15324G2第九頁，共一百一十二頁，編輯于2023年，星期三特點：無向圖的鄰接矩陣對稱，可壓縮存儲；有n個頂點的無向圖需存儲空間為n(n+1)/2有向圖鄰接矩陣不一定對稱；有n個頂點的有向圖需存儲空間為n2無向圖中頂點Vi的度TD(Vi)是鄰接矩陣A中第i行元素之和有向圖中，頂點Vi的出度是A中第i行元素之和頂點Vi的入度是A中第i列元素之和網(wǎng)絡的鄰接矩陣可定義為：第十頁，共一百一十二頁，編輯于2023年，星期三例1452375318642第十一頁，共一百一十二頁，編輯于2023年，星期三關聯(lián)矩陣——表示頂點與邊的關聯(lián)關系的矩陣定義：設G=(V,E)是有n1個頂點，e0條邊的圖，G的關聯(lián)矩陣A是具有以下性質的ne階矩陣第十二頁，共一百一十二頁，編輯于2023年，星期三4321例G124131234例15324G2123456432156第十三頁，共一百一十二頁，編輯于2023年，星期三例BDAC123456ABCD432156第十四頁，共一百一十二頁，編輯于2023年，星期三特點關聯(lián)矩陣每列只有兩個非零元素，是稀疏矩陣；n越大，零元素比率越大無向圖中頂點Vi的度TD(Vi)是關聯(lián)矩陣A中第i行元素之和有向圖中，頂點Vi的出度是A中第i行中“1”的個數(shù)頂點Vi的入度是A中第i行中“-1”的個數(shù)第十五頁，共一百一十二頁，編輯于2023年，星期三鄰接表實現(xiàn)：為圖中每個頂點建立一個單鏈表，第i個單鏈表中的結點表示依附于頂點Vi的邊（有向圖中指以Vi為尾的?。﹖ypedefstructnode{intadjvex;//鄰接點域，存放與Vi鄰接的點在表頭數(shù)組中的位置structnode*next;//鏈域，指示下一條邊或弧指向的點}JD;adjvexnext表頭接點：typedefstructtnode{intvexdata;//存放頂點信息structnode*firstarc;//指示第一個鄰接點}TD;TDga[M];//ga[0]不用vexdatafirstarc第十六頁，共一百一十二頁，編輯于2023年，星期三例G1bdac例aecbdG21234acdbvexdatafirstarc3241^^^^adjvexnext1234acdbvexdatafirstarc4212^^^adjvexnext5e435^15323^第十七頁，共一百一十二頁，編輯于2023年，星期三特點無向圖中頂點Vi的度為第i個單鏈表中的結點數(shù)有向圖中頂點Vi的出度為第i個單鏈表中的結點個數(shù)頂點Vi的入度為整個單鏈表中鄰接點域值是i的結點個數(shù)逆鄰接表：有向圖中對每個結點建立以Vi為頭的弧的單鏈表例G1bdac1234acdbvexdatafirstarc41^1^^3^adjvexnext第十八頁，共一百一十二頁，編輯于2023年，星期三6.3圖的遍歷深度優(yōu)先遍歷(DFS)方法：從圖的某一頂點V0出發(fā)，訪問此頂點；然后依次從V0的未被訪問的鄰接點出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問為止V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V7第十九頁，共一百一十二頁，編輯于2023年，星期三V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍歷：V1V2V4V8V5V6V3V7深度遍歷：V1V2V4V8V5V6V3V7第二十頁，共一百一十二頁，編輯于2023年，星期三V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V3V6V7V5第二十一頁，共一百一十二頁，編輯于2023年，星期三深度優(yōu)先遍歷算法遞歸算法開始訪問V0,置標志求V0鄰接點有鄰接點w求下一鄰接點wV0W訪問過結束NYNYDFS開始標志數(shù)組初始化Vi=1Vi訪問過DFSVi=Vi+1Vi==Vexnums結束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)方法：從圖的某一頂點V0出發(fā)，訪問此頂點后，依次訪問V0的各個未曾訪問過的鄰接點；然后分別從這些鄰接點出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點的鄰接點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問為止V1V2V4V5V3V7V6V8例廣度遍歷：V1V2V3V4V5V6V7V8第二十八頁，共一百一十二頁，編輯于2023年，星期三V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V8廣度遍歷：V1V2V3V4V5V6V7V8第二十九頁，共一百一十二頁，編輯于2023年，星期三V1V2V4V5V3V7V6V8例廣度遍歷：V1V2V3V4V6V7V8V5第三十頁，共一百一十二頁，編輯于2023年，星期三廣度優(yōu)先遍歷算法開始標志數(shù)組初始化Vi=1Vi訪問過BFSVi=Vi+1Vi==Vexnums結束NNYYCh6_2.c第三十一頁，共一百一十二頁，編輯于2023年，星期三開始訪問V0,置標志求V鄰接點ww存在嗎V下一鄰接點ww訪問過結束NYNYBFS初始化隊列V0入隊隊列空嗎隊頭V出隊訪問w,置標志w入隊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生成樹生成樹定義：所有頂點均由邊連接在一起，但不存在回路的圖叫~深度優(yōu)先生成樹與廣度優(yōu)先生成樹生成森林：非連通圖每個連通分量的生成樹一起組成非連通圖的~說明一個圖可以有許多棵不同的生成樹所有生成樹具有以下共同特點：生成樹的頂點個數(shù)與圖的頂點個數(shù)相同生成樹是圖的極小連通子圖一個有n個頂點的連通圖的生成樹有n-1條邊生成樹中任意兩個頂點間的路徑是唯一的在生成樹中再加一條邊必然形成回路含n個頂點n-1條邊的圖不一定是生成樹GHKI第三十八頁，共一百一十二頁，編輯于2023年，星期三V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度優(yōu)先生成樹V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V8第三十九頁，共一百一十二頁，編輯于2023年，星期三例ABLMCFDEGHKIJABLMCFJDEGHKI深度優(yōu)先生成森林第四十頁，共一百一十二頁，編輯于2023年，星期三最小生成樹問題提出要在n個城市間建立通信聯(lián)絡網(wǎng)，頂點——表示城市權——城市間建立通信線路所需花費代價希望找到一棵生成樹，它的每條邊上的權值之和（即建立該通信網(wǎng)所需花費的總代價）最小———最小代價生成樹問題分析1654327131791812752410n個城市間，最多可設置n(n-1)/2條線路n個城市間建立通信網(wǎng)，只需n-1條線路問題轉化為：如何在可能的線路中選擇n-1條，能把所有城市（頂點）均連起來，且總耗費（各邊權值之和）最小第四十一頁，共一百一十二頁，編輯于2023年，星期三構造最小生成樹方法方法一：普里姆(Prim)算法算法思想：設N=(V,{E})是連通網(wǎng)，TE是N上最小生成樹中邊的集合初始令U={u0},(u0V),TE=在所有uU,vV-U的邊(u,v)E中，找一條代價最小的邊(u0,v0)將(u0,v0)并入集合TE，同時v0并入U重復上述操作直至U=V為止，則T=(V,{TE})為N的最小生成樹算法實現(xiàn)：圖用鄰接矩陣表示算法描述算法評價：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++)//對n個點進行掃描if(ad[i][i]==1)

for(j=0;j<n;j++)//查找與已聯(liá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)算法算法思想：設連通網(wǎng)N=(V,{E})，令最小生成樹初始狀態(tài)為只有n個頂點而無邊的非連通圖T=(V,{})，每個頂點自成一個連通分量在E中選取代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價最小的邊依此類推，直至T中所有頂點都在同一連通分量上為止例165432651356642516543212345第四十六頁，共一百一十二頁，編輯于2023年，星期三（0）用頂點數(shù)組和邊數(shù)組存放頂點和邊信息（1）初始時，令每個頂點的jihe互不相同；每個邊的flag為0（2）選出權值最小且flag為0的邊（3）若該邊依附的兩個頂點的jihe值不同，即非連通，則令該邊的flag=1,選中該邊；再令該邊依附的兩頂點的jihe以及兩集合中所有頂點的jihe相同若該邊依附的兩個頂點的jihe值相同，即連通，則令該邊的flag=2,即舍去該邊（4）重復上述步驟，直到選出n-1條邊為止頂點結點：typedefstruct{intdata;//頂點信息intjihe;}VEX;邊結點：typedefstruct{intvexh,vext;//邊依附的兩頂點intweight;//邊的權值intflag;//標志域}EDGE;算法實現(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++)//建立點的集合{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條權值最小的邊,k值為邊的編號{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++)//所有集合相同的點都改為同一集合 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++)//輸出所有的點和邊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拓撲排序第五十二頁，共一百一十二頁，編輯于2023年，星期三6.5拓撲排序問題提出：學生選修課程問題頂點——表示課程有向弧——表示先決條件，若課程i是課程j的先決條件，則圖中有弧<i,j>學生應按怎樣的順序學習這些課程，才能無矛盾、順利地完成學業(yè)——拓撲排序 定義AOV網(wǎng)——用頂點表示活動，用弧表示活動間優(yōu)先關系的有向圖稱為頂點表示活動的網(wǎng)(ActivityOnVertexnetwork)，簡稱AOV網(wǎng)若<vi,vj>是圖中有向邊，則vi是vj的直接前驅；vj是vi的直接后繼AOV網(wǎng)中不允許有回路，這意味著某項活動以自己為先決條件第五十三頁，共一百一十二頁，編輯于2023年，星期三拓撲排序——把AOV網(wǎng)絡中各頂點按照它們相互之間的優(yōu)先關系排列成一個線性序列的過程叫~檢測AOV網(wǎng)中是否存在環(huán)方法：對有向圖構造其頂點的拓撲有序序列，若網(wǎng)中所有頂點都在它的拓撲有序序列中，則該AOV網(wǎng)必定不存在環(huán)拓撲排序的方法在有向圖中選一個沒有前驅的頂點且輸出之從圖中刪除該頂點和所有以它為尾的弧重復上述兩步，直至全部頂點均已輸出；或者當圖中不存在無前驅的頂點為止第五十四頁，共一百一十二頁，編輯于2023年，星期三例課程代號課程名稱先修棵C1C2C3C4C5C6C7C8C9C10C11C12無C1C1,C2C1C3,C4C11C3.C5C3,C6無C9C9C1,C9,C10程序設計基礎離散數(shù)學數(shù)據(jù)結構匯編語言語言的設計和分析計算機原理編譯原理操作系統(tǒng)高等數(shù)學線性代數(shù)普通物理數(shù)值分析C1C2C3C4C5C6C7C8C9C10C11C12第五十五頁，共一百一十二頁，編輯于2023年，星期三C1C2C3C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8或：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8一個AOV網(wǎng)的拓撲序列不是唯一的第五十六頁，共一百一十二頁，編輯于2023年，星期三C1C2C3C4C5C6C7C8C9C10C11C12第五十七頁，共一百一十二頁，編輯于2023年，星期三C2C3C4C5C6C7C8C9C10C11C12拓撲序列：C1（1）C3C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2（2）第五十八頁，共一百一十二頁，編輯于2023年，星期三C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3（3）C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3--C4（4）第五十九頁，共一百一十二頁，編輯于2023年，星期三C6C8C10C11C12拓撲序列：C1--C2--C3--C4--C5--C7--C9C6C8C11C12拓撲序列：C1--C2--C3--C4--C5--C7--C9--C10（8）C6C7C8C9C10C11C12拓撲序列：C1--C2--C3--C4--C5（5）C6C8C9C10C11C12拓撲序列：C1--C2--C3--C4--C5--C7（6）第六十頁，共一百一十二頁，編輯于2023年，星期三C6C8C12拓撲序列：C1--C2--C3--C4--C5--C7--C9--C10--C11（9）C8C12拓撲序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6（10）C8拓撲序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12（11）拓撲序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8（12）第六十一頁，共一百一十二頁，編輯于2023年，星期三算法實現(xiàn)以鄰接表作存儲結構把鄰接表中所有入度為0的頂點進棧棧非空時，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進棧重復上述操作直至?？諡橹埂Ｈ魲？諘r輸出的頂點個數(shù)不是n，則有向圖有環(huán)；否則，拓撲排序完畢鄰接表結點：typedefstructnode{intvex;//頂點域structnode*next;//鏈域}JD;表頭結點：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：個數(shù)，k：鄰接點，x：中間變量JD*p;top=0;m=0;for(j=1;j<=n;j++)//入度為0的點入棧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的頂點的時間：T(n)=O(n)拓撲排序：T(n)=O(n+e)Ch6_4.c第九十六頁，共一百一十二頁，編輯于2023年，星期三6.6關鍵路徑問題提出把工程計劃表示為有向圖，用頂點表示事件，弧表示活動；每個事件表示在它之前的活動已完成，在它之后的活動可以開始例設一個工程有11項活動，9個事件事件V1——表示整個工程開始事件V9——表示整個工程結束問題：（1）完成整項工程至少需要多少時間？（2）哪些活動是影響工程進度的關鍵？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4第九十七頁，共一百一十二頁，編輯于2023年，星期三定義AOE網(wǎng)(ActivityOnEdge)——也叫邊表示活動的網(wǎng)。AOE網(wǎng)是一個帶權的有向無環(huán)圖，其中頂點表示事件，弧表示活動，權表示活動持續(xù)時間路徑長度——路徑上各活動持續(xù)時間之和關鍵路徑——路徑長度最長的路徑叫~Ve(j)——表示事件Vj的最早發(fā)生時間Vl(j)——表示事件Vj的最遲發(fā)生時間e(i)——表示活動ai的最早開始時間l(i)——表示活動ai的最遲開始時間l(i)-e(i)——表示完成活動ai的時間余量關鍵活動——關鍵路徑上的活動叫~，即l(i)=e(i)的活動第九十八頁，共一百一十二頁，編輯于2023年，星期三問題分析如何找e(i)=l(i)的關鍵活動？設活動ai用弧<j,k>表示，其持續(xù)時間記為：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年，星期三求關鍵路徑步驟求Ve(i)求Vl(j)求e(i)求l(i)計算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9頂點VeVl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動ell-e00002266046258377077071031616014140033第一百頁，共一百一十二頁，編輯于2023年，星期三算法實現(xiàn)以鄰接表作存儲結構從源點V1出發(fā)，令Ve[1]=0,按拓撲序列求各頂點的Ve[i]從匯點Vn出發(fā)，令Vl[n]=Ve[n],按逆拓撲序列求其余各頂點的Vl[i]根據(jù)各頂點的Ve和Vl值，計算每條弧的e[i]和l[i],找出e[i]=l[i]的關鍵活動鄰接表結點：typedefstructnode{intvex;//頂點域intlength;structnode*next;//鏈域}JD;表頭結點：typedefstructtnode{intvexdata;intin;//入度域structnode*link;//鏈域}TD;TDg[M];//g[0]不用第一百零一頁，共一百一十二頁，編輯于2023年，星期三算法描述輸入頂點和弧信息，建立其鄰接表計算每個頂點的入度對其進行拓撲排序排序過程中求頂點的Ve[i]將得到的拓撲序列進棧按逆拓撲序列求頂點的Vl[i]計算每條弧的e[i]和l[i],找出e[i]=l[i]的關鍵活動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最短路徑問題提出用帶權的有向圖表示一個交通運輸網(wǎng)，圖中：頂點——表示城市邊——表示城市間的交通聯(lián)系權——表示此線路的長度或沿此線路運輸所花的時間或費用等問題：從某頂點出發(fā)，沿圖的邊到達另一頂點所經(jīng)過的路徑中，各邊上權值之和最小的一條路徑——最短路徑從某個源點到其余各頂點的最短路徑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：已求出最短路徑的頂點的集合（2）V-S=T：尚未確定最短路徑的頂點集合將T中頂點按最短路徑遞增的次序加入到S中，保證：（1）從源點V0到S中各頂點的最短路徑長度都不大于從V0到T中任何頂點的最短路徑長度（2）每個頂點對應一個距離值S中頂點：從V0到此頂點的最短路徑長度T中頂點：從V0到此頂點的只包括S中頂點作中間頂點的最短路徑長度依據(jù)：可以證明V0到T中頂點Vk的最短路徑，或是從V0到Vk的直接路徑的權值；或是從V0經(jīng)S中頂點到Vk的路徑權值之和（反證法可證