數(shù)據(jù)結(jié)構(gòu)教學(xué)課件：第七講2圖

1、n7.2 圖的存儲(chǔ)結(jié)構(gòu)u多重鏈表例G12413例15324G2V1V2 V4 V3 V1 V2 V4 V5 V3u鄰接矩陣表示頂點(diǎn)間相聯(lián)關(guān)系的矩陣F定義：設(shè)G=(V,E)是有n1個(gè)頂點(diǎn)的圖，G的鄰接矩陣A是具有以下性質(zhì)的n階方陣，其它0E(G)v,v或)v,(v若1,jijijiA例G12413例15324G200110001011101010101010100001100000000110F特點(diǎn)： 無(wú)向圖的鄰接矩陣對(duì)稱，可壓縮存儲(chǔ)；有n個(gè)頂點(diǎn)的無(wú)向圖需存儲(chǔ)空間為n(n+1)/2 有向圖鄰接矩陣不一定對(duì)稱；有n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為n 無(wú)向圖中頂點(diǎn)Vi的度TD(Vi)是鄰接矩陣A中第i行元

2、素之和 有向圖中，頂點(diǎn)Vi的出度是A中第i行元素之和頂點(diǎn)Vi的入度是A中第i列元素之和 網(wǎng)絡(luò)的鄰接矩陣可定義為：，其它0E(G)v,v或)v,(v若,jijiijjiA0618360240120078400530750例1452375318642u鄰接表F實(shí)現(xiàn)：為圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊（有向圖中指以Vi為尾的?。﹖ypedef struct node int adjvex; /鄰接點(diǎn)域，存放與Vi鄰接的點(diǎn)在表頭數(shù)組中的位置 struct node *next; /鏈域，指示下一條邊或弧JD;adjvex next表頭結(jié)點(diǎn)：typedef stru

3、ct tnode int vexdata; /存放頂點(diǎn)信息 struct node *firstarc; /指示第一個(gè)鄰接點(diǎn)TD;TD gaM; /ga0不用vexdata firstarc例G1bdac例aecbdG21234acdbvexdata firstarc 3 2 4 1adjvex next1234acdbvexdata firstarc 4 2 1 2adjvex next5e 4 3 5 1 5 3 2 3F特點(diǎn) 無(wú)向圖中頂點(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ù) 逆鄰接表：有向圖

4、中對(duì)每個(gè)結(jié)點(diǎn)建立以Vi為頭的弧的單鏈例G1bdac1234acdbvexdata firstarc 4 1 1 3adjvex nextn7.3 圖的遍歷u深度優(yōu)先遍歷(DFS)F方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問(wèn)此頂點(diǎn)；然后依次從V0的未被訪問(wèn)的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點(diǎn)都被訪問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未被訪問(wèn)的頂點(diǎn)作起點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)為止V1V2V4V5V3V7V6V8例深度遍歷：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍歷：V1 V2

5、 V4 V8 V5 V6 V3 V7深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8例深度遍歷：V1 V2 V4 V8 V3 V6 V7 V5u廣度優(yōu)先遍歷(BFS)F方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問(wèn)此頂點(diǎn)后，依次訪問(wèn)V0的各個(gè)未曾訪問(wèn)過(guò)的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未被訪問(wèn)的頂點(diǎn)作起點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)為止V1V2V4V5V3V7V6V8例廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8廣度遍歷：V1 V2 V3 V4 V5