0

我有一个包含交叉口（ID 安全名称）和街道（Intersection1 Intersection2 距离）的数据文件，如图所示：

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 程序应搜索提供的图形以找到满足以下要求的慢跑路径： 路径必须在用户指定的起始交点指示的同一交叉点（即顶点）处开始和结束。该路径不应重新访问任何交叉路口。换句话说，任何顶点都不应该在路径中出现两次。路径的总距离应在用户指定距离目标的 1 英里范围内。

慢跑路径安全

safejogger 程序应该计算慢跑路径的两个统计数据，包括： 平均路径安全：慢跑路径内所有交叉口的平均安全指数。最小路径安全：慢跑路径内所有路口的最小安全指数。

4

1 回答 1

0

如果要在图上实现 DFS，则需要一种方法来标记已访问过的顶点。您可以更改顶点结构以包含标志，或者使用单独的位向量将所有标志重新组合在一起。

对于 DFS 算法，它非常简单：

  • 你标记你开始的顶点，
  • 你跟随每一个边缘离开它，
  • 如果尚未标记结束顶点，则递归运行 DFS 算法。

这就是底线。您可以使用堆栈将该算法转换为循环（而不是递归）。

在你的任务中，你必须在 DFS 的每一步都做一些事情，所以你需要弄清楚如何做这些额外的事情。提示：创建一个在图上执行 DFS 工作的类，并派生该类以实现额外的东西。

您的问题的第二部分不是关于 DFS，而是关于处理搜索结果，一条慢跑路径，它是一个顶点列表。

于 2012-12-05T18:20:28.060 回答