0

次のように、交差点（ID安全名）と道路（交差点1交差点2の距離）を含むデータのファイルがあります。

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で示される同じ交差点（つまり頂点）で開始および終了する必要があります。パスは交差点を再訪してはいけません。つまり、パス内に頂点が2回表示されないようにする必要があります。パスの合計距離は、ユーザーが指定した距離目標から1マイル以内である必要があります。

ジョギングパスの安全性

safejoggerプログラムは、ジョギングパスに関する2つの統計を計算する必要があります。平均パス安全性：ジョギングパス内のすべての交差点の平均安全性指数。最小経路安全性：ジョギング経路内のすべての交差点の最小安全指数。

4

1 に答える 1

0

グラフに DFS を実装する場合は、既にアクセスした頂点をマークする方法が必要です。頂点構造体を変更してフラグを含めるか、すべてのフラグをまとめて再グループ化する個別のビット ベクトルを作成できます。

DFS アルゴリズムの場合は、非常に単純です。

  • 開始する頂点をマークし、
  • あなたはそれを残して各エッジをたどり、
  • 終了頂点がまだマークされていない場合は、DFS アルゴリズムを再帰的に実行します。

それがベースラインです。スタックを使用して、そのアルゴリズムを (再帰ではなく) ループに変えることができます。

あなたの課題では、DFS の各ステップで何かをしなければならないので、その追加作業を行う方法を理解する必要があります。ヒント: グラフで DFS を機能させるクラスを作成し、そのクラスを派生させて余分なものを実装します。

問題の 2 番目の部分は DFS に関するものではなく、検索結果の処理に関するものであり、頂点のリストであるジョギング パスです。

于 2012-12-05T18:20:28.060 に答える