這篇文章給大家分享的是有關(guān)C語(yǔ)言中如何尋找無(wú)向圖兩點(diǎn)間的最短路徑的內(nèi)容。小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過(guò)來(lái)看看吧。

十余年建站經(jīng)驗(yàn)， 網(wǎng)站建設(shè)、成都做網(wǎng)站客戶的見(jiàn)證與正確選擇。成都創(chuàng)新互聯(lián)提供完善的營(yíng)銷(xiāo)型網(wǎng)頁(yè)建站明細(xì)報(bào)價(jià)表。后期開(kāi)發(fā)更加便捷高效，我們致力于追求更美、更快、更規(guī)范。

1.簡(jiǎn)介

無(wú)向圖是圖結(jié)構(gòu)的一種。本次程序利用鄰接表實(shí)現(xiàn)無(wú)向圖，并且通過(guò)廣度優(yōu)先遍歷找到兩點(diǎn)之間的最短路徑。

2.廣度優(yōu)先遍歷

廣度優(yōu)先遍歷(BFS)和深度優(yōu)先遍歷(DFS)是圖結(jié)構(gòu)中最常用的遍歷方式。其中廣度優(yōu)先遍歷配合上隊(duì)列能夠找到兩點(diǎn)之間的最短路徑，同時(shí)也能解決一些其他的問(wèn)題(比如尋找迷宮的最短逃離路線)。廣度優(yōu)先遍歷尋找兩點(diǎn)之間最短路徑的操作分為以下幾步: 

1）.首先定義起始點(diǎn)和終點(diǎn)src和dst。接著定義一個(gè)數(shù)組distance[ ]，用于存放各點(diǎn)到src的距離。初始化時(shí)各點(diǎn)到src的距離是INF(表示正無(wú)窮。這里可自行定義，作用是表示還未得到該結(jié)點(diǎn)到src的距離)，而distance[src] = 0。然后將src放入隊(duì)列。

2）.取出隊(duì)列的第一個(gè)結(jié)點(diǎn)(一開(kāi)始隊(duì)列只有src，這里就是取出src)放在變量top中；

3）.獲得該結(jié)點(diǎn)的所有鄰接結(jié)點(diǎn)，并且判斷distance[ ]數(shù)組中各個(gè)鄰接結(jié)點(diǎn)是否為INF。如果是說(shuō)明還沒(méi)有訪問(wèn)過(guò)該結(jié)點(diǎn)則將distance[ ]相應(yīng)的位置設(shè)定為distance[top] + 1。如果不為INF，則表示之前已經(jīng)訪問(wèn)過(guò)了，因此跳過(guò)。

4）.重復(fù)2-3步直到top變量等于dst為止?；蛘咭恢钡疥?duì)列為空，這種情況下說(shuō)明兩點(diǎn)間不存在路徑。

總結(jié)起來(lái)就是將結(jié)點(diǎn)從src開(kāi)始按順序放進(jìn)隊(duì)列中，而已經(jīng)放進(jìn)過(guò)隊(duì)列的結(jié)點(diǎn)會(huì)被標(biāo)識(shí)，因此不會(huì)重復(fù)放進(jìn)隊(duì)列，直到找到dst為止。這種方法得到的路徑一定時(shí)最短路勁。 

3.輸出最短路徑

上面使用廣度優(yōu)先遍歷找到的是兩點(diǎn)之間最短路徑的長(zhǎng)度，并且存儲(chǔ)在了distance[dst]中，而如果要輸出這條最短路徑有不同的方法。本人這里使用的方法是先將dst壓入棧中，然后通過(guò)遍歷dst的鄰接結(jié)點(diǎn)中有哪一個(gè)結(jié)點(diǎn)在distance數(shù)組中的值是distance[dst] - 1，找到后壓入棧中。接著繼續(xù)尋找再前一個(gè)結(jié)點(diǎn)，同樣壓入棧中。循環(huán)該操作最后找到src，然后將棧中的元素依次pop出來(lái)。因?yàn)闂Ｏ冗M(jìn)后出的性質(zhì)，便能夠得到該條路徑。 

