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;}; #endifBFS找尋最短路徑代碼：
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;}以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持武林網(wǎng)。
新聞熱點(diǎn)
疑難解答
圖片精選
