數(shù)據(jù)結構與算法-圖與網(wǎng)

第五章圖與網(wǎng)6/22/20241第五章圖與網(wǎng)5.1圖與網(wǎng)的基本概念5.2圖與網(wǎng)的存儲結構5.3圖的遍歷5.4無向連通網(wǎng)的最小生成樹5.5有向網(wǎng)的最短路徑5.6有向無環(huán)圖及其應用6/22/202425.1圖與網(wǎng)的基本概念5.1.1圖與網(wǎng)的定義和術語圖的定義G=(V,E)ADCBE無向圖ADCBE有向圖頂點

邊

弧

弧尾

弧頭

6/22/202435.1.1圖與網(wǎng)的定義和術語頂點與邊的關系無向圖：0≤e≤n(n-1)/2

有向圖：0≤e≤n(n-1)ADCBE完全圖ADCBE稀疏圖e<nlogn6/22/202445.1.1圖與網(wǎng)的定義和術語網(wǎng)的定義弧或邊標上具體的數(shù)字，這些數(shù)稱為權。帶有權的圖稱為網(wǎng)

ADCBE無向網(wǎng)567434296/22/202455.1.1圖與網(wǎng)的定義和術語子圖的定義ADCBE圖GADCE圖G的子圖6/22/202465.1.2圖的相關術語無向圖頂點的度無向圖頂點的度等于依附于該頂點的邊的數(shù)目，例：TD(A)=3ADCBE無向圖6/22/202475.1.2圖的相關術語有向圖頂點的度有向圖中：分為入度ID(V)和出度OD(V)TD(V)=ID(V)+OD(V)

例：TD(E)=3，其中出度為OD(E)1，入度ID(E)為2ADCBE有向圖6/22/202485.1.2圖的相關術語頂點的度和邊的關系e=1/2∑TD(Vi)i=1nADCBE無向圖6/22/202495.1.2圖的相關術語路徑、回路(環(huán))，簡單路徑路徑：從A到D所經(jīng)過的頂點序列回路(環(huán)):AEDBA簡單路徑：頂點不重復出現(xiàn)ADCBE無向圖6/22/2024105.1.2圖的相關術語連通圖，連通分量連通圖：無向圖中，任何兩個頂點都連通。連通分量：非連通圖的極大連通子圖ADCBE連通圖GADCBE非連通圖G1ADCBEG1的兩個連通分量6/22/202411CB非強連通圖兩個強連通分量B非強連通圖ADCBE強連通圖AD6/22/2024125.1.2圖的相關術語連通圖的生成樹定義：極小連通子圖，包含全部n個頂點，只有n-1條邊ADCBE連通圖GADCBE生成樹6/22/2024135.2圖與網(wǎng)的存儲結構5.2.1鄰接矩陣ADCBEABCDEABCDE6/22/2024145.2.1鄰接矩陣網(wǎng)的鄰接矩陣ADCBE無向網(wǎng)56794ABCDEABCDE6/22/2024155.2.1鄰接矩陣鄰接矩陣類型定義

#definemaxvernum100#defineinfinitymaxinteger

typedef

struct{vertextype

vex[maxvernum];

int

adjmatrix[maxvernum][maxvernum];

int

n,e;/*定義頂點數(shù)和邊或弧數(shù)變量單元*/}mgraph;ADCBE6/22/2024165.2.2鄰接表與逆鄰接表無向網(wǎng)的鄰接表ADCBE無向網(wǎng)567940A1B2C3D4E15270536440749162914鄰接表6/22/2024175.2.2鄰接表與逆鄰接表有向網(wǎng)的鄰接表ADCBE152705360749162914鄰接表6/22/2024185.2.2鄰接表與逆鄰接表鄰接表結點定義鄰接表中結點和表頭結點的形式描述定義如下：

#definemaxvernum100/*定義表結點結構*/

typedef

structnode{int

adjvex,info;

structnode*next;}nodetype;/*定義表頭結點結構*/

typedef

struct

frontnode

{vertextypedata;

structnode*next;}frontnodetype;

typedef

frontnodetype

adjlist[maxvernum];6/22/2024195.2.2鄰接表與逆鄰接表逆鄰接表有向圖中為了便于查找以某結點為終點的邊ADCBEABCDE0536072823逆鄰接表568273326/22/2024205.2.3鄰接多重表datafristedge頂點結構邊結點結構markilinkivexjlinkjvex6/22/2024215.2.3鄰接多重表結點定義typedef

struct

edgenode/*定義邊結點類型*/{intmark,ivex,jvex;/*對于網(wǎng)可增加整型info域*/

struct

edgenode*ilink,*jlink;}edgenodetype;/*定義頂點結點類型*/typedef

