使用深度優先搜索在C++圖表

我有數據的帶交叉點（ID安全名稱）和街道（Intersection1 Intersection2距離）作爲文件所示：使用深度優先搜索在C++圖表

INTERSECTIONS: 
198 0.8 alvemon and 28th 
199 0.6 alvemon and 29th 
200 0.8 alvemon and 30th 

STREETS: 
1 2 0.6 
2 3 0.1 
3 4 0.9

交點是頂點和街道邊緣。這裏是我的頭：頂點頭：

#ifndef VERTEX_H 
#define VERTEX_H 
#include<list> 
#include<string> 
#include "global.h" 

struct Vertex_{ 
int xsect; 
double danger; 
std::string xstreets; 

std::list<Edge> EdgeList; 
/*struct Vertex_ *next; 
struct Vertex_ *prev;*/ 
}; 

#endif

邊緣標題：

#ifndef EDGE_H 
#define EDGE_H 

#include "global.h" 
#include "vertex.h" 
struct Edge_{ 
Vertex *adjvertex; 
double distance; 

/*struct edge *next; 
struct edge *prev;*/ 
}; 

#endif

我這是圖了名單。我已經完成了所有設置，並且製作了街道/十字路口的圖形（或地圖）。我知道我需要使用深度優先搜索，因爲下面的需求，但不知道如何實現。如果有人能給我一個深度優先搜索的例子，那會很棒。現在我的任務需要我：

慢跑路徑要求

的safejogger程序應搜索提供的圖表找到慢跑符合下列要求的路徑：路徑必須啓動並在同一路口結束（即頂點）由用戶指定的startingIntersection指示。該路徑不應該重新訪問任何交叉點。換句話說，沒有頂點應該在路徑中出現兩次。該路徑距離用戶指定距離目標的距離應該在1英里以內。

慢跑道安全

的safejogger程序應該計算機二級統計慢跑路徑，包括：平均路徑安全：慢跑路徑內的所有路口的平均安全指數。最小路徑安全：慢跑路徑內所有路口的最小安全指數。

來源

2012-12-05 ddwong

您有問題要問？ –

是的。我如何在圖表中使用深度優先搜索？ – ddwong

如果圖形是圓形的，它不是簡單的DFS。你是否試圖在一定距離內計算所有慢跑路線都是最危險的？ – gvd

如果要實現在圖形上DFS，你需要一種方式來紀念已經訪問過的頂點。你可以改變你的頂點結構來包含一個標誌，或者有一個單獨的位向量，將所有的標誌重新組合在一起。

對於DFS算法，它是非常簡單的：

你記住你開始頂點，
您按照每條邊離開它，
如果最終頂點尚未標註，您遞歸地運行DFS算法。

這就是底線。您可以通過使用堆棧將該算法轉換爲循環（而不是遞歸）。

在你的任務，你將不得不在DFS的每一步做一些事情，所以你需要弄清楚如何做到這一點額外的東西。提示：創建一個在圖上執行DFS工作的類，並派生該類來實現額外的東西。

你問題的第二部分是不是DFS，而是關於處理您的搜索，慢跑路徑，這是頂點列表的結果。

來源

2012-12-05 18:20:28 didierc

使用深度優先搜索在C++圖表

回答

相關問題