C語(yǔ)言算法積累圖的遍歷鄰接表簡(jiǎn)單路徑

更新時(shí)間：2022年06月06日 17:06:56 作者：aprilzj123

這篇文章主要為大家介紹了C語(yǔ)言算法積累圖的遍歷鄰接表簡(jiǎn)單路徑實(shí)現(xiàn)示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目：

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

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

思路：

Vi=u,Vj=v

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

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

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

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

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

d++;path[d]=u;

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

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

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

d++;path[d]=u1;

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

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

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

代碼：

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

以上就是C語(yǔ)言算法積累圖的遍歷鄰接表簡(jiǎn)單路徑的詳細(xì)內(nèi)容，更多關(guān)于C語(yǔ)言圖遍歷鄰接表簡(jiǎn)單路徑的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章:

相關(guān)文章

C語(yǔ)言如何輸出中文
這篇文章主要介紹了C語(yǔ)言如何輸出中文問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
2023-09-09
數(shù)組中求第K大數(shù)的實(shí)現(xiàn)方法
本篇文章是對(duì)數(shù)組中求第K大數(shù)的實(shí)現(xiàn)方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
2013-05-05
一文帶你了解Qt中槽的使用
這篇文章主要為大家詳細(xì)介紹了Qt中槽的使用教程，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)Qt有一定的幫助，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
2022-12-12
C語(yǔ)言實(shí)現(xiàn)制作通訊錄(新手推薦)
本文推薦給C語(yǔ)言學(xué)習(xí)到結(jié)構(gòu)體的新手們，供其練習(xí)。這篇文章主要是利用C語(yǔ)言制作一個(gè)簡(jiǎn)單的通訊錄功能，感興趣的小伙伴可以跟隨小編一起了解一下
2022-09-09
C/C++使用socket實(shí)現(xiàn)判斷ip是否能連通
這篇文章主要為大家詳細(xì)介紹了C/C++如何使用socket實(shí)現(xiàn)判斷ip是否能連通，文中的示例代碼講解詳細(xì)，具有一定的學(xué)習(xí)價(jià)值，感興趣的小伙伴可以了解一下
2023-07-07
C語(yǔ)言實(shí)現(xiàn)導(dǎo)航功能
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)導(dǎo)航功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2022-03-03
枚舉和宏的區(qū)別詳細(xì)解析
枚舉常量具有類型，但宏沒(méi)有類型，枚舉變量具有與普通變量相同的諸如作用域、值等性質(zhì)，但宏沒(méi)有，宏不是語(yǔ)言的一部分，它是一種預(yù)處理替換符
2013-09-09
C++內(nèi)存對(duì)齊的實(shí)現(xiàn)
本文主要介紹了C++內(nèi)存對(duì)齊的實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2023-02-02
C語(yǔ)言超全面define預(yù)處理指令的使用說(shuō)明
C語(yǔ)言里可以用#define定義一個(gè)標(biāo)識(shí)符來(lái)表示一個(gè)常量。特點(diǎn)是：定義的標(biāo)識(shí)符不占內(nèi)存，只是一個(gè)臨時(shí)的符號(hào)，預(yù)編譯后這個(gè)符號(hào)就不存在了，也不做類型定義。預(yù)編譯又叫預(yù)處理
2022-04-04
c語(yǔ)言中enum類型的用法案例講解
這篇文章主要介紹了c語(yǔ)言中enum類型的用法案例講解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是本文的詳細(xì)內(nèi)容,需要的朋友可以參考下
2021-07-07