algorithm - 在长度在给定用户定义范围内的加权无向图中找到一个简单循环

Question

已编辑 - 12/03/12 @ 1:05 AM PST

我已经按如下方式编辑了我的代码。但是，我仍然没有让它返回任何路径。

同样，此代码用于计算路径，用户指定起始顶点和距离。该程序将返回与指定数据匹配的所有适当路径。

到目前为止，这是我的代码:

vector<vector<Vertex>> Graph::FindPaths(Graph &g, int startingIntersection, float distanceInMiles)
{   
/* A vector which contains vectors which will contain all of the suitable found paths. */
vector<vector<Vertex>> paths;

/* Create an empty set to store the visited nodes. */
unordered_set<int> visited;

/* Vector which will be used to the hold the current path. */
vector<Vertex> CurrentPathList;

/* Will be used to store the currerntVertex being examined. */
Vertex currentVertex;

/* Will be used to store the next vertex ID to be evaluated. */
int nextVertex;

/* Will be used to determine the location of the start ID of a vertex within the VertexList. */
int start;

/* Stack containing the current paths. */
stack<Vertex> currentPaths;

/* CurrentPathDistance will be used to determine the currernt distance of the path. */
float currentPathDistance = 0;

/* The startingIntersection location must be found within the VertexList.  This is because there is
 * no guarantee that the VertexList will hold sequential data.
 *
 * For example, the user inputs a startingIntersection of 73.  The Vertex for intersection #73 may 
 * be located at the 20th position of the VertexList (i.e. VertexList[20]). */
start = g.FindStartingIntersection(g, startingIntersection);

/* Push the startingIntersection onto the stack. */
currentPaths.push(g.VertexList[start]);

/* Continue to iterate through the stack until it is empty.  Once it is empty we have exhaused all
 * possible paths. */
while(!currentPaths.empty())
{
    /* Assign the top value of the stack to the currentVertex. */
    currentVertex = currentPaths.top();

    /* Pop the top element off of the stack. */
    currentPaths.pop();

    /* Check to see if we are back to the startingIntersection.  As a note, if we are just starting, it will 
     * put the startingIntersection into the paths. */
    if(currentVertex.id == startingIntersection)
    {
        /* Add currentVertex to a list. */
        CurrentPathList.push_back(currentVertex);

        /* Find the current path distance. */
        currentPathDistance = FindPathDistance(g, CurrentPathList);

        /* Check the currentPathDistance.  If it is within +/- 1 mile of the specified distance, then place
         * it into the vector of possible paths. */
        if((currentPathDistance + 1 >= distanceInMiles) && (currentPathDistance - 1 <= distanceInMiles))
        {
            paths.push_back(CurrentPathList);
        }
    }
    else /* The ending vertex was not the user specified starting vertex. */
    {
        /* Remove all elements from the stack. */
        while(!currentPaths.empty())
        {
            currentPaths.pop();
        }
    }

    nextVertex = FindUnvisitedNeighbor(g, currentVertex, visited);

    // repeat while current has unvisited neighbors
    while(nextVertex != -1)
    {
        /* Find the new starting vertex. */
        start = g.FindStartingIntersection(g, nextVertex);

        /* Push the startingIntersection onto the stack. */
        currentPaths.push(g.VertexList[start]);

        /* Push the next vertex into the visted list. */
        visited.insert(nextVertex);

        nextVertex = FindUnvisitedNeighbor(g, currentVertex, visited);
    }     
}

/* Return the vector of paths that meet the criteria specified by the user. */
return paths;

我的 FindingUnvistedNeighbor() 代码如下:

int FindUnvisitedNeighbor(Graph &g, Vertex v, unordered_set<int> visited)
{
    /* Traverse through vertex "v"'s EdgeList. */
    for(int i = 0; i + 1 <= v.EdgeList.size(); i++)
    {
        /* Create interator to traverse through the visited list to find a specified vertex. */
        unordered_set<int>::const_iterator got = visited.find(v.EdgeList[i].intersection_ID_second);

        /* The vertex was not found in the visited list. */
        if(got == visited.end())
        {

            return v.EdgeList[i].intersection_ID_second;
        }
    }

    return -1;
}

Answer 1

这似乎是一个基本的算法问题，而不是特定于实现的问题，因此我为算法提供了详细的高级伪代码而不是实际代码。另外，我不知道C++。让我知道是否有任何语法/逻辑不清楚，我可以澄清更多。它本质上是进行 DFS，但在找到值时不会停止:它会继续搜索，并报告该值的所有路径(满足给定的距离标准)。

// Input: Graph G, Vertex start, Integer targetDistance
// Output: Set< List<Vertex> > paths
FindPaths ( G, start, targetDistance ):
    create an empty set, paths
    create an empty set, visited
    create an empty stack, currentPath

    // Iterative Exhaustive DFS
    push start on currentPath
    while ( currentPath is not empty ):
        current = pop ( currentPath )

        if ( current equals start ):
            copy currentPath to a list, L (reversed order doesn't matter)
            // find its weight
            w = FindPathWeight ( L, G )

            if ( w+1 >= targetDistance AND w-1 <= targetDistance ):
                add L to paths

        else if ( current is a dead-end ): drop it completely, it's useless

        x = FindUnvisitedNeighbor ( current, G, visited )
        // repeat while current has unvisited neighbors
        while ( x ):
            push x on currentPath
            add x to visited
            x = FindUnvisitedNeighbor ( current, G, visited )

    return paths
//EndFindPaths

// Input: List path, Graph G
// Output: Integer weight
FindPathWeight ( path, G ):
    Integer weight = 0;

    for each ( Vertex v in path ):

        if ( v is the end of the path ): break

        Consider the next vertex in the list, u
        Find the edge v——u in the graph, call it e
        Get the weight of e, w
        weight = weight + w

    return weight
//EndFindPathWeight

// Input: Vertex v, Graph G, Set visited
// Output: Vertex u (or null, if there are none)
FindUnvisitedNeighbor ( v, G, visited ):

    for each ( Edge v——u in G.EdgeList ):

        if ( u in visited ): continue

        // u is the first unvisited neighbor
        return u

    return null
//EndFindUnvisitedNeighbor