數(shù)據(jù)結(jié)構(gòu)作業(yè)系統(tǒng)第七章答案-資料下載頁
2025-06-22 15:17本頁面
【正文】 v=finished[i]。 if(!visited[v]) { DFS2(dig,v,scc,n,k)。 n++。 } }}void DFS1(OLGraph dig,int v){ int w。 ArcBox *p。 visited[v]=1。 for(p=[v].firstout。p。p=ptlink) { w=pheadvex。 if(!visited[w]) DFS1(dig,w)。 } finished[count++]=v。 }void DFS2(OLGraph dig,int v,StrARR amp。scc,int j,int k) { int w。 ArcBox *p。 visited[v]=1。 scc[j][k++]=[v].data。 for(p=[v].firstin。p。p=phlink) { w=ptailvex。 if(!visited[w]) DFS2(dig,w,scc,j,k)。 }}⑤ 試寫一個(gè)算法，在以鄰接矩陣方式存儲(chǔ)的有向圖G中求頂點(diǎn)i到頂點(diǎn)j的不含回路的、長度為k的路徑數(shù)。 實(shí)現(xiàn)下列函數(shù)：int SimplePath(MGraph G, int i, int j, int k)。/* 求有向圖G的頂點(diǎn)i到j(luò)之間長度為k的簡單路徑條數(shù) */圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)的類型定義如下：typedef enum {DG,DN,AG,AN} GraphKind。 // 有向圖,有向網(wǎng),無向圖,無向網(wǎng)typedef struct { VRType adj。 // 頂點(diǎn)關(guān)系類型。對(duì)無權(quán)圖，用1(是)或0(否)表示相鄰否； // 對(duì)帶權(quán)圖，則為權(quán)值類型 InfoType *info。 // 該弧相關(guān)信息的指針(可無)}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。typedef struct { AdjMatrix arcs。 // 鄰接矩陣 VertexType vexs[MAX_VERTEX_NUM]。 // 頂點(diǎn)向量 int vexnum,arum。 // 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) GraphKind kind。 // 圖的種類標(biāo)志}MGraph。int SimplePath(MGraph G, int i, int j, int k)/* 求有向圖G的頂點(diǎn)i到j(luò)之間長度為k的簡單路徑條數(shù) */{ int sum=0,v。 if( [i][j].adj amp。amp。k==1 amp。amp。 !visited[j]) sum=1。 else if(k1) { visited[i]=1。 for(v=0。v。v++) { if([i][v].adj amp。amp。 !visited[v]) sum+=SimplePath(G,v,j,k1)。 } visited[i]=0。 } return sum。}實(shí)現(xiàn)下列函數(shù)：int Search(SSTable s, KeyType k)。/* Index the element which key is k *//* in StaticSearchTable s. *//* Return 0 if x is not found. */靜態(tài)查找表的類型SSTable定義如下：typedef struct { KeyType key。 ... ... // 其他數(shù)據(jù)域} ElemType。typedef struct { ElemType *elem。 int length。} SSTable。int Search(SSTable a, KeyType k)/* Index the element which key is k *//* in StaticSearchTable s. *//* Return 0 if x is not found. */{ int i。 for(i=1。i=。i++) if([i].key==k)return i。 return 0。}
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1