# 一、综述 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）原图：  （2）第一种邻接表顺序与对应的广度优先树   （3）第二种邻接表顺序与对应的广度优先树   ### 22.2-5 这题的意思应该是举一种特殊的例子吧。  以上是一个有向图，令源顶点为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)