BFS_DFS_Adjacency Matrix

pwnmelife

1. // BFS_DFS.cpp : This file contains the 'main' function. Program execution begins and ends there.
   
2. //
   
3. 
   
4. 
   
5. #include <iostream>
   
6. #include <stdio.h>
   
7. #include <stdlib.h>
   
8. 
   
9. #define MaxVertexNum 100
   
10. typedef char VertexType;
    
11. typedef int ElemType;
    
12. typedef int EdgeType;
    
13. typedef struct QNode{
    
14.         ElemType data;
    
15.         struct QNode* next;
    
16. }QNode, *QNodePtr;
    
17. typedef struct {
    
18.         QNode *front, *rear;
    
19. }Queue, *QueuePtr;
    
20. 
    
21. typedef struct {
    
22.         VertexType Vex[MaxVertexNum];
    
23.         EdgeType Edge[MaxVertexNum][MaxVertexNum];
    
24.         int vexnum, arnum;
    
25. }MGraph;
    
26. 
    
27. bool visited[MaxVertexNum] = {false};
    
28. int number;
    
29. 
    
30. 
    
31. void InitQueue(QueuePtr *q); //初始化
    
32. void InsertQueue(QueuePtr *q, ElemType c); //入队
    
33. void DeleteQueue(QueuePtr *q, ElemType *c);//出队
    
34. bool IsEmpty(QueuePtr *q); //判空
    
35. 
    
36. void InitGraph(MGraph* m, int number);
    
37. void DFS(MGraph* m, int start);
    
38. void BFS(MGraph* m);
    
39. void visit(int);
    
40. 
    
41. int main()
    
42. {
    
43.         int start;
    
44.         MGraph m;
    
45.         printf("Please the vertex number: ");
    
46.         scanf("%d", &number);
    
47.         InitGraph(&m, number);
    
48.         printf("Please input a starting vertex:");
    
49.         scanf("%d", &start);
    
50.         //DFS(&m, start);
    
51.         BFS(&m);
    
52.         printf("\n");
    
53.         return 0;
    
54. }
    
55. 
    
56. void InitGraph(MGraph *m, int number) {
    
57.         printf("please input the whole graph, 1(yes), 0(no)\n");
    
58.         int isExist;
    
59.         for (int i = 0; i < number; i++) {
    
60.                 for (int j = 0; j < number; j++) {
    
61.                         scanf("%d", &isExist);
    
62.                         m->Edge[i][j] = isExist;
    
63.                 }
    
64.         }
    
65. }
    
66. 
    
67. void DFS(MGraph *m, int start) {
    
68.         visit(start);
    
69.         visited[start] = true;
    
70.         for (int i = 0; i < number; i++) {
    
71.                 if (!visited[i] && m->Edge[start][i]) {
    
72.                         DFS(m, i);
    
73.                 }
    
74.         }
    
75. }
    
76. void BFS(MGraph* m) {
    
77.         int vertex;
    
78.         QueuePtr *q = (QueuePtr *)malloc(sizeof(QueuePtr));
    
79.         InitQueue(q);
    
80.         for (int i = 0; i < number; i++) {
    
81.                 if (!visited[i]) {
    
82.                         visit(i);
    
83.                         visited[i] = true;
    
84.                         InsertQueue(q, i);
    
85.                         while (!IsEmpty(q)) {
    
86.                                 DeleteQueue(q, &vertex);
    
87.                                 for (int j = 0; j < number;j++) {
    
88.                                         if (!visited[j] && m->Edge[vertex][j]) {
    
89.                                                 visit(j);
    
90.                                                 visited[j] = true;
    
91.                                                 InsertQueue(q, j);
    
92.                                         }
    
93.                                 }
    
94.                         }
    
95.                 }
    
96.         }
    
97. }
    
98. void visit(int vertex) {
    
99.         printf("%d ", vertex);
    
100. }
     
101. void InitQueue(QueuePtr *q) {
     
102.         (*q) = (QueuePtr)malloc(sizeof(Queue));
     
103.         (*q)->front = (*q)->rear = (QNodePtr)malloc(sizeof(QNode)); //头结点
     
104.         (*q)->front->next = NULL;
     
105. }
     
106. void InsertQueue(QueuePtr *q, ElemType c) {
     
107.         QNodePtr qNode = (QNodePtr)malloc(sizeof(QNode));
     
108.         qNode->data = c;
     
109.         qNode->next = NULL;
     
110.         (*q)->rear->next = qNode;
     
111.         (*q)->rear = qNode;
     
112. }
     
113. void DeleteQueue(QueuePtr *q, ElemType *c) {
     
114.         if ((*q)->front == (*q)->rear) {
     
115.                 printf("The Queue is empty\n");
     
116.                 return;
     
117.         }
     
118.         QNodePtr headNode = (*q)->front;
     
119.         QNodePtr firstNode = headNode->next;
     
120.         *c = firstNode->data;
     
121.         headNode->next = firstNode->next;
     
122.         if ((*q)->rear == firstNode) {
     
123.             (*q)->rear = (*q)->front;
     
124.         }
     
125.         free(firstNode);
     
126. }
     
127. bool IsEmpty(QueuePtr *q) {
     
128.         if ((*q)->front == (*q)->rear) {
     
129.                 return true;
     
130.         } else {
     
131.                 return false;
     
132.         }
     
133. }

复制代码