相关疑难解决方法(0)

我正在寻找非二叉树的非递归深度优先搜索算法.很感谢任何形式的帮助.

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

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算法:

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);
            }
        } …

好的,这是我在Stack Overflow上的第一篇文章,我已经阅读了一段时间,真的很欣赏这个网站.我希望这是可以接受的问题.所以我一直在阅读Intro to Algorithms(Cormen.麻省理工学院出版社),我完全依赖于图算法.我一直在研究用于广度和深度优先详细搜索的正式算法.

这是深度优先搜索的伪代码:

DFS(G)
-----------------------------------------------------------------------------------
1  for each vertex u ? G.V
2      u.color ? WHITE       // paint all vertices white; undiscovered
3      u.? ? NIL
4      time ? 0              // global variable, timestamps
5  for each vertex u ? G.V
6      if u.color = WHITE
7          DFS-VISIT(G,u)

DFS-VISIT(G, u)
-----------------------------------------------------------------------------------
1  u.color ? GRAY          // grey u; it is discovered
2  time ? time + 1 
3  u.d ? time
4  for each v ? G.Adj[u]   // …