struct

vexnode{intdata;

struct

edgenode*firstedge;}vexnodetype;typedef

vexnodetype

adjmulist[maxvernum]6/22/2024225.3圖的遍歷從圖中某一頂點出發(fā)，訪問圖中其余頂點，且使每一頂點僅被訪問一次。深度優(yōu)先搜索遍歷廣度優(yōu)先搜索遍歷ADCBEGF6/22/2024235.3.1深度優(yōu)先搜索遍歷遞歸算法描述如下，類似樹的先根遍歷ADCBEGF⑴從圖中某個頂點v0出發(fā)并訪問它；⑵依次從v0的未被訪問的鄰接頂點出發(fā)深度優(yōu)先遍歷圖，直到圖中所有從v0出發(fā)有路徑可達的頂點都已被訪問到；⑶若圖中還有頂點未被訪問到，則另選一個未被訪問的頂點記作v0轉⑴，否則圖的深度優(yōu)先遍歷結束。圖G的深度遍歷CDBEFGA6/22/2024245.3.1深度優(yōu)先搜索遍歷深度優(yōu)先算法的實現(xiàn)1.先定義存儲結構假設圖用鄰接表作存儲結構為了在遍歷過程中區(qū)分頂點是否已被訪問過，設置標志數(shù)組c[n+1]，初始值全為0，一旦頂點vi被訪問時置c[i]為1。6/22/2024255.3.1深度優(yōu)先搜索遍歷2.從頂點v出發(fā)按深度優(yōu)先搜索遍歷圖的遞歸算法dfs如下：

voiddfs(adjlist

g[],int

v,intc[]){inti;

nodetype*p;

c[v]=1;

printf(“%d\n”,v);/*訪問頂點v*/

for(p=g[v].next;p!=NULL;p=p->next){i=p->adjvex;

if(c[i]==0)

dfs(g,i,c);}}ADCBEGF圖G的深度遍歷6/22/2024265.3.1深度優(yōu)先搜索遍歷3.對整個圖的遍歷算法travergraph如下voidtravergraph(adjlistg[],intn){intv;

intc[n+1];

for(v=1;v<=n;v++)

c[v]=0;/*標志數(shù)組初始化*/

for(v=1;v<=n;v++)/*按深度優(yōu)先遍歷圖g*/

if(c[v]==0)

dfs(g,v,c);}ADCBEGF圖G的深度遍歷6/22/2024275.3.2廣度優(yōu)先搜索遍歷遞歸算法描述如下，類似樹的先根遍歷ADCBEGF⑴從圖中某個頂點v0出發(fā)并訪問它；⑵依次訪問v0的各個未被訪問的鄰接頂點，然后分別從這些鄰接頂點出發(fā)依次訪問它們的鄰接頂點，并使先被訪問頂點的鄰接頂點先于后被訪問頂點的鄰接頂點，直到圖中已被訪問過的頂點的鄰接頂點都被訪問到；⑶若圖中還有頂點未被訪問到，則另選一個未被訪問的頂點記作v0轉⑴，否則圖的廣度優(yōu)先遍歷結束。圖G的深度遍歷BCEDFGA6/22/2024285.3.2廣度優(yōu)先搜索遍歷算法實現(xiàn)仍假設使用鄰接表作為存儲結構設置隊列q存放已被訪問過的頂點以保證按層次依次訪問它們的鄰接頂點；同時需要設置一個數(shù)組c記錄頂點是否已被訪問的情況。ADCBEGF圖G的廣度遍歷6/22/2024295.3.2廣度優(yōu)先搜索遍歷圖的廣度優(yōu)先搜索算法bfs可描述如下：voidbfs(adjlist

g[],int

v,intc[]){intq[N+1],r=0,f=0;//定義隊列q,r為隊尾指針,f為隊頭

nodetype*p;

c[v]=1;printf(“%d\n”,v);q[0]=v;

while(f<=r)/*當隊列q不空時*/{v=q[f++];p=g[v].next;

while(p!=NULL){v=p->adjvex;

if(c[v]==0){c[v]=1;printf(“%d\n”,v);

q[++r]=v;}p=p->next;}}}ADCBEGF圖G的廣度遍歷6/22/2024305.3.3圖的遍歷應用舉例1.圖的連通性問題2.生成樹和生成森林6/22/2024311.圖的連通性問題若圖是非連通圖，則在travergraph算法中需要多次調用dfs或bfs,于是可在travergraph算法中設一變量COUNT記錄下dfs或bfs調用了多少次。根據(jù)count的值即可判斷圖的聯(lián)通性ADCBEGF6/22/2024322.生成樹和生成森林生成樹:是圖的一個極小連通子圖，它包含圖中全部n個頂點和保證使任意兩個頂點連通所需的n-1條邊。ADCBEADCBE圖G圖G的生成樹6/22/2024332.生成樹和生成森林生成森林:遍歷過程得到多棵生成樹ADCBEADCBE圖G圖G的生成森林GFHGFH6/22/2024345.4無向連通網(wǎng)的最小生成樹5.4.1最小生成樹的概念在無向連通網(wǎng)所有可能的生成樹中，邊的權值總和最小的那棵生成樹稱為最小生成樹。6/22/2024355.4.2Prim算法Prim算法思想6/22/202436Prim算法（續(xù)）為了實現(xiàn)Prim算法，需設一個輔助數(shù)組closedge以記錄每次選擇的權值最小的邊。數(shù)組元素closedge[i]對應于序號為i的頂點vi，它包含兩個域adjvex和lowcost。若vi已在生成樹上，則置closedge[i].lowcost=0；若頂點vi不在生成樹上，用closedge[i].lowcost存放vi與生成樹上的頂點構成的最小代價邊的權值，而用closedge[i].adjvex存放該邊所關聯(lián)的生成樹上的另一頂點的序號。6/22/202437Prim算法（續(xù)）設有n個頂點的無向連通網(wǎng)以鄰接矩陣g存儲，從序號為k的頂點vk開始構造最小生成樹，則輔助數(shù)組的初始情況為：

