在c++中使用深度优先搜索查找图数据结构中所有可能的路径

Question

假设你有一个图，G，你需要做的是找到从start_node到finish_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都有其他节点可以去，但它们的距离不会被考虑，即使深度优先算法将探索它们。这是一个单向图，输入来自文本文件。

Answer 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());