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