【算法导论】--C++实现广度优先搜索bfs

 1 enum Color{white,red,green};//设定每个顶点的颜色,white表示还没有碰到的，green表示在队列中的，red表示已经完成的
 2 
 3 struct vertextype//表示图中的每个顶点的类型
 4 {
 5     int id;//每个顶点的编号
 6     int pred;//每个顶点的前驱顶点
 7     int dist;//每个顶点的距离
 8     enum Color color;//设定顶点的状态
 9 };
10 
11 struct MGraph//邻接矩阵表示法的结构和类型声明
12 {
13     vertextype V[maxvertexnum];//顶点集
14     edgetype E[maxvertexnum][maxvertexnum];//边集
15     int n,e;//顶点数，边数
16     enum GraphType GType;//设定图的类型
17 };

 1 void bfs(MGraph *G,vertextype s)
 2 {
 3     int i,j,k=0;
 4     for(i=0;i<100;i++)//初始化图中所有点，使其全部为未被碰到的，以及没有前驱，没有距离,100表示生成图中只有100个顶点，根据生成的图具体定义
 5     {
 6         if (s.id==i)
 7         {    
 8             continue;//跳过初始点s
 9         }else
10         {
11             G->V[i].color=white;
12             G->V[i].dist=infinity;
13             G->V[i].pred=NULL;
14             //cout<<"["<<G->V[i].id<<","<<G->V[i].pred<<","<<G->V[i].color<<"]	";
15         }
16     }
17     s.color=green;//将初始点入队
18     s.dist=0;
19     s.pred=NULL;
20     queue<vertextype> Q;//创建一个空队列
21     Q.push(s);//将初始点入队列
22     cout<<"["<<s.id<<","<<s.pred<<","<<s.color<<"]"<<endl;//此处都为打印验证可以将其注释
23 
24     cout<<endl;
25     while(!Q.empty())//当队列非空
26     {
27         vertextype u,v;//建立一个空顶点
28         u=Q.front();//取出队列第一个元素
29         Q.pop();//将队列中第一个元素删除
30         cout<<endl;
31         cout<<"====["<<u.id<<","<<u.pred<<","<<u.color<<"]====="<<endl;//此处为打印验证可以注释
32         
33         int i,j;
34         for(i=0;i<100;i++)
35         {
36             //v=G->V[i];
37             if(G->E[u.id][i]==0)//在u的邻接矩阵中找到它的邻接顶点，当为0时跳过
38             {
39                 continue;
40             }
41             else if(G->V[i].color==white)
42             {
43                 G->V[i].color=green;
44                 G->V[i].dist=u.dist+1;
45                 G->V[i].pred=u.id;
46                 Q.push(G->V[i]);
47                 k++;//记录整张图上可以到达的点的个数
48                 cout<<"["<<G->V[i].id<<","<<G->V[i].pred<<","<<G->V[i].color<<","<<G->V[i].dist<<"]	";//此处为打印验证可以注释
49             }
50         }
51         u.color=red;
52     }
53     cout<<endl;
54     cout<<"================="<<k<<"==============="<<endl;//此处为打印验证可以注释
55 }

 1 vertextype findid(MGraph *G,int id)//找到对应id的顶点，并返回,当没有时返回空
 2 {
 3     return G->V[id];
 4 }
 5 
 6 
 7 void printpath(MGraph *G,vertextype s,vertextype v)
 8 {
 9     //s为其实顶点，v为所要寻找的顶点,
10     //使用递归来进行每一步的更往前寻找pred
11     vertextype u;
12     //vertextype *record=new vertextype[100];
13     int i,j;
14     if(v.id==s.id)
15         cout<<" ->"<<s.id<<" ";
16     else 
17         {
18             if(v.pred==NULL)
19             {
20                 cout<<"没有顶点"<<s.id<<"到顶点"<<v.id<<"的路径"<<endl;
21             }
22             else
23             {
24                 u=findid(G,v.pred);//u表示为v的前置节点
25                 printpath(G,s,u);
26                 cout<<"->"<<v.id<<" ";
27             }
28     }
29 }

 1 int main()
 2 {
 3     ofstream myuggraph,mydggraph;
 4     myuggraph.open("myuggraph.txt");
 5 
 6     MGraph *UGG=new MGraph();
 7     CreateMGraphUG(UGG);
 8     for(int i=0;i<100;i++)
 9     {
10         myuggraph<<UGG->V[i].id<<"	";
11         for(int j=0;j<100;j++)
12         {
13             myuggraph<<UGG->E[i][j]<<" ";//将整个邻接矩阵写到一个文本文件中，也是为了便于纠错吧
14         }
15         myuggraph<<"
";
16     }
17     
18     bfs(UGG,UGG->V[3]);
19     cout<<endl;
20     cout<<"======================";
21     cout<<endl;
22     printpath(UGG,UGG->V[3],UGG->V[75]);
23     cout<<endl;
24 
25     return 0;
26 }

1 #include<iostream>
2 #include<fstream>
3 #include<queue>//引入队列头文件