广度优先搜索

黄蕊小白花

算法过程：

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皆可
   / m9 C3 z  b% X' J% W. I8 h' ~( x, o4 |
6. 
   
7. struct node//声明图形顶点结构
   
8. {
   3 ~" ]+ |" i  x# d
9. int vertex;
   + y/ L! t. j( `- l/ @, ^$ g0 k3 {1 ?
10. struct node *next;
    
11. };
    3 x- I. |9 S$ Y8 ~& o5 {' Z
12. 
    0 V4 X) v4 u  e# S9 N1 C! Y
13. typedef struct node *graph;
    
14. struct node head[verMax];//声明顶点结构数组
    
15. int que[queMax];
    
16. int front=-1;
    4 j2 x% y5 ]( c
17. int rear=-1;
    
18. int visit[verMax];//查找记录//队列的存入
    6 b+ g1 k# D2 s8 V" m: {, @
19. 
    ) U7 [! N* C! c" D! N( l
20. int enque(int v)
    
21. {
    
22.     if(rear>=queMax)//队列已满
    
23.     return -1;
    
24. else
    % |4 X/ y; @' K- V/ x; o
25. {
    
26.     rear++;//对了尾端指针后移
    
27.     que[rear]=v;//将值存入队列中
    $ r. A) A- `6 [3 h
28.     return 1;
    ! a7 n+ H3 u- k. G! Y, @# J
29.     }
    " P  Y$ n! n1 `) H# K9 v7 z4 z/ W. w
30. }
    8 M% p* o5 _* I% @3 m4 _+ z6 q
31. //队列的取出
    & `: f+ X" p2 M& E
32. int deque()
    
33. {
    
34.     if(front==rear)//队列已空
    
35.         return -1;
    
36.     else
    
37.     {
    
38.         front++;
    ; w  n, b8 A. Q" V
39.         return que[front];
    
40.     }
    + @" E3 x0 I/ I5 L4 ~4 {, J, M7 r
41. }
    3 Z6 X0 ~4 o1 n' W
42. //广度优先搜索法
    # b2 v8 ?! e+ x$ Q1 H1 O$ R8 s
43. void BFS(int v)
    # A. c& ]  Z3 p" X1 z, B! ^
44. {
    & B1 J0 X4 t( j: l" {7 w* t$ `
45.     graph point;
    
46.     enque(v);//存入队列
    & m; ^- W# b1 x
47.     visit[v]=1;//已查找
    
48.     cout<<"["<<v<<"]==>";
    , h$ F1 x* S. ^/ v( F0 @
49.     while(front!=rear)
    8 ]: F* n* S* w8 H* Q5 T5 T
50.     {
    
51.         v=deque();
    
52.         point=head[v].next;
    
53.         while(point!=NULL)//读入邻接列表所有顶点
    # t/ j  k4 O2 d( C
54.         {
    
55.             if(visit[point->vertex]==0)
    
56.             {
    
57.                 enque(point->vertex);//存入队列
    + T, {4 B7 B" C. [- M+ t3 q  j
58.                 visit[point->vertex]=1;//已查找过的顶点
    % T$ s$ R, D/ V; P2 G2 W
59.                 cout<<"["<<point->vertex<<"]==>";
    + W, {& x- l' ?! z; e7 w
60.             }
      d$ a/ O. @$ T3 X9 d
61.             point=point->next;
    / Y  a# G) _. H) Y( {# n0 e
62.         }
    
63.     }
    7 m! ~( U* S" I  Y' l
64. }
    
65. //建立邻接顶点至邻接列表内
    % P1 `9 u1 y( m( A4 F1 ?% Z( ]
66. void create_graph(int v1,int v2)
    
67. {
    + g2 }! X3 r" z1 i, C
68.     graph point,New;
    
69.     New=(graph)malloc(sizeof(struct node));
    
70.     if(New!=NULL)
    : W/ W: g, [2 N& W' b% c8 i4 w  S. C1 l, N
71.     {
    9 g0 `! G, ?5 Z8 K7 O
72.         New->vertex=v2;//邻近顶点
    
73.         New->next=NULL;
    4 W+ w5 P  i) ^4 Q
74.         point=&(head[v1]);
    : _7 X, W9 k" ?( M& n
75.         while(point->next!=NULL)
    " Z7 b) _& n- s4 P1 p; l. j
76.             point=point->next;
    1 n; j3 p; m4 }1 A. ~7 V5 `
77.         point->next=New;//串连在列表尾端
    
78.     }
    ( y# F0 i8 ?. q* W* I
79. }
    
80. //输出邻接列表内数据
    
81. void print_graph(struct node *head)
    
82. {
    4 x% D& O1 ^) A! @8 n  i" l! @
83.     graph point;
    9 f  n) D4 E- L' `  o/ b9 x) K
84.     point=head->next;//设置point为首节点
    
85.     while(point!=NULL)
    
86.     {
    3 t8 z: E6 ]% g  X+ q  v
87.         cout<<"["<<point->vertex<<"] ";
    
88.         point=point->next;
    
89.     }
    6 t/ L) s, ]9 y1 r3 E" t& b
90.     cout<<endl;
    1 z9 s  w# L6 W% L; n9 o
91. }
    
92. //主程序
    
93. void main()
    7 T: ^* I7 {8 n. ~7 X
94. {
    # D3 l' G7 k. j6 z
95.     int node[20][2]={
    ' I8 C% o4 z2 R
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;
     ; n4 I, D4 J7 d. k
103.     }
     
104.     for(i=0;i<verMax;i++)
     0 c( ?* q( ]9 s
105.         visit[i]=0;
     
106. 
     
107.     for(i=0;i<20;i++)
     1 W1 M) z( u2 E% g$ S4 s
108.         create_graph(node[i][0],node[i][1]);
     5 w/ b1 M* Y6 {) A8 J
109. 
     
110.     cout<<"======Graph======"<<endl;
     
111.     for(i=1;i<verMax;i++)
     ; u5 b: d2 V1 {2 ?: C* b
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;
     9 Y8 b) L5 |4 n8 W0 w! O
120. }

复制代码

: ~" \+ @' W$ z& l
/ R) j* u! `! p6 }! Y$ M, U& k