首页 > 代码库 > 十大基础实用算法之深度优先搜索和广度优先搜索
十大基础实用算法之深度优先搜索和广度优先搜索
深度优先搜索算法（Depth-First-Search），是搜索算法的一种。它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。DFS属于盲目搜索。
深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。
深度优先遍历图算法步骤：
1. 访问顶点v；
2. 依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
3. 若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。
上述描述可能比较抽象，举个实例：
DFS 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻 接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问，… 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。
接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。
深度优先搜索的图文介绍
下面以"无向图"为例，来对深度优先搜索进行演示。
对上面的图G1进行深度优先遍历，从顶点A开始。
第1步：访问A。
第2步：访问(A的邻接点)C。
在第1步访问A之后，接下来应该访问的是A的邻接点，即"C,D,F"中的一个。但在本文的实现中，顶点ABCDEFG是按照顺序存储，C在"D和F"的前面，因此，先访问C。
第3步：访问(C的邻接点)B。
在第2步访问C之后，接下来应该访问C的邻接点，即"B和D"中一个(A已经被访问过，就不算在内)。而由于B在D之前，先访问B。
第4步：访问(C的邻接点)D。
在第3步访问了C的邻接点B之后，B没有未被访问的邻接点；因此，返回到访问C的另一个邻接点D。
第5步：访问(A的邻接点)F。
前面已经访问了A，并且访问完了"A的邻接点B的所有邻接点(包括递归的邻接点在内)"；因此，此时返回到访问A的另一个邻接点F。
第6步：访问(F的邻接点)G。
第7步：访问(G的邻接点)E。
因此访问顺序是：A -> C -> B -> D -> F -> G -> E
下面以"有向图"为例，来对深度优先搜索进行演示。
对上面的图G2进行深度优先遍历，从顶点A开始。
第1步：访问A。
第2步：访问B。
在访问了A之后，接下来应该访问的是A的出边的另一个顶点，即顶点B。
第3步：访问C。
在访问了B之后，接下来应该访问的是B的出边的另一个顶点，即顶点C,E,F。在本文实现的图中，顶点ABCDEFG按照顺序存储，因此先访问C。
第4步：访问E。
接下来访问C的出边的另一个顶点，即顶点E。
第5步：访问D。
接下来访问E的出边的另一个顶点，即顶点B,D。顶点B已经被访问过，因此访问顶点D。
第6步：访问F。
接下应该回溯"访问A的出边的另一个顶点F"。
第7步：访问G。
因此访问顺序是：A -> B -> C -> E -> D -> F -> G
下面介绍广度优先搜索
广度优先搜索算法（Breadth-First-Search），是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。
算法步骤：
1. 首先将根节点放入队列中。
2. 从队列中取出第一个节点，并检验它是否为目标。
- 如果找到目标，则结束搜寻并回传结果。
- 否则将它所有尚未检验过的直接子节点加入队列中。
3. 若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
4. 重复步骤2。
广度优先搜索图文介绍
下面以"无向图"为例，来对广度优先搜索进行演示。还是以上面的图G1为例进行说明。
第1步：访问A。
第2步：依次访问C,D,F。
在访问了A之后，接下来访问A的邻接点。前面已经说过，在本文实现中，顶点ABCDEFG按照顺序存储的，C在"D和F"的前面，因此，先访问C。再访问完C之后，再依次访问D,F。
第3步：依次访问B,G。
在第2步访问完C,D,F之后，再依次访问它们的邻接点。首先访问C的邻接点B，再访问F的邻接点G。
第4步：访问E。
在第3步访问完B,G之后，再依次访问它们的邻接点。只有G有邻接点E，因此访问G的邻接点E。
因此访问顺序是：A -> C -> D -> F -> B -> G -> E
下面以"有向图"为例，来对广度优先搜索进行演示。还是以上面的图G2为例进行说明。
第1步：访问A。
第2步：访问B。
第3步：依次访问C,E,F。
在访问了B之后，接下来访问B的出边的另一个顶点，即C,E,F。前面已经说过，在本文实现中，顶点ABCDEFG按照顺序存储的，因此会先访问C，再依次访问E,F。
第4步：依次访问D,G。
在访问完C,E,F之后，再依次访问它们的出边的另一个顶点。还是按照C,E,F的顺序访问，C的已经全部访问过了，那么就只剩下E,F；先访问E的邻接点D，再访问F的邻接点G。
因此访问顺序是：A -> B -> C -> E -> F -> D -> G
借用知乎里的一句话，Talk is cheap,show me your code.邻接矩阵的无向图：（代码经过实验，可产生如上的访问顺序）
#include <iostream>
using namespace std;
const int MAX = 100;
class MatrixUDG
{
public:
MatrixUDG();//创建图，自己输入数据
MatrixUDG(char vexs[],int vlen,char edges[][2],int elen);//使用已经存在的矩阵
~MatrixUDG();
void DFS();
void BFS();
void print();
private:
char mVexs[MAX];//顶点集合
int mVexNum; //顶点数
int mEdgNum; //边数
int mMatrix[MAX][MAX]; //邻接矩阵
char readChar();//读取一个输入字符串
int getPosition(char ch);//返回ch在mMatrix矩阵中的位置
int firstVertex(int v);//返回顶点v的第一个邻接顶点的索引，失败则返回-1
int nextVertex(int v,int w);//返回顶点v的相对于顶点w的下一个索引，失败则返回-1
void DFS(int i,int *visted);//深度优先搜索遍历图的递归实现
};
MatrixUDG::MatrixUDG()
{
char c1,c2;
int i,p1,p2;
//input vertex and edge number
cout<<"input vertex number:";
cin>>mVexNum;
cout<<"input edge number:";
cin>>mEdgNum;
if(mVexNum<1 || mEdgNum<1 || mEdgNum>mVexNum*(mVexNum - 1))
{
cout<<"input error:invalid parameters!";
return;
}
// init vertex
for(i = 0;i<mVexNum;i++)
{
cout<<"vertex("<<i<<")"<<endl;
mVexs[i] = readChar();
}
//init edge
for(i = 0;i<mEdgNum;i++)
{
cout<<"edge("<<i<<")";
c1 = readChar();
c2 = readChar();
p1 = getPosition(c1);
p2 = getPosition(c2);
if(p1 == -1 || p2 == -1)
{
cout<<"input error:invalid parameters."<<endl;
return;
}
mMatrix[p1][p2] = 1;
mMatrix[p2][p1] = 1;
}
}
MatrixUDG::MatrixUDG(char vexs[], int vlen, char edges[][2], int elen)
{
int i, p1, p2;
// 初始化"顶点数"和"边数"
mVexNum = vlen;
mEdgNum = elen;
// 初始化"顶点"
for (i = 0; i < mVexNum; i++)
mVexs[i] = vexs[i];
// 初始化"边"
for (i = 0; i < mEdgNum; i++)
{
// 读取边的起始顶点和结束顶点
p1 = getPosition(edges[i][0]);
p2 = getPosition(edges[i][1]);
mMatrix[p1][p2] = 1;
mMatrix[p2][p1] = 1;
}
}
MatrixUDG::~MatrixUDG()
{}
int MatrixUDG::getPosition(char ch)
{
int i;
for(i = 0;i<mVexNum;i++)
if(mVexs[i] == ch)
return i;
return -1;
}
char MatrixUDG::readChar()
{
char ch;
do
{
cin>>ch;
}while(!((ch>='a' && ch<='z') || (ch>='A' && ch<='Z')));
return ch;
}
int MatrixUDG::firstVertex(int v)
{
int i;
if(v<0 || v>(mVexNum - 1))
return -1;
for(i = 0;i<mVexNum;i++)
{
if(mMatrix[v][i] == 1)
return i;
}
return -1;
}
int MatrixUDG::nextVertex(int v,int w)
{
int i;
if(v<0 || v>(mVexNum - 1) || w<0 || w>(mVexNum - 1))
return -1;
for(i = w+1;i<mVexNum;i++)
{
if(mMatrix[v][i] == 1)
return i;
}
return -1;
}
void MatrixUDG::DFS(int i,int *visted)
{
int w;
visted[i] = 1;
cout<<mVexs[i]<<' ';
for(w = firstVertex(i);w>=0;w = nextVertex(i,w))
{
if(!visted[w])
DFS(w,visted);
}
}
void MatrixUDG::DFS()
{
int i;
int visted[MAX];
for(i = 0;i<mVexNum;i++)
visted[i] = 0;
cout<<"DFS:";
for(i = 0;i<mVexNum;i++)
{
if(!visted[i])
DFS(i,visted);
}
cout<<endl;
}
void MatrixUDG::BFS()
{
int head = 0;
int rear = 0;
int queue[MAX];
int visted[MAX];
int i,j,k;
for(i = 0;i<mVexNum;i++)
visted[i] = 0;
cout<<"BFS:";
for(i = 0;i<mVexNum;i++)
{
if(!visted[i])
{
visted[i] = 1;
cout<<mVexs[i]<<' ';
queue[rear++] = i;//in queue
}
while(head != rear)
{
j = queue[head++];
for(k = firstVertex(j);k >= 0;k = nextVertex(j,k))
{
if(!visted[k])
{
visted[k] = 1;
cout<<mVexs[k]<<" ";
queue[rear++] = k;
}
}
}
}
cout<<endl;
}
void MatrixUDG::print()
{
int i,j;
cout<<"Matrix Graph:"<<endl;
cout<<" A B C D E F G"<<endl;
for(i = 0;i<mVexNum;i++)
{
cout<<mVexs[i]<<" ";
for(j = 0;j<mVexNum;j++)
cout<<(mMatrix[i][j] == 1?1:0)<<" ";
cout<<endl;
}
}
int main()
{
char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
char edges[][2] = {
{'A', 'C'},
{'A', 'D'},
{'A', 'F'},
{'B', 'C'},
{'C', 'D'},
{'E', 'G'},
{'F', 'G'}};
int vlen = sizeof(vexs)/sizeof(vexs[0]);
int elen = sizeof(edges)/sizeof(edges[0]);
MatrixUDG* pG;
// 自定义"图"(输入矩阵队列)
//pG = new MatrixUDG();
// 采用已有的"图"
pG = new MatrixUDG(vexs, vlen, edges, elen);
pG->print(); // 打印图
pG->DFS(); // 深度优先遍历
pG->BFS(); // 广度优先遍历
return 0;
}其中有向图的改动较小，只需要在添加边的时候添加一条边即可。不再显示代码。
以下是邻接表的实现，关键的是节点定义和访问方法的改变。
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
#define MAX 100
// 邻接表
class ListUDG
{
private: // 内部类
// 邻接表中表对应的链表的顶点
class ENode
{
public:
int ivex; // 该边所指向的顶点的位置
ENode *nextEdge; // 指向下一条弧的指针
};
// 邻接表中表的顶点
class VNode
{
public:
char data; // 顶点信息
ENode *firstEdge; // 指向第一条依附该顶点的弧
};
private: // 私有成员
int mVexNum; // 图的顶点的数目
int mEdgNum; // 图的边的数目
VNode mVexs[MAX];
public:
// 创建邻接表对应的图(自己输入)
ListUDG();
// 创建邻接表对应的图(用已提供的数据)
ListUDG(char vexs[], int vlen, char edges[][2], int elen);
~ListUDG();
// 深度优先搜索遍历图
void DFS();
// 广度优先搜索（类似于树的层次遍历）
void BFS();
// 打印邻接表图
void print();
private:
// 读取一个输入字符
char readChar();
// 返回ch的位置
int getPosition(char ch);
// 深度优先搜索遍历图的递归实现
void DFS(int i, int *visited);
// 将node节点链接到list的最后
void linkLast(ENode *list, ENode *node);
};
/*
* 创建邻接表对应的图(自己输入)
*/
ListUDG::ListUDG()
{
char c1, c2;
int v, e;
int i, p1, p2;
ENode *node1, *node2;
// 输入"顶点数"和"边数"
cout << "input vertex number: ";
cin >> mVexNum;
cout << "input edge number: ";
cin >> mEdgNum;
if ( mVexNum < 1 || mEdgNum < 1 || (mEdgNum > (mVexNum * (mVexNum-1))))
{
cout << "input error: invalid parameters!" << endl;
return ;
}
// 初始化"邻接表"的顶点
for(i=0; i<mVexNum; i++)
{
cout << "vertex(" << i << "): ";
mVexs[i].data = http://www.mamicode.com/readChar();>