<legend id='t8Kxx'><style id='t8Kxx'><dir id='t8Kxx'><q id='t8Kxx'></q></dir></style></legend>

      <small id='t8Kxx'></small><noframes id='t8Kxx'>

      • <bdo id='t8Kxx'></bdo><ul id='t8Kxx'></ul>
    1. <i id='t8Kxx'><tr id='t8Kxx'><dt id='t8Kxx'><q id='t8Kxx'><span id='t8Kxx'><b id='t8Kxx'><form id='t8Kxx'><ins id='t8Kxx'></ins><ul id='t8Kxx'></ul><sub id='t8Kxx'></sub></form><legend id='t8Kxx'></legend><bdo id='t8Kxx'><pre id='t8Kxx'><center id='t8Kxx'></center></pre></bdo></b><th id='t8Kxx'></th></span></q></dt></tr></i><div id='t8Kxx'><tfoot id='t8Kxx'></tfoot><dl id='t8Kxx'><fieldset id='t8Kxx'></fieldset></dl></div>
      <tfoot id='t8Kxx'></tfoot>
    2. 迭代 DFS 与递归 DFS 以及不同的元素顺序

      时间:2023-06-29

      <small id='rBQD2'></small><noframes id='rBQD2'>

        <tbody id='rBQD2'></tbody>
        1. <legend id='rBQD2'><style id='rBQD2'><dir id='rBQD2'><q id='rBQD2'></q></dir></style></legend>
            <bdo id='rBQD2'></bdo><ul id='rBQD2'></ul>
            • <tfoot id='rBQD2'></tfoot>
                <i id='rBQD2'><tr id='rBQD2'><dt id='rBQD2'><q id='rBQD2'><span id='rBQD2'><b id='rBQD2'><form id='rBQD2'><ins id='rBQD2'></ins><ul id='rBQD2'></ul><sub id='rBQD2'></sub></form><legend id='rBQD2'></legend><bdo id='rBQD2'><pre id='rBQD2'><center id='rBQD2'></center></pre></bdo></b><th id='rBQD2'></th></span></q></dt></tr></i><div id='rBQD2'><tfoot id='rBQD2'></tfoot><dl id='rBQD2'><fieldset id='rBQD2'></fieldset></dl></div>
                本文介绍了迭代 DFS 与递归 DFS 以及不同的元素顺序的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着跟版网的小编来一起学习吧!

                问题描述

                我编写了一个递归 DFS 算法来遍历图:

                I have written a recursive DFS algorithm to traverse a graph:

                void Graph<E, N>::DFS(Node n)
                {
                    std::cout << ReadNode(n) << " ";
                
                    MarkVisited(n);
                
                    NodeList adjnodes = Adjacent(n);
                
                    NodeList::position pos = adjnodes.FirstPosition();
                
                    while(!adjnodes.End(pos))
                    {
                        Node adj = adjnodes.ReadList(pos);
                
                        if(!IsMarked(adj))
                            DFS(adj);
                
                        pos = adjnodes.NextPosition(pos);
                    }
                }
                

                然后我编写了一个使用堆栈的迭代 DFS 算法:

                Then I have written an iterative DFS algorithm using a stack:

                template <typename E, typename N>
                void Graph<E, N>::IterativeDFS(Node n)
                {
                    Stack<Node> stack;
                
                    stack.Push(n);
                
                    while(!stack.IsEmpty())
                    {
                        Node u = stack.Read();
                
                        stack.Pop();
                
                        if(!IsMarked(u))
                        {
                            std::cout << ReadNode(u) << " ";
                
                            MarkVisited(u);
                
                            NodeList adjnodes = Adjacent(u);
                
                            NodeList::position pos = adjnodes.FirstPosition();
                
                            while(!adjnodes.End(pos))
                            {
                                stack.Push(adjnodes.ReadList(pos));
                
                                pos = adjnodes.NextPosition(pos);
                            }
                        }
                    }
                

                我的问题是,在一个图中,例如,我输入三个节点 'a', 'b', 'c' 与弧 ('a', 'b') 和 ('a', 'c') 我的输出是:

                My problem is that in a graph in which, for example, I enter the three nodes 'a', 'b', 'c' with arcs ('a', 'b') and ('a', 'c') my output is:

                'a'、'b'、'c' 与递归 DFS 版本,以及:

                'a', 'b', 'c' with the recursive DFS version, and:

                'a', 'c', 'b' 与迭代 DFS 一.

                'a', 'c', 'b' with the iterative DFS one.

                我怎么能得到同样的订单?我做错了什么吗?

                How could I get the same order? Am I doing something wrong?

                谢谢!

                推荐答案

                两者都是有效的 DFS 算法.DFS 不会指定您首先看到哪个节点.这并不重要,因为边之间的顺序没有定义[记住:边通常是一个集合].不同之处在于您处理每个节点的子节点的方式.

                Both are valid DFS algorithms. A DFS does not specify which node you see first. It is not important because the order between edges is not defined [remember: edges are a set usually]. The difference is due to the way you handle each node's children.

                迭代方法中:您首先将所有元素插入堆栈 - 然后处理堆栈的头部[这是插入的最后一个节点] - 因此您的第一个节点句柄是最后一个孩子.

                In the iterative approach: You first insert all the elements into the stack - and then handle the head of the stack [which is the last node inserted] - thus the first node you handle is the last child.

                递归方法中:当您看到每个节点时,您就对其进行处理.因此,您处理的第一个节点是第一个子节点.

                In the recursive approach: You handle each node when you see it. Thus the first node you handle is the first child.

                为了使迭代 DFS 产生与递归相同的结果 - 您需要以相反的顺序向堆栈添加元素 [对于每个节点,首先插入其最后一个子节点,最后插入其第一个子节点]

                To make the iterative DFS yield the same result as the recursive one - you need to add elements to the stack in reverse order [for each node, insert its last child first and its first child last]

                这篇关于迭代 DFS 与递归 DFS 以及不同的元素顺序的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持跟版网!

                上一篇:C++ 中图形问题的邻接表或邻接矩阵哪个更好? 下一篇:提升图中 VertexList = ListS 的 Dijkstra 最短路径

                相关文章

                    <bdo id='gvb39'></bdo><ul id='gvb39'></ul>
                  <legend id='gvb39'><style id='gvb39'><dir id='gvb39'><q id='gvb39'></q></dir></style></legend>
                1. <small id='gvb39'></small><noframes id='gvb39'>

                  <tfoot id='gvb39'></tfoot>

                    <i id='gvb39'><tr id='gvb39'><dt id='gvb39'><q id='gvb39'><span id='gvb39'><b id='gvb39'><form id='gvb39'><ins id='gvb39'></ins><ul id='gvb39'></ul><sub id='gvb39'></sub></form><legend id='gvb39'></legend><bdo id='gvb39'><pre id='gvb39'><center id='gvb39'></center></pre></bdo></b><th id='gvb39'></th></span></q></dt></tr></i><div id='gvb39'><tfoot id='gvb39'></tfoot><dl id='gvb39'><fieldset id='gvb39'></fieldset></dl></div>