【正文】 輸入結(jié)點(diǎn)數(shù) (n)和邊數(shù) (e):\n”)。 scanf(“%d,%d”,amp。n,amp。e)。 for(i=1。i=n。i++) { printf(“\n請輸入第 %d個頂點(diǎn)信息： ” ,i)。 scanf(“%c”,amp。g[i].data)。 g[i].link=NULL。 } for(i=1。i=e。i++) 產(chǎn)生無向圖的鄰接表算法 (續(xù) ) { printf(“\n請輸入第 %d條邊起點(diǎn)序號 ， 終點(diǎn)序號： ” ,i)。 scanf(“%d,%d”,amp。s,amp。d)。 p=(struct edgenode *)malloc(sizeof(edgenode))。 p→adjvex=d 。 /*鄰接點(diǎn)序號為 d*/ p→next=g[s] .link。 g[s].link=p。 /*將新結(jié)點(diǎn)插入頂點(diǎn) Vs邊表的頭部 */ p=(struct edgenode *)malloc(sizeof(edgenode))。 p→adjvex=s 。 /*鄰接點(diǎn)序號為 s*/ p→next=g[d] .link。 g[d].link=p。 /*將新結(jié)點(diǎn)插入頂點(diǎn) Vd邊表的頭部 */ } } 返回 對有向圖 , 也可采用十字鏈表法 4. 鄰接多重表存儲法 用于無向圖 圖的遍歷 ? 1。 深度優(yōu)先搜索 (DFS) ? 首先訪問圖中某指定起始點(diǎn) Vi ，然后由 Vi出發(fā)訪問它的任一相鄰接頂點(diǎn) Vj，再從 Vj出發(fā)訪問 Vj的任一未訪問過的相鄰接頂點(diǎn) Vk，再從 Vk出發(fā)進(jìn)行類似訪問，如此進(jìn)行下去，直到某頂點(diǎn)已沒有未被訪問過的相鄰接頂點(diǎn)時，則退回一步，退到前一個頂點(diǎn)，找前一個頂點(diǎn)的其它尚未被訪問的相鄰接頂點(diǎn)。 ? 如有未訪問過的相鄰接頂點(diǎn)，則訪問此頂點(diǎn)后，再從該頂點(diǎn)出發(fā)向前進(jìn)行與前述類似的訪問； ? 如退回一步后，前一頂點(diǎn)也沒有未被訪問過的相鄰接頂點(diǎn)，則再向回退一步進(jìn)行搜索，重復(fù)上述過程，一直到所有頂點(diǎn)均被訪問過為止。 圖 圖的遍歷例子 ⑤ ⑥ ⑧ ④ ① ⑦ ② ③ ?由于圖中的路徑可能有環(huán)路，為了避免重復(fù)訪問某些頂點(diǎn)，設(shè)計圖的搜索算法時，可設(shè)置一個表示頂點(diǎn)是否被訪問過的輔助數(shù)組 visited，初始時將數(shù)組元素置零，一旦某頂點(diǎn) Vi被訪問過，則令visited[Vi ]=1，以后此頂點(diǎn)即不再訪問。 鄰接表表示的圖的 DFS算法 adjlist為鄰接表 ， 從 v0開始 深度優(yōu)先 遍歷 void DFStraverse(adjlist) { for(i=0。 in。 i++) visited[i]=0。 /*給 visited數(shù)組賦初值 */ for(i=0。 in。 i++) if(visited[i]==0) dfs(adjlist, vi)。 } adjlist為鄰接表 ， 從 v0開始 深度優(yōu)先 遍歷的 遞歸 算法 void dfs(adjlist , v0) { visited[v0]=1。 visit(adjlist[v0].vexdata)。 /*訪問 v0 p=adjlist[v0].firstarc。 /*P為 v0的鄰接結(jié)點(diǎn) while(p!=NULL) { if(visited[p→vertex]== 0) dfs(adjlist, p→vertex) 。 /*從 v未訪問的鄰接點(diǎn)出發(fā)進(jìn)行 DFS*/ p=p→next 。 } } 時間復(fù)雜性分析 ?一個有 n個頂點(diǎn)、 e條邊的圖，在深度優(yōu)先搜索圖的過程中，找鄰接點(diǎn)所需時間為 O(e)。 ?對輔助數(shù)組初始化時間為 O(n)。 ?因此，當(dāng)用鄰接表作為圖的存儲結(jié)構(gòu)時，深度優(yōu)先搜索圖的時間復(fù)雜性為 O(e+n)。 非遞歸算法 ?從頂點(diǎn) Vi出發(fā)進(jìn)行深度優(yōu)先遍歷的遞歸過程也可以寫成非遞歸的形式，此時需借助一個堆棧保存被訪問過的結(jié)點(diǎn)，以便回溯時查找已被訪問結(jié)點(diǎn)的未被訪問過的鄰接點(diǎn)。 ?設(shè)堆棧由一個一維數(shù)組構(gòu)成，數(shù)組名為stack，棧頂指針為 top ,假設(shè)此數(shù)組足夠大 ,不必考慮溢出的可能。 深度優(yōu)先非遞歸算法 void dfs(adjlist， v0) /*adjlist為鄰接表 ,從 v0開始 { …… visited[ ]=0。 top=1。 visit(adjlist[v0].vexdata)。 visited[v0]=1。 /*visited[]:訪問標(biāo)記 P=adjlist[v0].firstarc。 /*p臨時變量 do { while (p!=null) { v=pvertex。 if (visited[v]==0) /*若 v未訪問 { stack[++top] =pnext。 visit(adjlist[v]. vexdata)。 visited[v]=1。 p=adjlist[v].firstarc。 } else p=pnext。 } if (top!=1) p=stack[top]。 } while ((p!=null) or (top!=1)) /*為真返回 , } /*為假結(jié)束 2. 廣度優(yōu)先搜索 (BFS) ?圖的廣度優(yōu)先搜索（ BFS）類似于樹的按層次遍歷。 ?廣度優(yōu)先搜索的基本思想是：首先訪問圖中某指定的起始點(diǎn) Vi并將其標(biāo)記為已訪問過，然后由 Vi出發(fā)訪問與它相鄰接的所有頂點(diǎn) Vj、 Vk…… ，并均標(biāo)記為已訪問過，然后再按照Vj、 Vk…… 的次序，訪問每一個頂點(diǎn)的所有未被訪問過的鄰接頂點(diǎn)，并均標(biāo)記為已訪問過，下一步再從這些頂點(diǎn)出發(fā)訪問與它們相鄰接的尚未被訪問的頂點(diǎn)，如此做下去，直到所有的頂點(diǎn)均被訪問過為止。 ?在廣度優(yōu)先搜索中，若對頂點(diǎn) V1的訪問先于頂點(diǎn) V2的訪問，則對 V1鄰接頂點(diǎn)的訪問也先于 V2鄰接頂點(diǎn)的訪問。就是說廣度優(yōu)先搜索中對鄰接點(diǎn)的尋找具有“先進(jìn)先出”的特性。因此，為了保證訪問頂點(diǎn)的這種先后關(guān)系，需借助一個隊(duì)列暫存那些剛訪問過的頂點(diǎn)。 ?設(shè)此隊(duì)列由一個一維數(shù)組構(gòu)成，數(shù)組名為Queue，隊(duì)首指針和隊(duì)尾指針分別為 front和rear。假設(shè)數(shù)組足夠大，不必考慮有溢出的可能性。 ?廣度優(yōu)先搜索不是遞歸過程，不能用遞歸形式。 BFS算法描述 BFS(v0) { 訪問 v0頂點(diǎn)； visited[v0]=1。 被訪問過的頂點(diǎn)入隊(duì)； 當(dāng)隊(duì)列非空時 ， 進(jìn)行下面的循環(huán) { （ 1） 被訪問過的頂點(diǎn)出隊(duì)； （ 2） 對所有與該頂點(diǎn)相鄰接的頂點(diǎn) w if (visited[w]==0) { (a)訪問 w頂點(diǎn)； (b)visited[w]=1。 (c)w入隊(duì) 。 } } } 鄰接表表示的圖的 BFS算法 int visited[MAXVEX]。 int queue[MAXVEX]。 void bfs(adjlist adj,int v) { int front=0,rear=1,v。 struct edgenode *p。 visited[v]=1。 printf(“%d”,v)。 queue[rear]=v。 /*初始頂點(diǎn)入隊(duì) */ while(front!=rear) /*隊(duì)列不為空 */ 鄰接表表示的圖的 BFS算法 (續(xù) ) { front=front+1。 v=queue[front]。 /*按訪問次序出隊(duì)列 */ p=adj[v]link。 /*找 v的鄰接頂點(diǎn) */ while(p!=NULL) { if (visited[padjvex]==0) { visited[padjvex]=1。 printf(“%d”,padjvex)。 鄰接表表示的圖的 BFS算法續(xù) rear=rear+1。 queue[rear]=padjvex。 } p=pnext。 } } } 時間復(fù)雜性分析 ?一個有 n個頂點(diǎn)、 e條邊的圖，在廣度優(yōu)先搜索圖的過程中，每個頂點(diǎn)至多進(jìn)一次隊(duì)列，圖的搜索過程實(shí)質(zhì)上是通過邊來找頂點(diǎn)的過程，找鄰接點(diǎn)所需時間為 O(e