Отображение переполнения стека обхода графика поиска в глубину

Я работаю над обходом графа, который я настроил как класс, используя векторы для хранения вершин и ребер. Я использую поиск по глубине на графике, чтобы показать пути по мере их прохождения, но я бы хотел как-то заставить мой код отображать вершины в порядке их прохождения в формате, подобном следующему:

<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;
}

0

Решение

Вы можете использовать Vector (созданный в другой функции, вызывающей DFS_visit) и передавать его в DFS_visit. В DFS_visit вы добавляете узел в начале, а затем каждый раз, когда возвращаетесь от исследуемого потомка. Это должно дать вам полное описание пути.

void DFS_visit(Vertex* u, Vector<Vertex*> path )
{
u->color = "gray";  //  Mark that we have visited intersection 'u'
path.push_back(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,path);  // recursive function call
path.push_back(u);
}
}

//  Once all adjacent vertices have been located, we are done with this node
u->color = "black";
}
1

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector