75_图的遍历（DFS）

关键词：深度优先（DFS）

0. 深度优先（DFS）

• 原料：class LinkStack<T>
• 步骤：
  1. 将起始顶点压入栈中
  2. 弹出栈顶顶点v，判断是否已经标记（标记：转2，未标记：转3）
  3. 标记顶点v，并将顶点v的邻接顶点压入栈中

  4. 判断栈是否为空（非空：转2，空：结束）

     
     
     DFS算法示例
     DFS流程图

    SharedPointer< Array<int> > DFS(int i)
    {
        DynamicArray<int>* ret = NULL;

        if( (i <= 0) && (i < vCount()) )
        {
            LinkStack<int> s;
            LinkQueue<int> r;
            DynamicArray<bool> visted(vCount());

            // 初始化设置，标记数组中的每一个都没有被访问
            for(int j=0; j<visted.length(); ++j)
            {
                visted[j] = false;
            }

            s.push(i);

            while( s.size() > 0 )
            {
                int v = s.top();      // 拿出队列头部的顶点

                s.pop();

                if( !visted[v] )        // 判断是否被访问
                {
                    SharedPointer< Array<int> > aj = getAdjacent(v);

                    for(int j=aj->length()-1; j>=0; --j)
                    {
                        s.push((*aj)[j]);
                    }

                    r.add(v);
                    visted[v] = true;
                }
            }

            ret = toArray(r);
        }
        else
        {
            THROW_EXCEPTION(InvalidParameterExcetion, "Index i is invalid ... ");
        }

        return ret;
    }

1. 小结

• 深度优先按照先序遍历的方式对顶点进行访问
• 深度优先算法的核心是栈的使用
• 深度优先和广度优先的唯一不同在于栈或队列的使用

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4