广度优先搜索

黄蕊小白花

算法过程：

1.将根节点放入队列中

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

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

4.判断队列是否为空

     a. 若是，则结束

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

1. #include <iostream>
   
2. using namespace std;
     x) F7 i' v6 {) U4 f7 x1 x4 Z' Y% M
3. 
   - r7 d- @- H) M1 q* o
4. const int verMax=9;
   
5. const int queMax=10; // >=9皆可
   1 s7 F/ @/ v$ e( }
6. 
   
7. struct node//声明图形顶点结构
   
8. {
   ' t3 B/ l" h: i: u: q
9. int vertex;
   
10. struct node *next;
    5 M3 ?% c# i- [. o' e
11. };
    " E  z# o, ^/ j, _
12. 
    2 h) K6 k& ~: Z3 t
13. typedef struct node *graph;
    
14. struct node head[verMax];//声明顶点结构数组
      V! A/ d' n3 t
15. int que[queMax];
    
16. int front=-1;
    
17. int rear=-1;
    5 D$ _6 C( h9 V( A/ Z( @
18. int visit[verMax];//查找记录//队列的存入
    
19. 
    4 u# `$ w) L2 T9 ]7 Q; X3 K
20. int enque(int v)
    
21. {
    3 M5 l) j" ^- x5 @: p0 \) R
22.     if(rear>=queMax)//队列已满
    
23.     return -1;
    ' Z6 b; k0 r: l7 f: V% U  w2 C" B
24. else
    1 j+ Q. c1 C0 t. i1 {2 x
25. {
    - q: n3 k6 ^/ `' ~+ [6 Y
26.     rear++;//对了尾端指针后移
    7 x) ^# V  R. d( J0 @
27.     que[rear]=v;//将值存入队列中
    , Q  Y# ~5 Z2 C% V! d" a( l
28.     return 1;
    9 N8 M9 K- m5 \
29.     }
    # c$ w* Z% l; j5 R" Q  D
30. }
    9 R. ^; Q: D+ S# }' ?/ F
31. //队列的取出
    
32. int deque()
    5 d' o/ f; v0 }3 p. t5 {
33. {
    
34.     if(front==rear)//队列已空
    
35.         return -1;
    
36.     else
    7 L0 r; [" O5 X1 u$ n: k
37.     {
    
38.         front++;
    : @) {0 K( b0 D4 k
39.         return que[front];
    / R; J/ d8 d2 L* i
40.     }
    + [2 d/ \' X! @
41. }
    1 o4 N  h5 p( |- u
42. //广度优先搜索法
    
43. void BFS(int v)
    
44. {
    
45.     graph point;
    7 f  i/ L8 l' p6 i! ?- F$ A5 p
46.     enque(v);//存入队列
    9 S+ [: w+ S& \* C) ~' F
47.     visit[v]=1;//已查找
    
48.     cout<<"["<<v<<"]==>";
    ; l' P7 e$ d+ s5 d4 f5 H* r
49.     while(front!=rear)
    5 }4 j) x0 G$ }' z  F
50.     {
    
51.         v=deque();
    / ?$ J% f$ _/ T
52.         point=head[v].next;
    " B5 m& F5 h$ S; }/ n6 G
53.         while(point!=NULL)//读入邻接列表所有顶点
    
54.         {
    
55.             if(visit[point->vertex]==0)
    1 ^! |- U4 b. X% o2 [2 m; Q8 c
56.             {
    & r- V. ~- e, g
57.                 enque(point->vertex);//存入队列
    % F% ^" D8 S! V4 Y, v- e
58.                 visit[point->vertex]=1;//已查找过的顶点
    
59.                 cout<<"["<<point->vertex<<"]==>";
    / Q" m( f9 H* [
60.             }
    
61.             point=point->next;
    / U5 A$ v) v5 F; v1 {4 y) j5 I
62.         }
    ! t' {  d4 T# ~' u9 F
63.     }
    
64. }
    * P, s" {$ V+ ?" H
65. //建立邻接顶点至邻接列表内
    
66. void create_graph(int v1,int v2)
    & x; [+ D5 d" t5 A! P4 K
67. {
    
68.     graph point,New;
    + V% d. ]* U/ A* c7 Q
69.     New=(graph)malloc(sizeof(struct node));
    
70.     if(New!=NULL)
    3 V. K5 T* f8 G# t9 s+ K0 o
71.     {
    2 R) ~8 j0 q  D& L
72.         New->vertex=v2;//邻近顶点
    ) Q; Y/ K- z8 J; [/ _( J% g+ r
73.         New->next=NULL;
    , T% H! H3 x1 ?: P# p
74.         point=&(head[v1]);
    
75.         while(point->next!=NULL)
    
76.             point=point->next;
    
77.         point->next=New;//串连在列表尾端
    - F5 Q3 ^& s7 F1 m/ V  [
78.     }
    
79. }
    4 \; t: b# a) W  q
80. //输出邻接列表内数据
    0 f; b2 R, H, Q  u+ h  B0 y7 ^! d+ n9 I6 O
81. void print_graph(struct node *head)
    # q' K- K  ]1 i/ j3 t9 k3 ?
82. {
    0 C" Z" c" c/ [" j2 i, T( a  S& M
83.     graph point;
    
84.     point=head->next;//设置point为首节点
      N! D$ l7 f" c% R! c" `
85.     while(point!=NULL)
    ' T5 C' f+ V4 ?' L- v7 j  f2 o0 i- i7 i
86.     {
    
87.         cout<<"["<<point->vertex<<"] ";
    
88.         point=point->next;
    
89.     }
    
90.     cout<<endl;
    - b! V% S/ C( B
91. }
    
92. //主程序
    + ^2 o' r7 v* n: Y+ Q
93. void main()
    
94. {
    # q1 @5 M' {8 P8 y5 S) @" ?
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;
    6 _6 `. C- v' \" g# H3 [* r
99.     for(i=0;i<verMax;i++)
    
100.     {
     
101.         head[i].vertex=i;
     
102.         head[i].next=NULL;
     7 \. Z' z0 Z( ]9 h: x7 W% Z
103.     }
     / F! e$ ]2 |4 s. h# \
104.     for(i=0;i<verMax;i++)
     
105.         visit[i]=0;
     1 {8 B4 [& W: H. C
106. 
     $ Y  f5 t% W$ @: ]" K
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++)
     ! }3 z! r, e; G  [) |/ s& e
112.     {
     
113.         cout<<"Vertex["<<i<<"]: ";
     : l  n4 G$ {4 A
114.         print_graph(&head[i]);
     
115.     }
     / D; U( n6 R. v3 ~7 f- o  E. B
116.     //广度优先搜索
     
117.     cout<<"Bradth-First-Search:"<<endl<<"&BEGIN==>";
     3 c9 h  n, o+ @' E
118.     BFS(4);
     
119.     cout<<"END&"<<endl;
     ; M" Q7 B9 X7 g9 {
120. }

复制代码

6 [) b! j5 G+ f* j- F7 G% n2 b) c) I
) \3 H5 w% B0 s# |: S) C% t8 {/ |& t