關鍵詞：深度優(yōu)先（DFS）

0. 深度優(yōu)先（DFS）

• 原料：class LinkStack<T>
• 步驟：
  1. 將起始頂點壓入棧中
  2. 彈出棧頂頂點v，判斷是否已經(jīng)標記（標記：轉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());

            // 初始化設置，標記數(shù)組中的每一個都沒有被訪問
            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. 小結

• 深度優(yōu)先按照先序遍歷的方式對頂點進行訪問
• 深度優(yōu)先算法的核心是棧的使用
• 深度優(yōu)先和廣度優(yōu)先的唯一不同在于?；蜿犃?/strong>的使用