图的深度优先搜索和广度优先搜索具有很多实用价值,我写这两个算法花了好久,最终的到了几个宝贝而惨痛的经验。
总结如下:
1、以图的深度优先搜索未例，该问题本身具有递归的性质，我试着借助栈的来实现深度优先搜索的非递归算法，费了好大的力气，还是没有弄出来。
如果问题本身具有递归性质,则用递归算法几乎是最好的方法。
2、当面临一个复杂问题,该问题中用到了其他的功能,把其中这些功能分出来写成独立的函数实现几乎是最好的方法.从《操作系统的设计和实现》中可以看到，当作者处理一个复杂问题时，并不会考虑其中用的功能如何实现，只用一个函数来表示，这样简化了问题的解答，是解决复杂问题的方法。
3、单步调试威力无穷，当程序在大多数情况下工作正常时，问题出在别的地方。
下面给出图的深度优先搜索算法和广度优先搜索算法:
/*
广度优先遍历算法：（类似层次遍历）
1、首先访问当前顶点v，并设置该顶点的访问标志visited[v]=true。
2、然后访问v的各个未曾被访问过的邻接顶点w1,w2,...wt,然后再访问w1,w2...,wt的
所有未被访问过的邻接顶点。这里需要将先访问的顶点入队,出队。
3、再从这些顶点出发，访问它们未被访问过的邻接点。
具体算法:
1、声明一个visited数组和一个bfs数组用于记录访问与否和访问次序。
2、首先访问结点0。
3、使用STL中的函数库queue来进行队列的入队出队操作。将第一个结点入队。
4、如果该队列不为空，则出队，找到该元素的第一个邻接点。
5、如果该邻接点不为空，且未被访问过，则访问并将该结点入队。
6、找该结点的下一个邻接点。
*/
void LinkedGraph::BFSGraph(LinkedGraph *lg)
{
cout<<"---------广度优先遍历---------"<<endl;
bool visited[9];
int count=0;
for(int i=0;i<9;i++) //声明一个访问记录数组
visited[i]=false;
int bfs[9]; //记录访问的次序数组
//初始化这个数组
for(int i=0;i<9;i++)
bfs[i]=0;
//GraphEdge *q; //用于前一步所访问的顶点，很重要,不可实现
visited[0]=true;
bfs[0]=0;
//自己定义的队列有问题，改用C++标准函数库
//Queue qg;
//qg.EnQueue(0); //顶点入队,循环遍历整个图
queue<int> qg;
qg.push(0); //入队
while(!qg.empty()) //每次访问该层所有的结点
{
int d=qg.front(); //将上次访问的顶点出队
qg.pop(); //出队，并删除第一个元素,猜对了,哈哈
int w=lg->getFirstNeighbour(d); //找到顶点d的第一邻接点
while(w!=-1) //如果这个邻接点存在
{
if(visited[lg->getVerPosition(w)]==false) //如果顶点没有被访问过
{
count++ ; //顶点数加1
bfs[count]=w;
int loc=lg->getVerPosition(w); //获得w的顶点好
visited[loc]=true;
qg.push(w); //将访问过的该结点入队
}
w=lg->getNextNeighbour(d,w); //遍历顶点d的所有邻接点，并且将访问过的结点入队
}
}
//打印顶点的访问次序
for(int i=0;i<9;i++)
cout<<bfs[i]<<"--";
cout<<endl;
}
/*
深度优先搜索算法：(以连通图作为例子)
由于要用到上一次访问过的结点，用一个辅助栈来表示。
1、给定一个起始顶点,每一步探查过程中,首先对当前顶点进行访问,并立即设置该
顶点的访问标志为true。
2、接着在v的所有邻接点中选一个未被访问的作为当前的探查结点，
3、如果当前顶点的所有邻接点都已经被访问过,则把上一次访问的顶点取出,当做探查的当前顶点.
*/
程序的算法以程序的注释为准:
void LinkedGraph::DFSGraph(LinkedGraph *lg,int data)
{
int i;
bool visited[9];
for(i=0;i<9;i++)visited[i]=false;
DFSGraph(lg,data,visited); //递归处理
}
void LinkedGraph::DFSGraph(LinkedGraph *lg,int data,bool visited[])
{
//递归子程序
cout<<v[lg->getVerPosition(data)].data<<" "; //打印该结点
visited[lg->getVerPosition(data)]=true; //设置该结点的访问标志为true
int w=lg->getFirstNeighbour(data); //找第一个邻接点
while(w!=-1) //邻接点存在
{
if(visited[lg->getVerPosition(w)]==false) //如果这个顶点没有被访问过
DFSGraph(lg,w,visited); //递归的访问当前顶点
w=lg->getNextNeighbour(data,w); //找下一个邻接点
}
}
运行的结果如下:
---------广度优先遍历---------
0--1--2--3--4--5--6--7--8--
----------图的深度优先搜索------
0 1 4 6 2 5 3 7 8
------------------结束---------------