我有个可能对你来说不太易懂的程序，是对付stanford CS106B的course reader上的一个对应实现，你可以稍看一下，用了std::map，也许你不会，但你大可拿去运行一下，我不截图，你存为后缀cpp，应该可以在如vc下的编译器下运行。
#include <iostream>#include <vector>
#include <map>
#include <map>
#include <string>
#include <deque>
#include <stack>
#include <queue>
#include <utility>
class Graph {
public:
~Graph();
void addNode(const std::string & s);
void addDirectedEdge(const std::string & from, const std::string & to, int weight);
void addUndirectedEdge(const std::string & v1, const std::string & v2, int weight);
void DFT(const std::string & s);
void BFT(const std::string & s);
void dijkstra(const std::string & s);
private:
std::vector<std::map<int, int> > adjacencyList;
std::map<std::string, int> s2i;
std::map<int, std::string> i2s;
};
Graph::~Graph()
{
for (int i = 0; i < (int)adjacencyListsize(); ++i) {
delete adjacencyList[i];
}
}
void Graph::addNode(const std::string & s)
{
s2i[s] = (int)adjacencyListsize();
i2s[(int)adjacencyListsize()] = s;
adjacencyListpush_back(new std::map<int, int>());
}
void Graph::addDirectedEdge(const std::string & from, const std::string & to, int weight)
{
(adjacencyList[s2i[from]])[s2i[to]] = weight;
}
void Graph::addUndirectedEdge(const std::string & v1, const std::string & v2, int weight)
{
addDirectedEdge(v1, v2, weight);
addDirectedEdge(v2, v1, weight);
}
void Graph::DFT(const std::string & s)
{
std::deque<bool> visited(adjacencyListsize(), false);
int start = s2i[s];
std::stack<int> stk;
stkpush(start);
while (!stkempty()) {
int top = stktop();
stkpop();
if (visited[top]) {
continue;
}
std::cout << i2s[top] << std::endl;
visited[top] = true;
for (std::map<int, int>::reverse_iterator i = adjacencyList[top]->rbegin(); i != adjacencyList[top]->rend(); ++i) {
if (!visited[i->first]) {
stkpush(i->first);
}
}
}
}
void Graph::BFT(const std::string & s)
{
std::deque<bool> visited(adjacencyListsize(), false);
int start = s2i[s];
std::queue<int> q;
qpush(start);
while (!qempty()) {
int top = qfront();
qpop();
if (visited[top]) {
continue;
}
std::cout << i2s[top] << std::endl;
visited[top] = true;
for (std::map<int, int>::iterator i = adjacencyList[top]->begin(); i != adjacencyList[top]->end(); ++i) {
if (!visited[i->first]) {
qpush(i->first);
}
}
}
}
void Graph::dijkstra(const std::string & s)
{
int n = adjacencyListsize();
std::deque<bool> fixed(n, false);
int start = s2i[s];
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > > pq;
pqpush(std::pair<int, int>(0, start));
while (n > 0) {
std::pair<int, int> top = pqtop();
pqpop();
if (fixed[topsecond]) {
continue;
}
std::cout << i2s[topsecond] << ':' << topfirst << std::endl;
fixed[topsecond] = true;
--n;
for (std::map<int, int>::iterator i = adjacencyList[topsecond]->begin(); i != adjacencyList[topsecond]->end(); ++i) {
if (!fixed[i->first]) {
pqpush(std::pair<int, int>(topfirst + i->second, i->first));
}
}
}
}
int main()
{
Graph g;
gaddNode("Atlanta");
gaddNode("Boston");
gaddNode("Chicago");
gaddNode("Dallas");
gaddNode("Denver");
gaddNode("Los Angeles");
gaddNode("New York");
gaddNode("Portland");
gaddNode("San Francisco");
gaddNode("Seattle");
gaddUndirectedEdge("Atlanta", "Chicago", 599);
gaddUndirectedEdge("Atlanta", "Dallas", 725);
gaddUndirectedEdge("Atlanta", "New York", 756);
gaddUndirectedEdge("Boston", "New York", 191);
gaddUndirectedEdge("Boston", "Seattle", 2489);
gaddUndirectedEdge("Chicago", "Denver", 907);
gaddUndirectedEdge("Dallas", "Denver", 650);
gaddUndirectedEdge("Dallas", "Los Angeles", 1240);
gaddUndirectedEdge("Dallas", "San Francisco", 1468);
gaddUndirectedEdge("Denver", "San Francisco", 954);
gaddUndirectedEdge("Portland", "San Francisco", 550);
gaddUndirectedEdge("Portland", "Seattle", 130);
gDFT("San Francisco");
gBFT("San Francisco");
gdijkstra("San Francisco");
return 0;
}
（1）在产生新的子结点时，深度越小的结点越先得到扩展，即先产生它的子结点。为使算法便于实现，存放结点的数据库一般用队列的结构。
（2）无论问题性质如何不同，利用广度优先搜索法解题的基本算法是相同的，但数据库中每一结点内容，产生式规则，根据不同的问题，有不同的内容和结构，就是同一问题也可以有不同的表示方法。
（3）当结点到跟结点的费用（有的书称为耗散值）和结点的深度成正比时，特别是当每一结到根结点的费用等于深度时，用广度优先法得到的解是最优解，但如果不成正比，则得到的解不一定是最优解。这一类问题要求出最优解，一种方法是使用后面要介绍的其他方法求解，另外一种方法是改进前面深度（或广度）优先搜索算法：找到一个目标后，不是立即退出，而是记录下目标结点的路径和费用，如果有多个目标结点，就加以比较，留下较优的结点。把所有可能的路径
都搜索完后，才输出记录的最优路径。
（4）广度优先搜索算法，一般需要存储产生的所有结点，占的存储空间要比深度优先大得多，因此程序设计中，必须考虑溢出和节省内存空间得问题。
（5）比较深度优先和广度优先两种搜索法，广度优先搜索法一般无回溯 *** 作，即入栈和出栈的 *** 作，所以运行速度比深度优先搜索算法法要快些。
总之，一般情况下，深度优先搜索法占内存少但速度较慢，广度优先搜索算法占内存多但速度较快，在距离和深度成正比的情况下能较快地求出最优解。因此在选择用哪种算法时，要综合考虑。决定取舍！
我以前做的一个光搜题，给你贴上吧，是一个关于素数变化的题目，输入一对素数，每个是4位数，每次只能变化一位数，且变化后的数还是素数，求经过多少次变化，能变成另一个输入的素数。程序有点复杂，慢慢看吧。
#include<iostream>
#include<cmath>
using namespace std;
int temp,temp2,i,j;
int f(int t)
{
temp2 = sqrt(float(t))+1;
for(j=2;j<temp2;++j)
if(t%j==0)
return 0;
return 1;
}
int main()
{
int prime[10000],qu[20000],result,k,h,num,tag[10000],sum,index,itag,d[10000],atag;
while(1)
{
for(i = 1000;i<10000;++i) {tag[i] = 0,d[i]=0;}
cin>>num>>result;
k=0;h=1;qu[k]=num;index=0;itag=1;tag[num]=1;atag=0;
while(k!=h)
{
if(qu[k] == result)
{cout<<d[qu[k]]<<endl;break;}
if(qu[k]%2==0) continue;
temp=qu[k]-qu[k]%10+1;
for(i=0;i<5;i++,temp+=2)
if(f(temp)==1&&tag[temp]==0)
{tag[temp]=1;d[temp]=d[qu[k]]+1;qu[h]=temp;
if(temp==result){cout<<d[temp]<<endl;atag=1;break;}++h;}if(atag==1) break;
temp=qu[k]-qu[k]%100/1010;
for(i=0;i<10;++i,temp+=10)
if(f(temp)==1&&tag[temp]==0)
{tag[temp]=1;d[temp]=d[qu[k]]+1;qu[h]=temp;
if(temp==result){cout<<d[temp]<<endl;atag=1;break;}++h;}if(atag==1) break;
temp=qu[k]-qu[k]%1000/100100;
for(i=0;i<10;++i,temp+=100)
if(f(temp)==1&&tag[temp]==0)
{tag[temp]=1;d[temp]=d[qu[k]]+1;qu[h]=temp;
if(temp==result){cout<<d[temp]<<endl;atag=1;break;}++h;}if(atag==1) break;
temp=qu[k]-qu[k]/10001000+1000;
for(i=0;i<8;++i,temp+=1000)
if(f(temp)==1&&tag[temp]==0)
{tag[temp]=1;d[temp]=d[qu[k]]+1;qu[h]=temp;
if(temp==result){cout<<d[temp]<<endl;atag=1;break;}++h;}if(atag==1) break;
++k;
}
}
return 1;
}
//////////////////////////////////////////////////////////////////
//图是通过文件建立的
//数据元素为char类型
//存储结构为邻接表
//文件中第一行为图的类型
//第二行为节点元素，以#结束
//下边每一行为边，和边的权值
//下边是文件的示例
/
2
A B C D #
A B 3
A C 4
B C 2
C D 4
D A 1
# #
/
//////////////////////////////////////////////////////////////////
#include<iostream>
#include<fstream>
using namespace std;
const int MaxNum= 20;
const int Infinity=-1;
typedef char VexType;
typedef int ArcType;
typedef struct QNode
//定义队列节点
{
int data;
QNode next;
}LQueuePtr;
struct LQueue
//定义队列结构体
{
LQueuePtr front,rear;
};
void QueueInit(LQueue &Q)
//队列初始化
{
Qfront =new QNode;
Qfront ->next =0;
Qrear =Qfront ;
}
void Enqueue(LQueue &Q,int e)
{
LQueuePtr s;
s=new QNode;
s->data =e;
s->next =0;
Qrear ->next =s;
Qrear =s;
}
bool Dequeue(LQueue &Q,int &e)
{
LQueuePtr p;
if(Qfront ==Qrear ) return false;
p=Qfront ;
Qfront =p->next ;
e=Qfront ->data ;
delete p;
return true;
}
typedef struct ArcNode
//定义边的结构体
{
int adjvex;
ArcType info;
ArcNode nextarc;
}ArcPtr;
struct VexNode
//定义节点的结构体
{
VexType data;
ArcPtr firstarc;
};
struct ALGraph
//定义图的结构体
{
VexNode vexs[MaxNum+1];
int kind,vexnum,arcnum;
};
int LocateVex(ALGraph &G,VexType v)
//在图中找到某一个元素
{
int i;
for(i=Gvexnum ;i>0&&Gvexs [i]data !=v;i--);
return i;
}
void CreateGraph(ALGraph &G,char fn[])
//创建图
{
int i,j;
VexType u,v;
ArcPtr p;
ifstream f;
ArcType w;
fopen (fn);
//打开文件失败
if(!f)
{
Gvexnum =0;
return;
}
//读入图的种类
f>>Gkind ;
//先设置边数为0
Garcnum =0;
i=0;
while(true)
//向节点数组中添加节点
{
f>>u;
if('#'==u) break;
i++;
Gvexs [i]data =u;
Gvexs [i]firstarc =0;
}
Gvexnum =i;
while(true)
//读入各条边
{
f>>u>>v;
if('#'==u||'#'==v) break;
i=LocateVex(G,u);
if(0==i) continue;
j=LocateVex(G,v);
if(0==j||j==i) continue;
if(1==Gkind||3==Gkind )w=1;
else f>>w;
Garcnum ++;
p=new ArcNode;
p->adjvex =j;
p->info =w;
p->nextarc =Gvexs[i]firstarc ;
Gvexs[i]firstarc =p;
if(Gkind <=2) continue;
p=new ArcNode;
p->adjvex =i;
p->info =w;
p->nextarc =Gvexs[j]firstarc ;
Gvexs[j]firstarc =p;
}
fclose ();
}
void OutputGraph(ALGraph &G)
//输出图
{
int i;
ArcPtr p;
if(0==Gvexnum )
{
cout<<"空图"<<endl;
return ;
}
cout<<"顶点数="<<Gvexnum <<" 弧数="<<Garcnum <<endl<<"顶点：";
for(i=1;i<=Gvexnum ;i++) cout<<Gvexs [i]data <<' ';
cout<<endl<<"出弧:"<<endl;
for(i=1;i<=Gvexnum ;i++)
{
cout<<"顶点"<<Gvexs [i]data <<endl;
for(p=Gvexs [i]firstarc ;p;p=p->nextarc )
cout<<" <"<<Gvexs [i]data <<","<<Gvexs [p->adjvex ]data <<"> "<<p->info <<endl;
}
}
void visit(VexType x)
{
cout<<x;
}
void DFS(ALGraph &G,int i,bool visited[],void visit(VexType))
//图的名称，当前节点位置，标记数组，访问函数
{
int j;
ArcPtr p;
//访问当前节点
visit(Gvexs [i]data );
//修改标记值
visited[i]=true;
for(p=Gvexs[i]firstarc ;p;p=p->nextarc )
{
j=p->adjvex ;
if(!visited[j])
//对下一个节点递归
DFS(G,j,visited,visit);
}
}
void DFSTraverse(ALGraph &G,void visit(VexType))
{
int i;
bool visited[MaxNum+1];
for(i=1;i<=Gvexnum ;i++)
//初始化标记数组
{
visited[i]=false;
}
for(i=1;i<=Gvexnum ;i++)
{
if(!visited[i])
{
DFS(G,i,visited,visit);
}
}
}
void BFSTraverse(ALGraph &G,void visit(VexType))
{
int u,v,w;
ArcPtr p;
LQueue q;
bool visited[MaxNum+1];
//初始化标记数组
for(v=1;v<=Gvexnum ;v++)
visited[v]=false;
QueueInit(q);
for(v=1;v<=Gvexnum ;v++)
if(!visited[v])
{
//访问节点
visit(Gvexs[v]data );
visited[v]=true;
//将访问的节点入队
Enqueue(q,v);
while(Dequeue(q,u))
//出队并访问
{
for(p=Gvexs[u]firstarc ;p;p=p->nextarc )
{
w=p->adjvex ;
if(!visited[w])
{
visit(Gvexs[w]data );
visited[w]=true;
Enqueue(q,w);
}
}
}
}
}
int main()
{
ALGraph G;
CreateGraph(G,"aaatxt");
cout<<"创建的图为:";
OutputGraph(G);
cout<<"深度优先遍历："<<endl;
DFSTraverse(G,visit);
cout<<endl<<"广度优先遍历"<<endl;
BFSTraverse(G,visit);
cout<<endl;
return 0;
}
以上就是关于求简单易懂广度优先搜索c++代码全部的内容，包括:求简单易懂广度优先搜索c++代码、数据结构 深度和广度优先搜索、广度优先搜索算法等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）