一些基础算法

俞晨曦

1. #include <STDIO.H>
   
2. int visited[5] = {0};
   
3. 
   
4. int graph[5][5] =
   
5. {
   
6.         0,1,1,0,0,
   
7.         1,0,0,1,1,
   
8.         0,0,0,0,1,
   
9.         0,1,0,0,1,
   
10.         0,1,1,1,0
    
11. };
    
12. 
    
13. void DFS(int x)
    
14. {
    
15.         printf("%d\n",x);
    
16.         visited[x] = 1;
    
17.         int y;
    
18.        
    
19.         for(y = 0;y < 5;++y)
    
20.                 if(graph[x][y] && !visited[y])
    
21.                         DFS(y);
    
22. }
    
23. 
    
24. #define MAX_SIZE 0x40
    
25. 
    
26. typedef struct
    
27. {
    
28.         int queue[MAX_SIZE];
    
29.         int front,rear;
    
30. }Queue,*PQueue;
    
31. 
    
32. void InitQueue(PQueue PQ)
    
33. {
    
34.         PQ->rear = PQ->front = 0;
    
35. }
    
36. 
    
37. void InQueue(PQueue PQ,int data)
    
38. {
    
39.         PQ->queue[PQ->rear] = data;
    
40.         PQ->rear = (PQ->rear + 1)%MAX_SIZE;
    
41. }
    
42. 
    
43. int OutQueue(PQueue PQ)
    
44. {
    
45.         int data = PQ->queue[PQ->front];
    
46.         PQ->front = (PQ->front + 1)%MAX_SIZE;
    
47.         return data;
    
48. }
    
49. 
    
50. int IsQueueEmpty(PQueue PQ)
    
51. {
    
52.         if(PQ->rear == PQ->front)
    
53.                 return 1;
    
54.         return 0;
    
55. }
    
56. 
    
57. void BFS(int x)
    
58. {
    
59.         Queue q;
    
60.         int i;
    
61.        
    
62.         InitQueue(&q);
    
63.        
    
64.         InQueue(&q,x);
    
65.         visited[x] = 1;               
    
66. 
    
67.         while(!IsQueueEmpty(&q))
    
68.         {
    
69.                 x = OutQueue(&q);
    
70.                 printf("%d\n",x);
    
71.        
    
72.                 for (i = 0;i < 5;++i)
    
73.                 {
    
74.                         if(!visited[i] && graph[x][i])
    
75.                         {
    
76.                                 InQueue(&q,i);
    
77.                                 visited[i] = 1;        //标记访问
    
78.                         }
    
79.                 }
    
80.                
    
81.         }
    
82. }
    
83. 
    
84. int main()
    
85. {
    
86.         return 0;
    
87. }
    

复制代码

知表不言