4.代碼實(shí)現(xiàn)

具體的代碼如下

#ifndef _GRAPH_H
#define _GRAPH_H
 
#include <stack>
#include <iostream>
#include <queue>
 
#define ERROR   -1
#define V_E_INFO  1
#define FIND    1
#define PATH    2
#define MAX     100
 
using namespace std;
 
 
 
class ArcNode
{
  private:
    int value;
    ArcNode *next;
  
  public:
    ArcNode(int , ArcNode * = nullptr);
    void set_next(ArcNode *);
    ArcNode *get_next() const;
    int get_value() const;
    void set_value(int);
};
 
 
 
class List
{  
  private:
    int value;
    ArcNode *firstnode;
  public:
    List(int = 0,ArcNode * = nullptr);
    ~List();
    ArcNode *Pop();
    void Push(int);
    int get_value() const;
    int is_exist(int) const;
    ArcNode *get_firstnode() const;
    void set_value(int);
    void dfs_find_path() const;
    void set_firstnode(ArcNode *);
    void print() const;
};
 
 
 
class Graph
{    
  private:
    List list[MAX];
    int vertices_num;
    int edge_num;
  
  public:
    Graph(int,int,int []);
    ~Graph();
    int get_vertices_num() const;
    int get_edge_num() const;
    List *get_list(int);
    void print() const;
    void dfs_print_path(int,int) const;
    void dfs_find_path(int,int,int [],stack<int> & ,int &) const;
    void dfs(int src,int visited[],int &count) const;
    void dfs_print(int) const;
    void dfs_non_recursive() const;
    int find_shortest_path(int,int) const;
    void dfs(int,int []) const;
};
 
#endif

BFS找尋最短路徑代碼：

int Graph::find_shortest_path(int src,int dst) const
{
  queue<int> myQ;
 
  int value[vertices_num];/用于存放各點(diǎn)到src的距離
  int head = 0;
  int output[10];
  for(int i = 0;i < vertices_num;i++)
  {
    value[i] = -1;//-1表示還沒(méi)有訪問(wèn)過(guò)該結(jié)點(diǎn)
  }
 
  value[src] = 0;
  myQ.push(src);
 
  while(myQ.size())
  {
    head = myQ.front();
    myQ.pop();
    if(head == dst)
    {
      int find = dst;
      stack<int> myS;
      myS.push(dst);
      while(find != src)
      {  
        for(int j = 0; j < vertices_num; j++)
        {
          if((list[j].is_exist(find) == 1) && (value[find] == value[j] + 1))
          {
            myS.push(j);
            find = j;
            break;
          }
        }
      }
      int count = myS.size();
      for(int j = 0;j < count;j++)
      {
        if(j == count - 1)
          cout << myS.top() << endl;
        else
        {
          cout << myS.top() << "-";
          myS.pop();
        }
      }
    
      return FIND;
    }
    
    ArcNode *a = list[head].get_firstnode();
    while( a != nullptr)
    {
      if(value[a -> get_value()] == -1)
      {
        value[a -> get_value()] = value[head] + 1;
        myQ.push(a -> get_value());
      }
      a = a -> get_next();
    }
  }
  cout << "Error: no path between " << src << " and " << dst << endl;
  return ERROR;
}

感謝各位的閱讀！關(guān)于“C語(yǔ)言中如何尋找無(wú)向圖兩點(diǎn)間的最短路徑”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！

本文題目：C語(yǔ)言中如何尋找無(wú)向圖兩點(diǎn)間的最短路徑
網(wǎng)頁(yè)URL：http://www.rwnh.cn/article36/jdiisg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、、企業(yè)建站、外貿(mào)網(wǎng)站建設(shè)、自適應(yīng)網(wǎng)站、網(wǎng)站收錄

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)