99999久久久久久亚洲,欧美人与禽猛交狂配,高清日韩av在线影院,一个人在线高清免费观看,啦啦啦在线视频免费观看www

熱線電話：13121318867

登錄
首頁(yè)精彩閱讀 經(jīng)典算法研究系列；BFS和DFS優(yōu)先搜索算法
經(jīng)典算法研究系列；BFS和DFS優(yōu)先搜索算法
2015-01-24
收藏

 經(jīng)典算法研究系列；BFS和DFS優(yōu)先搜索算法


關(guān)于此類(lèi)BFS和DFS算法的文章，很多。但，都說(shuō)不出個(gè)所以然來(lái)。
讀完此文，我想，
你對(duì)圖的廣度優(yōu)先搜索和深度優(yōu)先搜索定會(huì)有個(gè)通通透透，徹徹底底的認(rèn)識(shí)。

咱們由BFS開(kāi)始：
首先，看下算法導(dǎo)論一書(shū)關(guān)于 此BFS 廣度優(yōu)先搜索算法的概述。
算法導(dǎo)論第二版，中譯本，第324頁(yè)。
廣度優(yōu)先搜索（BFS）
在Prime最小生成樹(shù)算法，和Dijkstra單源最短路徑算法中，都采用了與BFS 算法類(lèi)似的思想。

//u 為 v 的先輩或父母。
BFS(G, s)
 1  for each vertex u ∈ V [G] - {s}
 2       do color[u] ← WHITE
 3          d[u] ← ∞
 4          π[u] ← NIL
  //除了源頂點(diǎn)s之外，第1-4行置每個(gè)頂點(diǎn)為白色，置每個(gè)頂點(diǎn)u的d[u]為無(wú)窮大，
  //置每個(gè)頂點(diǎn)的父母為NIL。
 5  color[s] ← GRAY
  //第5行，將源頂點(diǎn)s置為灰色，這是因?yàn)樵谶^(guò)程開(kāi)始時(shí)，源頂點(diǎn)已被發(fā)現(xiàn)。
 6  d[s] ← 0       //將d[s]初始化為0。
 7  π[s] ← NIL     //將源頂點(diǎn)的父頂點(diǎn)置為NIL。
 8  Q ← ?
 9  ENQUEUE(Q, s)                  //入隊(duì)
  //第8、9行，初始化隊(duì)列Q，使其僅含源頂點(diǎn)s。

10  while Q ≠ ?
11      do u ← DEQUEUE(Q)    //出隊(duì)
  //第11行，確定隊(duì)列頭部Q頭部的灰色頂點(diǎn)u，并將其從Q中去掉。
12         for each v ∈ Adj[u]        //for循環(huán)考察u的鄰接表中的每個(gè)頂點(diǎn)v
13             do if color[v] = WHITE
14                   then color[v] ← GRAY     //置為灰色
15                        d[v] ← d[u] + 1     //距離被置為d[u]+1
16                        π[v] ← u            //u記為該頂點(diǎn)的父母
17                        ENQUEUE(Q, v)        //插入隊(duì)列中
18         color[u] ← BLACK      //u 置為黑色

 

 

由下圖及鏈接的演示過(guò)程，清晰在目，也就不用多說(shuō)了： 

ok，不再贅述。接下來(lái)，具體講解深度優(yōu)先搜索算法。
深度優(yōu)先探索算法 DFS 
//u 為 v 的先輩或父母。
DFS(G)
1  for each vertex u ∈ V [G]
2       do color[u] ← WHITE
3          π[u] ← NIL
//第1-3行，把所有頂點(diǎn)置為白色，所有π 域被初始化為NIL。
4  time ← 0       //復(fù)位時(shí)間計(jì)數(shù)器
5  for each vertex u ∈ V [G]
6       do if color[u] = WHITE
7             then DFS-VISIT(u)  //調(diào)用DFS-VISIT訪問(wèn)u，u成為深度優(yōu)先森林中一棵新的樹(shù)
    //第5-7行，依次檢索V中的頂點(diǎn)，發(fā)現(xiàn)白色頂點(diǎn)時(shí)，調(diào)用DFS-VISIT訪問(wèn)該頂點(diǎn)。
    //每個(gè)頂點(diǎn)u 都對(duì)應(yīng)于一個(gè)發(fā)現(xiàn)時(shí)刻d[u]和一個(gè)完成時(shí)刻f[u]。
