<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 一、綜述 深搜策略:在深搜過程中,對于最新發現的頂點,如果它還有以此為起點的而未探測到的邊,就沿此邊繼續探測下去。當頂點v的所有邊都已被探測過后,搜索將回溯到發現頂點v有起始點的那些邊。 時間戳:當頂點v第一次被發現時記錄下第一個時間戳d[v],當結束檢查v的鄰接表時,記錄下第二個時間戳f[v]。v在d[v]時刻前是白色的,在時刻d[v]和f[v]之間是灰色的,在時刻f[v]之后是黑色的。 括號定理,后裔區間的嵌套,白色路徑定理 邊的分類:(1)樹邊(2)反向邊(3)正向邊(4)交叉邊 對無向圖G進行深度搜索時,G的每一條邊,要么是樹邊,要么是反向邊。 # 二、代碼 ### 1.Link_Graph.h https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter22/section22_3.cpp ### 2.main.cpp https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/tst/chapter22/section22_3Test.cpp ### 3.測試數據 書P335,圖22-6 10 14 q s? s v? v w? w s? q w? q t? t y? y q? t x? x z? z x? u y? r y? r u ### 4.輸出結果 見22.3-2 # 三、練習 ### 22.3-1 關鍵是“任何時刻” 有向圖 | ? | WHITE | GRAY | BLACK | |-----|-----|-----|-----| | WHITE | TBFC | BC | C | | GRAY | TF | TFB | TFC | | BLACK | ? | B | TFBC | 無向圖 | ? | WHITE | GRAY | BLACK | |-----|-----|-----|-----| | WHITE | TB | TB | ? | | GRAY | TB | TB | TB | | BLACK | ? | TB | TB | ### 22.3-2 q:1 16 r:17 20 s:2 7 t:8 15 u:18 19 v:3 6 w:4 5 x:9 12 y:13 14 z:10 11 q->s: 樹邊 q->t: 樹邊 q->w: 正向邊 r->u: 樹邊 r->y: 交叉邊 s->v: 樹邊 t->x: 樹邊 t->y: 樹邊 u->y: 交叉邊 v->w: 樹邊 w->s: 反向邊 x->z: 樹邊 y->q: 反向邊 z->x: 反向邊 ### 22.3-3 (u(v(y(xx)y)v)u)(w(zz))w) ### 22.3-6 [算法導論-22.3-6-用棧實現DFS](http://blog.csdn.net/mishifangxiangdefeng/article/details/7839628) ### 22.3-7 參考1樓所給的答案: V={w,u,v} E={(w,u), (u,w), (w,v)} 有一條從u到v的路徑,即u->w->v DFS的順序為w,u,u,v,v,w,d[u]=2,d[v]=4,d[u]<d[v] 得到的森林中,u和v都是w的后裔 ### 22.3-8 如圖所示,(1)有一條從u到v的路徑 ![](https://box.kancloud.cn/2016-02-02_56b02bd37eab8.jpg) ### 22.3-9 貌似不用改 ### 22.3-10 ![](https://box.kancloud.cn/2016-02-02_56b02bd392fe1.gif) ### 22.3-11 聯通分支的數量用ceil表示,代碼修改如下: ~~~ void Link_Graph::DFS() { int u, ceil = 0; //對每個頂點初始化 for(u = 1; u <= n; u++) { V[u].color = WHITE; V[u].p = NULL; } //時間戳初始化 time = 0; //依次檢索V中的頂點,發現白色頂點時,調用DFS_Visit訪問該頂點 for(u = 1; u <= n; u++) { if(V[u].color == WHITE) { ceil++; DFS_Visit(u, ceil); } } } void Link_Graph::DFS_Visit(int u, int ceil) { int v; Edge *e; //將u置為灰色 V[u].color = GRAY; //使全局變量time增值 time++; //將time的新值記錄為發現時間 V[u].d = time; e = V[u].head; while(e) { v = e->end; //如果頂點為白色 if(V[v].color == WHITE) { //遞歸訪問頂點 V[v].p = u; DFS_Visit(v, ceil); //樹邊 e->type = TREE; } else if(V[v].color == GRAY) { //反向邊 e->type = BACK; } else if(V[v].color == BLACK) { //正向邊 if(V[u].d < V[v].d) e->type = FORWARD; //交叉邊 else e->type = CROSS; } e = e->next; } //以u為起點的所有邊都被探尋后,置u為黑色 V[u].color = BLACK; V[u].ceil = ceil; //并將完成時間記錄在f[u]中 time++; V[u].f = time; } ~~~ ### 22.3-12 單連通圖沒有正向邊
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看