我正在遍历一个我已经设置为类的图,使用向量来存储顶点和边 . 我在图表上使用深度优先搜索来显示遍历的路径,但我想以某种方式让我的代码按顺序显示顶点,顺序如下:
<u, i1, i2, ... v>
其中'u'和'v'是起始顶点(我希望它在相同的顶点开始和结束),'i'值是它沿途经过的顶点 .
到目前为止,这是DFS的功能,我已将其简化,以便将其用作一般参考 . 有什么我可以在这里修改,以便让它显示我想要的东西? (它目前没有设置显示任何内容) .
vector<Vertex*> vertices;
vector<Edge*> edges;
class Vertex {
public:
Vertex () {};
Vertex (int id, float safetyIndex, string name)
: id(id), safetyIndex(safetyIndex), name(name), previous(NULL), distFromStart(INT_MAX), color("white")
{
vertices.push_back(this);
}
public:
int id;
float safetyIndex;
string name;
int distFromStart;
Vertex* previous;
string color;
};
class Edge {
public:
Edge () {};
Edge (Vertex* intersection1, Vertex* intersection2, int distance)
: intersection1(intersection1), intersection2(intersection2), distance(distance)
{
edges.push_back(this);
}
bool street_connection(Vertex* intersection1, Vertex* intersection2)
{
return (
(intersection1 == this->intersection1 && intersection2 == this->intersection2) ||
(intersection1 == this->intersection2 && intersection2 == this->intersection1));
}
public:
Vertex* intersection1;
Vertex* intersection2;
int distance;
};
void pathFinder(Vertex* startVertex)
{
DFS_visit(startVertex);
}
void DFS_visit(Vertex* u)
{
u->color = "gray"; // Mark that we have visited intersection 'u'
// Create a vector containing all adjacent vertices to intersection 'u'
vector<Vertex*>* adjVertex = AdjVertices(u);
const int size = adjVertex->size();
for( int i=0; i<size; ++i)
{
Vertex* v = adjVertex->at(i);
if ( v->color == "white" )
{
DFS_visit(v); // recursive function call
}
}
// Once all adjacent vertices have been located, we are done with this node
u->color = "black";
}
vector <Vertex*>* AdjVertices(Vertex* vert)
{
// Creates a vector containing all of the adjacent vertices
// to the intersection in question (vert)
vector<Vertex*>* adjVertex = new vector <Vertex*> ();
const int size = edges.size();
for(int i=0; i<size; ++i)
{
Edge* edge = edges.at(i);
Vertex* adjacent = NULL;
if (edge->intersection1 == vert) // if edge's start vertex is the vertex in question
{
adjacent = edge->intersection2;
}
else if (edge->intersection2 == vert) // if edge's end vertex is the vertex in question
{
adjacent = edge->intersection1;
}
if (adjacent && vertices_check(vertices, adjacent))
{
adjVertex->push_back(adjacent);
}
}
return adjVertex;
}
1 回答
您可以使用Vector(在您调用DFS_visit的其他函数中构造)并将其传递给DFS_visit . 在DFS_visit中,您在开始时添加节点,然后每次从被调查的子项返回时添加节点 . 这应该给你一个完整的路径描述 .