DFS-VISIT(u)
1  color[u] ← GRAY            //u 開(kāi)始時(shí)被發(fā)現(xiàn)，置為白色
2  time ← time +1             //time 遞增
3  d[u] <-time                   //記錄u被發(fā)現(xiàn)的時(shí)間
4  for each v ∈ Adj[u]   //檢查并訪問(wèn) u 的每一個(gè)鄰接點(diǎn) v
5       do if color[v] = WHITE            //如果v 為白色，則遞歸訪問(wèn)v。
6             then π[v] ← u                   //置u為 v的先輩
7                         DFS-VISIT(v)        //遞歸深度，訪問(wèn)鄰結(jié)點(diǎn)v
8  color[u] <-BLACK         //u 置為黑色，表示u及其鄰接點(diǎn)都已訪問(wèn)完成
9  f [u] ? time ← time +1  //訪問(wèn)完成時(shí)間記錄在f[u]中。
//完
第1-3行，5-7行循環(huán)占用時(shí)間為O（V），此不包括調(diào)用DFS-VISIT的時(shí)間。
    對(duì)于每個(gè)頂點(diǎn)v(-V，過(guò)程DFS-VISIT僅被調(diào)用依次，因?yàn)橹挥袑?duì)白色頂點(diǎn)才會(huì)調(diào)用此過(guò)程。
第4-7行，執(zhí)行時(shí)間為O（E）。
因此，總的執(zhí)行時(shí)間為O(V+E)。

數(shù)據(jù)分析咨詢請(qǐng)掃描二維碼

若不方便掃碼，搜微信號(hào)：CDAshujufenxi

數(shù)據(jù)分析師資訊
更多

OK
客服在線
立即咨詢
客服在線
立即咨詢
') } function initGt() { var handler = function (captchaObj) { captchaObj.appendTo('#captcha'); captchaObj.onReady(function () { $("#wait").hide(); }).onSuccess(function(){ $('.getcheckcode').removeClass('dis'); $('.getcheckcode').trigger('click'); }); window.captchaObj = captchaObj; }; $('#captcha').show(); $.ajax({ url: "/login/gtstart?t=" + (new Date()).getTime(), // 加隨機(jī)數(shù)防止緩存 type: "get", dataType: "json", success: function (data) { $('#text').hide(); $('#wait').show(); // 調(diào)用 initGeetest 進(jìn)行初始化 // 參數(shù)1：配置參數(shù) // 參數(shù)2：回調(diào)，回調(diào)的第一個(gè)參數(shù)驗(yàn)證碼對(duì)象，之后可以使用它調(diào)用相應(yīng)的接口 initGeetest({ // 以下 4 個(gè)配置參數(shù)為必須，不能缺少 gt: data.gt, challenge: data.challenge, offline: !data.success, // 表示用戶后臺(tái)檢測(cè)極驗(yàn)服務(wù)器是否宕機(jī) new_captcha: data.new_captcha, // 用于宕機(jī)時(shí)表示是新驗(yàn)證碼的宕機(jī) product: "float", // 產(chǎn)品形式，包括：float，popup width: "280px", https: true // 更多配置參數(shù)說(shuō)明請(qǐng)參見(jiàn)：http://docs.geetest.com/install/client/web-front/ }, handler); } }); } function codeCutdown() { if(_wait == 0){ //倒計(jì)時(shí)完成 $(".getcheckcode").removeClass('dis').html("重新獲取"); }else{ $(".getcheckcode").addClass('dis').html("重新獲取("+_wait+"s)"); _wait--; setTimeout(function () { codeCutdown(); },1000); } } function inputValidate(ele,telInput) { var oInput = ele; var inputVal = oInput.val(); var oType = ele.attr('data-type'); var oEtag = $('#etag').val(); var oErr = oInput.closest('.form_box').next('.err_txt'); var empTxt = '請(qǐng)輸入'+oInput.attr('placeholder')+'！'; var errTxt = '請(qǐng)輸入正確的'+oInput.attr('placeholder')+'！'; var pattern; if(inputVal==""){ if(!telInput){ errFun(oErr,empTxt); } return false; }else { switch (oType){ case 'login_mobile': pattern = /^1[3456789]\d{9}$/; if(inputVal.length==11) { $.ajax({ url: '/login/checkmobile', type: "post", dataType: "json", data: { mobile: inputVal, etag: oEtag, page_ur: window.location.href, page_referer: document.referrer }, success: function (data) { } }); } break; case 'login_yzm': pattern = /^\d{6}$/; break; } if(oType=='login_mobile'){ } if(!!validateFun(pattern,inputVal)){ errFun(oErr,'') if(telInput){ $('.getcheckcode').removeClass('dis'); } }else { if(!telInput) { errFun(oErr, errTxt); }else { $('.getcheckcode').addClass('dis'); } return false; } } return true; } function errFun(obj,msg) { obj.html(msg); if(msg==''){ $('.login_submit').removeClass('dis'); }else { $('.login_submit').addClass('dis'); } } function validateFun(pat,val) { return pat.test(val); }