广度优先搜索

黄蕊小白花

算法过程：

1.将根节点放入队列中

2.从队列中取出第一个元素，将队列中的第一个元素弹出

3.将所取得元素的全部节点加入队列中

4.判断队列是否为空

     a. 若是，则结束

     b.若不是，则跳到第二步

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. const int verMax=9;
   
5. const int queMax=10; // >=9皆可
   
6. 
   
7. struct node//声明图形顶点结构
   
8. {
   
9. int vertex;
   
10. struct node *next;
    
11. };
    
12. 
    
13. typedef struct node *graph;
    
14. struct node head[verMax];//声明顶点结构数组
    
15. int que[queMax];
    
16. int front=-1;
    
17. int rear=-1;
    
18. int visit[verMax];//查找记录//队列的存入
    
19. 
    
20. int enque(int v)
    
21. {
    
22.     if(rear>=queMax)//队列已满
    
23.     return -1;
    
24. else
    
25. {
    
26.     rear++;//对了尾端指针后移
    
27.     que[rear]=v;//将值存入队列中
    
28.     return 1;
    
29.     }
    
30. }
    
31. //队列的取出
    
32. int deque()
    
33. {
    
34.     if(front==rear)//队列已空
    
35.         return -1;
    
36.     else
    
37.     {
    
38.         front++;
    
39.         return que[front];
    
40.     }
    
41. }
    
42. //广度优先搜索法
    
43. void BFS(int v)
    
44. {
    
45.     graph point;
    
46.     enque(v);//存入队列
    
47.     visit[v]=1;//已查找
    
48.     cout<<"["<<v<<"]==>";
    
49.     while(front!=rear)
    
50.     {
    
51.         v=deque();
    
52.         point=head[v].next;
    
53.         while(point!=NULL)//读入邻接列表所有顶点
    
54.         {
    
55.             if(visit[point->vertex]==0)
    
56.             {
    
57.                 enque(point->vertex);//存入队列
    
58.                 visit[point->vertex]=1;//已查找过的顶点
    
59.                 cout<<"["<<point->vertex<<"]==>";
    
60.             }
    
61.             point=point->next;
    
62.         }
    
63.     }
    
64. }
    
65. //建立邻接顶点至邻接列表内
    
66. void create_graph(int v1,int v2)
    
67. {
    
68.     graph point,New;
    
69.     New=(graph)malloc(sizeof(struct node));
    
70.     if(New!=NULL)
    
71.     {
    
72.         New->vertex=v2;//邻近顶点
    
73.         New->next=NULL;
    
74.         point=&(head[v1]);
    
75.         while(point->next!=NULL)
    
76.             point=point->next;
    
77.         point->next=New;//串连在列表尾端
    
78.     }
    
79. }
    
80. //输出邻接列表内数据
    
81. void print_graph(struct node *head)
    
82. {
    
83.     graph point;
    
84.     point=head->next;//设置point为首节点
    
85.     while(point!=NULL)
    
86.     {
    
87.         cout<<"["<<point->vertex<<"] ";
    
88.         point=point->next;
    
89.     }
    
90.     cout<<endl;
    
91. }
    
92. //主程序
    
93. void main()
    
94. {
    
95.     int node[20][2]={
    
96.     {1,2},{2,1},{1,3},{3,1},{2,4},{4,2},{2,5},{5,2},{3,6},{6,3},
    
97.     {3,7},{7,3},{4,8},{8,4},{5,8},{8,5},{6,8},{8,6},{7,8},{8,7}};
    
98.     int i;
    
99.     for(i=0;i<verMax;i++)
    
100.     {
     
101.         head[i].vertex=i;
     
102.         head[i].next=NULL;
     
103.     }
     
104.     for(i=0;i<verMax;i++)
     
105.         visit[i]=0;
     
106. 
     
107.     for(i=0;i<20;i++)
     
108.         create_graph(node[i][0],node[i][1]);
     
109. 
     
110.     cout<<"======Graph======"<<endl;
     
111.     for(i=1;i<verMax;i++)
     
112.     {
     
113.         cout<<"Vertex["<<i<<"]: ";
     
114.         print_graph(&head[i]);
     
115.     }
     
116.     //广度优先搜索
     
117.     cout<<"Bradth-First-Search:"<<endl<<"&BEGIN==>";
     
118.     BFS(4);
     
119.     cout<<"END&"<<endl;
     
120. }

复制代码