<dl id="obfdf"></dl>

<progress id="obfdf"><tr id="obfdf"></tr></progress>

      <em id="obfdf"><ol id="obfdf"><mark id="obfdf"></mark></ol></em>

      <progress id="obfdf"><tr id="obfdf"><object id="obfdf"></object></tr></progress>
      <dl id="obfdf"><ins id="obfdf"></ins></dl>
      <em id="obfdf"><ol id="obfdf"><thead id="obfdf"></thead></ol></em>

      張金磊的個人網站

      當前位置:首頁 > 網站優化
      服務熱線
      18695836489
      聯系郵箱
      [email protected]

      SEO技術關于廣度優先搜索和深度優先搜索

      時間:2016-03-05 00:00:00 瀏覽:

       廣度優先搜索(BFS),可以被形象的描述為“淺嘗輒止”,具體一點就是每個頂點只訪問它的鄰接節點(如果它的鄰接節點沒有被訪問)并且記錄這個鄰接節點,當訪問完它的鄰接節點之后就結束這個頂點的訪問。周口網站建設

      廣度優先用到了“先進先出”隊列,通過這個隊列來存儲第一次發現的節點,以便下一次的處理;而對于再次發現的節點,我們不予理會——不放入隊列,因為再次發現的節點:周口網站建設

      無非是已經處理完的了;周口網站建設

      或者是存儲在隊列中尚未處理的。周口網站建設

      周口網站建設

      《算法導輪》對兩種搜索都采用了很聰明的做法,用白色WHITE來標志未發現的節點,用灰色GRAY來標志第一次被發現的節點,用黑色BLACK來標志第二次被發現的節點。周口網站建設

      于是有了:周口網站建設

      1. BFS(G,s)
      2.     for each vertex v in V[G]
      3.         status[v] = WHITE
      4.         /******其他初始化******/
      5.     status[s] = GRAY    //s是原點
      6.     queue q
      7.     入隊(q,s);
      8.     while q非空
      9.         t = 出隊(q);
      10.         for each vertex v in Adj[t] //與t鄰接的點
      11.             if status[v] = WHITE    //只對未訪問的操作
      12.                 status[v] = GRAY    //標記為第一次訪問
      13.                 /******其他操作******/
      14.                 入隊(q,v)
      15.         status[t] = BLACK   //此點已經處理完了
      復制代碼

      周口網站建設

      導論還在上面偽代碼的“其他”中加入了訪問長度和父節點的操作。此舉可以算出,從源點到其他頂點路徑的最少步數和它的具體路徑。周口網站建設

      關于廣度優先搜索的一個簡單應用:周口網站建設

      假如有問題,每個村莊之間都通過橋來聯通,先給出村莊的圖,問村莊A到村莊B最少要通過多少座橋?這個問題可以很容易的轉化為上面的BFS問題。周口網站建設

      深度優先搜索深度優先搜索(DFS),可以被形象的描述為“打破沙鍋問到底”,具體一點就是訪問一個頂點之后,我繼而訪問它的下一個鄰接的頂點,如此往復,直到當前頂點一被訪問或者它不存在鄰接的頂點。周口網站建設

      同樣,算法導論采用了“聰明的做法”,用三種顏色來標記三種狀態。但這三種狀態不同于廣度優先搜索:周口網站建設

      WHITE 未訪問頂點周口網站建設

      GRAY 一條深度搜索路徑上的頂點,即被發現時周口網站建設

      BLACK 此頂點的鄰接頂點被全部訪問完之后——結束訪問次頂點周口網站建設

      1. DFS(G,s)
      2.     for each vertex v in V(G)
      3.         status[v] = WHITE
      4.         /******其他初始化******/
      5.     for each vertex v in V(G)
      6.         if(status[v]==WHITE)
      7.             DFS-VISIT(v)
      8.  
      9. DFS-VISIT(v)
      10.     status[v] = GRAY
      11.     for each vertex t in Adj(v)
      12.         if status[t] = WHITE
      13.             DFS-VISIT(t)
      14.             /******其他操作******/
      15.     status[v] = BLACK
      復制代碼

      通過給DFS搜索過程中給每一個頂點加時間戳,就可以實現拓撲排序了。實現拓撲排序需要:周口網站建設

      對于每一個頂點,都有兩個時間戳,分別這樣來定義:周口網站建設

      在一頂點剛被發現的時候,標記此頂點的第一個時間戳;周口網站建設

      在結束此頂點的訪問的時候,標記此頂點的第二個時間戳。時間戳可以用簡單的123456來標記,只要能區分大小就行。周口網站建設

      因此,你會發現,越早發現的點,他的第一個時間戳會越小,但是他的第二個時間戳會越大。周口網站建設

      總結兩個算法都是O(V+E),在用到的時候適當選取。在使用白灰黑標志的時候,突然明白了如何用深度優先搜索來判斷有向圖中是否存在環。周口網站建設

      深度優先和廣度優先各有各的優缺點:周口網站建設

      廣優的話,占內存多,能找到最優解,必須遍歷所有分枝. 廣優的一個應用就是迪科斯徹單元最短路徑算法。周口網站建設

      深優的話,占內存少,能找到最優解(一定條件下),但能很快找到接近解(優點),可能不必遍歷所有分枝(也就是速度快), 深優的一個應用就是連連看游戲。周口網站建設

      在更多的情況下,深優是比較好的方案。周口網站建設

      上一篇:SEO技術避免網站流量大損失的seo策略
      下一篇:seo技術關于鼠標鍵盤模擬與數據提交
      分享到:

      聯系我們

      三石網站,設計開發安全無漏洞網站。

      辦公郵箱:[email protected]公司地址:河南省周口市太康縣

      選擇三石,選擇快捷!三石網絡,讓您不同!
      广东十一选五杀号公式
      <dl id="obfdf"></dl>

      <progress id="obfdf"><tr id="obfdf"></tr></progress>

          <em id="obfdf"><ol id="obfdf"><mark id="obfdf"></mark></ol></em>

          <progress id="obfdf"><tr id="obfdf"><object id="obfdf"></object></tr></progress>
          <dl id="obfdf"><ins id="obfdf"></ins></dl>
          <em id="obfdf"><ol id="obfdf"><thead id="obfdf"></thead></ol></em>
          <dl id="obfdf"></dl>

          <progress id="obfdf"><tr id="obfdf"></tr></progress>

              <em id="obfdf"><ol id="obfdf"><mark id="obfdf"></mark></ol></em>

              <progress id="obfdf"><tr id="obfdf"><object id="obfdf"></object></tr></progress>
              <dl id="obfdf"><ins id="obfdf"></ins></dl>
              <em id="obfdf"><ol id="obfdf"><thead id="obfdf"></thead></ol></em>