C語言怎么遍歷鄰接表簡單路徑

這篇“C語言怎么遍歷鄰接表簡單路徑”文章的知識點(diǎn)大部分人都不太理解，所以小編給大家總結(jié)了以下內(nèi)容，內(nèi)容詳細(xì)，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“C語言怎么遍歷鄰接表簡單路徑”文章吧。

題目：

假設(shè)圖用鄰接表表示，設(shè)計一個算法，輸出從頂點(diǎn)Vi到Vj的所有簡單路徑

關(guān)鍵字： 圖，鄰接表，簡單路徑

思路：

Vi=u,Vj=v

本題采用基于遞歸的深度優(yōu)先遍歷算法，從結(jié)點(diǎn)u出發(fā)，遞歸深度優(yōu)先遍歷圖中各個結(jié)點(diǎn)，若訪問到結(jié)點(diǎn)v，則輸出該搜索路徑上的結(jié)點(diǎn)。

為此，設(shè)置：一個path數(shù)組來存放路徑上的結(jié)點(diǎn)（初始為空），d表示路徑長度（初始為-1）。

查找從頂點(diǎn)u到v 的簡單路徑過程說明如下

（假設(shè)查找函數(shù)名為FindPath（））：

1）FindPath(G,u,v,path,d):

d++;path[d]=u;

若找到u的未訪問過的相鄰結(jié)點(diǎn)u1，則繼續(xù)下去，

否則置visited[u]=0并返回。

2）FindPath（G,u1,v,path,d）:

d++;path[d]=u1;

若找到u1的未訪問過的相鄰結(jié)點(diǎn)u2，則繼續(xù)下去，

否則置visited[u1]=0并返回。

3）以此類推，繼續(xù)上述遞歸過程，直到ui=v,輸出path

代碼：

void FindPath (AGraph *G,int u,int v,int path[],int d){
      int w;//w是每一次遍歷中，當(dāng)前結(jié)點(diǎn)的下一個鄰接頂點(diǎn)的代表變量
      ArcNode*p;
      d++;//路徑長度增加1
      path[d]=u;//將當(dāng)期頂點(diǎn)添加到路徑中
      visited[u]=1;//設(shè)置已訪問結(jié)點(diǎn)
      if(u==v)//找到一條路徑則輸出
           print(path[]);//輸出路徑上的結(jié)點(diǎn)
      p=G->adjlist[u].firstarc;//p指向u的第一個相鄰點(diǎn)
      while(p!=NULL){     //遍歷u的所有相鄰點(diǎn)
        w=p->adjvex;//w為下一個鄰接頂點(diǎn)
        if(visited[w]==0)//若頂點(diǎn)w未訪問，遞歸訪問它
           FindPath(G,w,V,path,d);
        p=p->nextarc;//p指向u的下一個相鄰點(diǎn)
      }
      visited[u]=0;//恢復(fù)環(huán)境，使該頂點(diǎn)可重新使用
  }

以上就是關(guān)于“C語言怎么遍歷鄰接表簡單路徑”這篇文章的內(nèi)容，相信大家都有了一定的了解，希望小編分享的內(nèi)容對大家有幫助，若想了解更多相關(guān)的知識內(nèi)容，請關(guān)注億速云行業(yè)資訊頻道。