數(shù)據(jù)結(jié)構(gòu)第章習(xí)題答案-資料下載頁
2025-06-07 19:56本頁面
【正文】 if([i][j].adj) { [i][j].adj=0。 。 } return OK。 }//Delete_Arc 3. 【③】試基于圖的深度優(yōu)先搜索策略寫一算法，判別以鄰接表方式存儲的有向圖中是否存在由頂點vi到頂點vj的路徑（i≠j）。注意：算法中涉及的圖的基本操作必須在此存儲結(jié)構(gòu)上實現(xiàn)。int visited[MAXSIZE]。 //指示頂點是否在當(dāng)前路徑上 int exist_path_DFS(ALGraph G,int i,int j)//深度優(yōu)先判斷有向圖G中頂點i到頂點j 是否有路徑,是則返回1,否則返回0 { if(i==j) return 1。 //i就是j else { visited[i]=1。 for(p=[i].firstarc。p。p=pnextarc) { k=padjvex。 if(!visited[k]amp。amp。exist_path(k,j)) return 1。//i下游的頂點到j(luò)有路徑 }//for }//else }//exist_path_DFS 解2：（以上算法似乎有問題：如果不存在路徑，則原程序不能返回0。我的解決方式是在原程序的中引入一變量level來控制遞歸進(jìn)行的層數(shù)。具體的方法我在程序中用紅色標(biāo)記出來了。）int visited[MAXSIZE]。 //指示頂點是否在當(dāng)前路徑上 int level＝1。//遞歸進(jìn)行的層數(shù)int exist_path_DFS(ALGraph G,int i,int j)//深度優(yōu)先判斷有向圖G中頂點i到頂點j 是否有路徑,是則返回1,否則返回0 { if(i==j) return 1。 //i就是j else { visited[i]=1。 for(p=[i].firstarc。p。p=pnextarc，level) { level++。 k=padjvex。 if(!visited[k]amp。amp。exist_path(k,j)) return 1。//i下游的頂點到j(luò)有路徑 }//for }//else if (level==1) return 0。}//exist_path_DFS 附加題：【④】采用鄰接表存儲結(jié)構(gòu)，編寫一個判別無向圖中任意給定的兩個頂點之間是否存在一條長度為k的簡單路徑的算法。（注1：一條路徑為簡單路徑指的是其頂點序列中不含有重現(xiàn)的頂點。注2：此題可參見嚴(yán)題集P207208中有關(guān)按“路徑”遍歷的算法基本框架。）int visited[MAXSIZE]。 int exist_path_len(ALGraph G,int i,int j,int k)//判斷鄰接表方式存儲的有向圖G 的頂點i到j(luò)是否存在長度為k的簡單路徑 { { if(i==jamp。amp。k==0) return 1。 //找到了一條路徑,且長度符合要求 else if(k0) { visited[i]=1。 for(p=[i].firstarc。p。p=pnextarc) { l=padjvex。 if(!visited[l]) if(exist_path_len(G,l,j,k1)) return 1。 //剩余路徑長度減一 }//for visited[i]=0。 //本題允許曾經(jīng)被訪問過的結(jié)點出現(xiàn)在另一條路徑中 }//else return 0。 //沒找到 }//exist_path_len9
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1