<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>

                ??碼云GVP開源項目 12k star Uniapp+ElementUI 功能強大 支持多語言、二開方便! 廣告
                # 一、綜述 BFS蠻簡單的,沒什么好的綜述的。 BFS算法的算法過程與它是有向圖還是無向圖沒有關系,也與用鄰接圖還是用矩陣表示也沒有關系。本文的代碼是用鄰接圖實現的,例子是22-3的有向圖。 用鄰接矩陣實現的BFS見[算法導論-22.2-3-鄰接矩陣實現圖的廣度優先搜索](http://blog.csdn.net/mishifangxiangdefeng/article/details/7837922) # 二、代碼 ### 1.Link_Graph.h ~~~ #include <iostream> #include <queue> using namespace std; #define N 100 #define WHITE 0 #define GRAY 1 #define BLACK 2 queue<int> Q; struct Vertex; struct Edge { int start; int end; int value; Edge *next; Edge(int s, int e, int v):start(s),end(e),value(v),next(NULL){} }; struct Vertex { int color; int d; int Pie; Edge *head; Vertex():head(NULL),color(WHITE),d(0x7fffffff),Pie(0){}; }; class Link_Graph { public: int n; Vertex *V; Link_Graph(int num):n(num) { V = new Vertex[n+1]; } ~Link_Graph(){delete []V;} void AddSingleEdge(int start, int end, int value = 1) { Edge *NewEdge = new Edge(start, end, value); if(V[start].head == NULL || V[start].head->end > end) { NewEdge->next = V[start].head; V[start].head = NewEdge; } else { Edge *e = V[start].head, *pre = e; while(e != NULL && e->end < end) { pre = e; e = e->next; } if(e && e->end == end) { delete NewEdge; return; } NewEdge->next = e; pre->next = NewEdge; } } void AddDoubleEdge(int a, int b, int value = 1) { AddSingleEdge(a, b, value); AddSingleEdge(b, a, value); } void DeleteSingleEdge(int start, int end) { Edge *e = V[start].head, *pre = e; while(e && e->end < end) { pre = e; e = e->next; } if(e == NULL || e->end > end) return; if(e == V[start].head) V[start].head = e->next; else pre->next = e->next; delete e; } void DeleteDoubleEdge(int a, int b) { DeleteSingleEdge(a, b); DeleteSingleEdge(b, a); } //22.2 //廣度優先搜索 void BFS(int s); //廣度優先樹 void Print_Path(int s, int v); }; void Link_Graph::BFS(int s) { int i; for(i = 1; i <= n; i++) { V[i].color = WHITE; V[i].d = 0x7fffffff; V[i].Pie = 0; } V[s].color = GRAY; V[s].d = 0; V[s].Pie = 0; while(!Q.empty())Q.pop(); Q.push(s); while(!Q.empty()) { int u, v; u = Q.front();Q.pop(); Edge *e = V[u].head; while(e) { v = e->end; if(V[v].color == WHITE) { V[v].color = GRAY; V[v].d = V[u].d + 1; V[v].Pie = u; Q.push(v); } e = e->next; } V[u].color = BLACK; } } void Link_Graph::Print_Path(int s, int v) { BFS(s); if(v == s) cout<<s<<' '; else { if(V[v].Pie == 0) cout<<"no path from "<<s<<" to "<<v<<" exists."; else { Print_Path(s, V[v].Pie); cout<<v<<' '; } } } ~~~ ### 2.main.cpp ~~~ #include <iostream> #include "Link_Graph.h" using namespace std; /* 1 2 1 5 2 6 6 7 6 3 3 7 3 4 7 8 7 4 4 8 */ int main() { Link_Graph *G = new Link_Graph(8); int i = 0, a, b; for(i = 1; i <= 10; i++) { cin>>a>>b; G->AddDoubleEdge(a,b); } G->BFS(2); for(i = 1; i <= 8; i++) cout<<G->V[i].d<<' '; cout<<endl; int s, v; while(cin>>s>>v) { G->Print_Path(s, v); cout<<endl; } return 0; } ~~~ # 三、練習 ### 22.2-1 d:2147483647 3 0 2 1 1 p:-1 4 -1 5 3 3 ### 22.2-2 d:4 3 1 0 5 2 1 1 p:2 6 4 -1 1 3 4 4 ### 22.2-3 [算法導論-22.2-3-鄰接矩陣實現圖的廣度優先搜索](http://blog.csdn.net/mishifangxiangdefeng/article/details/7837922) ### 22.2-4 (1)原圖: ![](https://box.kancloud.cn/2016-02-02_56b02bd31bc20.gif) (2)第一種鄰接表順序與對應的廣度優先樹 ![](https://box.kancloud.cn/2016-02-02_56b02bd32a6ad.gif) ![](https://box.kancloud.cn/2016-02-02_56b02bd33ca0a.gif) (3)第二種鄰接表順序與對應的廣度優先樹 ![](https://box.kancloud.cn/2016-02-02_56b02bd34bcfc.gif) ![](https://box.kancloud.cn/2016-02-02_56b02bd36026d.gif) ### 22.2-5 這題的意思應該是舉一種特殊的例子吧。 ![](https://box.kancloud.cn/2016-02-02_56b02bd36d92a.gif) 以上是一個有向圖,令源頂點為s,帶陰影的邊組成一個邊的集合e,e屬于E。e滿足對每一頂點v屬于V,從s到v的唯一路徑是G中的一條最短路徑。 對G做BFS,無法產生邊的集合e。 ### 22.2-6 這道題第一反應是用并查集來解決,處理起來有點麻煩。后來發現用BFS也可以處理。 [算法導論 22.6 職業摔跤手](http://blog.csdn.net/mishifangxiangdefeng/article/details/8393722) ### 22.2-7 [算法導論-22.2-7-樹的直徑](http://blog.csdn.net/mishifangxiangdefeng/article/details/7838106) ### 22.2-8 感覺應該是深搜,但是這一節講的是廣搜,怎么用廣搜解決這個問題呢?求想法. 使用DFS的解題方法見[算法導論 22.2-8 無向圖遍歷](http://blog.csdn.net/mishifangxiangdefeng/article/details/8395479)
                  <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>

                              哎呀哎呀视频在线观看