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

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

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

3、ct tnode int vexdata; /存放頂點信息 struct node *firstarc; /指示第一個鄰接點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特點 無向圖中頂點Vi的度為第i個單鏈表中的結(jié)點數(shù) 有向圖中頂點Vi的出度為第i個單鏈表中的結(jié)點個數(shù)頂點Vi的入度為整個單鏈表中鄰接點域值是i的結(jié)點個數(shù) 逆鄰接表：有向圖

4、中對每個結(jié)點建立以Vi為頭的弧的單鏈例G1bdac1234acdbvexdata firstarc 4 1 1 3adjvex nextn7.3 圖的遍歷u深度優(yōu)先遍歷(DFS)F方法：從圖的某一頂點V0出發(fā)，訪問此頂點；然后依次從V0的未被訪問的鄰接點出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問為止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方法：從圖的某一頂點V0出發(fā)，訪問此頂點后，依次訪問V0的各個未曾訪問過的鄰接點；然后分別從這些鄰接點出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點的鄰接點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問為止V1V2V4V5V3V7V6V8例廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8廣度遍歷：V1 V2 V3 V4 V5