# 一、綜述
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)
- 前言
- 第6章 堆排序
- 6-3 Young氏矩陣
- 第7章 快速排序
- 第8章 線性時間排序
- 第9章 排序和順序統計學算法導論
- 算法導論 9.1-1 求第二小元素
- 第10章 10.1 棧和隊列
- 第10章 10.2 鏈表
- 第10章 10.3 指針和對象實現
- 第10章 10.4 有根樹的表示
- 第11章-散列表
- 第12章 二叉查找樹
- 第13章 紅黑樹
- 第14章 14.1 動態順序統計
- 算法導論-14-1-最大重疊點
- 算法導論-14-2-Josephus排列
- 第14章 14.3 區間樹
- 第15章 動態規劃
- 第16章 貪心算法
- 第18章 B樹
- 第19章-二項堆
- 第20章 斐波那契堆
- 第21章 用于不相交集合的數據結構
- 第22章 圖的基本算法 22.1 圖的表示
- 第22章 圖算法 22.2 廣度優先搜索
- 第22章 圖算法 22.3 深度優先搜索
- 第22章 圖的基本算法 22.4 拓撲排序
- 第22章 圖的基本算法 22.5 強聯通分支