1

假设你有一个 Graph，G你需要做的是找到从到的所有可能的路线。此外，您需要以正确的顺序打印所有路线。你会怎么做？发现节点并不难，它以正确的顺序打印它们并获得距离。start_nodefinish_node

template <class VertexType>
void DepthFirstSearch(Graph<VertexType> routes, VertexType from_vertex, VertexType to_vertex) 
{
    stack<VertexType> mystack;
    queue<VertexType> vertexQ;
    int total_weight = 0;
    int found_count = 0;

    /*stringstream ss;*/

    bool found = false;
    VertexType vertex;
    VertexType item;

    routes.clearMarks();

    // size_t i = 0;
    // size_t j = 0;

    mystack.push(from_vertex); // Adding Location to stack

    do 
    {   
        vertex = mystack.top(); // Get top location
        mystack.pop(); // Getting rid of top location
        if (vertex == to_vertex) // If location == destination, then stop;
        {
            found = true;
            found_count++;
        } else {
            if (!routes.isMarked(vertex)) // If route has not been traveled to
            {
                routes.markVertex(vertex); // Mark place
                routes.goToVertices(vertex, vertexQ); // Add adjacent positions
                while (!vertexQ.empty()) // While there are still positions left to test
                {

                    item = vertexQ.front(); // Get top position
                    vertexQ.pop(); // Get rid of top position from stack
                    if (!routes.isMarked(item)) // If top position is not marked,
                        mystack.push(item); // Add to-visit stack
                }
            }
        }
    } while (!mystack.empty());

    if(!found) 
    {
        std::cout << "Distance: infinity" << std::endl;
        std::cout << "Rout:" << std::endl;
        std::cout << "None" << std::endl;
    } else {
        std::cout << "Found this many times: " << found_count << std::endl;
    }
}

理想情况下，如果有人输入A B，那么输出示例将是：

distance: 100
A to C, 50
C to D, 40
D to B, 10


distance: 10
A to B, 10

请注意，两者C都有D它们可以去的其他节点，但是即使深度优先算法会探索它们，它们的距离也不会被考虑在内。这是一个单向图，输入来自文本文件。

4

1 回答 1

1

您需要跟踪您已经通过的顶点，并将该列表用作路径。

然后你有两个选择：

  • 找到路径时打印出顶点列表，然后回溯到下一个可能的分支，
  • 或将路径复制到另一个容器，回溯并在最后打印出整个路径列表

这两种方法都是正确的，具体取决于您希望在路径上执行哪种处理。

为了能够正确回溯，您需要知道当前路径上的每个顶点还有哪些相邻顶点需要访问。您当前的算法通过将所有顶点推入mystack. 我建议在 中使用迭代器而不是顶点，并让您的图形对象从方法中mystack返回此类迭代器。goToVertices

由于我不知道您是否有该类可用于您的图形，因此我将使用队列堆栈而不是按级别对顶点进行分组mystack。每个队列代表覆盖 dfs 的树的一个级别。

deque<queue<VertexType> > mystack;
queue<VertexType> vertexQ;
int total_weight = 0;
int found_count = 0;

VertexType vertex;

routes.clearMarks();

// size_t i = 0;
// size_t j = 0;

vertexQ.push(from_vertex);
mystack.push_front(vertexQ); // Adding Location to stack

do 
{   
    vertexQ = mystack.front(); // Get top location
    if (vertexQ.empty()) {
        mystack.pop_front();
        mystack.front().pop();
        continue;
    }
    if (vertexQ.front() == to_vertex) // If location == destination, then stop;
    {
        // save path: loop on all the queues from mystack and print front.    
        for (stack<queue<VertexType>>::const_reverse_iterator it = mystack.rbegin();
               it != mystack.rend();  ++it){
            // save or process path vertices
            cout << it->front() << endl;
        }               
        // backtrack
        mystack.pop_front();
        mystack.front().pop();
    } else {
        if (!routes.isMarked(vertexQ.front())) // If route has not been traveled to
        {
            routes.markVertex(vertexQ.front()); // Mark place
            mystack.push_front(
                routes.goToVertices(vertexQ.front())); // Get adjacent vertices
        }
    }
} while (!mystack.empty());
于 2013-04-19T11:55:06.397 回答