closedge[k].lowcost=0;

closedge[i].lowcost=g.adjmatrix[k,i](i≠k且1≤i≤n)

closedge[i].adjvex=k;(i≠k且1≤i≤n)假設k=1,則初始值如下表：closedge234567UV-Uvexlowcost13121419916199{v1}{v2v3v4v5v6v7}6/22/2024385.4.2Prim算法(執(zhí)行過程）closedge234567UV-Uvexlowcost13121419916199{v1}{v2v3v4v5v6v7}vexlowcoat3110313316199{v1,v3}{v2v4v5v6v7}vexlowcost3010313316199{v1,v3,v2}{v4v5v6v7}vexlowcost3010303316199{v1,v3,v2,v4}{v5v6v7}vexlowcost301030304345{v1,v3,v2,v4,v5}{v6v7}vexlowcost301030304045{v1,v3,v2,v4,v5v6}{v7}vexlowcost301030304040{v1v2v3v4v5v6v7}{}6/22/2024395.4.2Prim算法prim算法的時間復雜度為O(n2)，適合于求稠密網(wǎng)的最小生成樹Prim算法的實現(xiàn)6/22/2024405.4.3Kruskal算法Kruskal算法思想時間復雜度主要與網(wǎng)中邊的條數(shù)e相關為O(eloge)6/22/2024415.5有向網(wǎng)的最短路徑5.5.1單源最短路徑從某點出發(fā)到圖中其余各頂點的最短路徑：6/22/2024425.5.1單源最短路徑求單源最短路徑的Dijkstra算法：①首先引進輔助數(shù)組Dist[n+1]，它的每個分量Dist[i]代表從起點v1到vi的最短路徑長度；若不能到達則為∞。②第一條路徑顯然是以Dist[i]最小的結點作為終點；將i結點加入已選結點中，那下一條邊呢？③若Dist[i]+(vi,vk)<Dist[k],k是尚未加入的結點，則修改Dist[k]=Dist[i]+(vi,vk)；重復第二步，直到n-1次6/22/2024436/22/2024445.5.1單源最短路徑(續(xù))i123456Pre[i]0015146/22/2024455.5.1單源最短路徑從vi到其他頂點最短路徑過程演示,用pre數(shù)組記錄路徑。6/22/2024465.5.1單源最短路徑dijkstra*/算法實現(xiàn)6/22/2024475.6有向無環(huán)圖及其應用

5.6.1有向無環(huán)圖的概念有向無環(huán)圖（directedacyclinegraph）是指無環(huán)的有向圖，簡稱為DAG圖6/22/2024485.6.2AOV網(wǎng)與拓撲排序AOV網(wǎng)有向圖中用頂點表示活動,用表示活動間的優(yōu)先關系。如下圖：6/22/2024495.6.2AOV網(wǎng)與拓撲排序有向圖拓撲排序的算法描述如下：①從圖中選擇一個入度為0的頂點，輸出該頂點；②在圖中刪除該頂點及相關的弧，調整被刪除弧的弧頭的入度（入度-1）；③重復執(zhí)行①、②直到所有頂點均被輸