0

ベクトルを使用して頂点とエッジを格納する、クラスとして設定したグラフのトラバースに取り組んでいます。グラフで深さ優先検索を使用して、通過するパスを表示していますが、コードを取得して、次のような形式で頂点を順番に表示したいと思います。

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

1 に答える 1

1

ベクター (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";
}
于 2012-12-06T11:08:21.833 に答える