2023.1.29 学习总结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef struct {
int vexs[100];
int edges[100][100];
int v_num, e_num;
}MGraph;
void init(MGraph* mg) {
int n, m;
cin >> n >> m;
mg->v_num = n;
mg->e_num = m;
for (int i = 0; i < n; i++) {
mg->vexs[i] = i;
}
int a, b, c;
for (int i = 0; i < m; i++) {
cin >> a >> b;
mg->edges[a][b] = 1;
mg->edges[b][a] = 1;
}
}
int flag1[100];
void DFS(MGraph* mg, int i) {
cout << i << " ";
flag1[i] = 1;
for (int j = 0; j < mg->v_num; j++) {
if (mg->edges[i][j] == 1 && !flag1[j]) {
DFS(mg, j);
}
}
}
void DFSTraverse(MGraph* mg) {
for (int i = 0; i < mg->v_num; i++) {
if (!flag1[i]) {
DFS(mg, i);
}
}
}
int flag2[100];
void BFS(MGraph* mg, int i) {
queue<int> q;
q.push(i);
flag2[i] = 1;
cout << i << " ";
int temp;
while (!q.empty()) {
temp = q.front();
q.pop();
for (int j = 0; j < mg->v_num; j++) {
if (mg->edges[temp][j] == 1 && !flag2[j]) {
q.push(j);
flag2[j] = 1;
cout << j << " ";
}
}
}
}
void BFSTraverse(MGraph* mg) {
for (int i = 0; i < mg->v_num; i++) {
if (!flag2[i]) {
BFS(mg, i);
}
}
}
/*
8 9
0 1
0 2
2 5
2 6
5 6
1 3
1 4
3 7
4 7
*/
int main()
{
MGraph* mg = (MGraph*)malloc(sizeof(MGraph));
init(mg);
BFSTraverse(mg);
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef struct EdgeNode {
int data;
EdgeNode* next;
};
typedef struct VexNode {
int nodedata;
EdgeNode* first;
};
typedef struct ALGraph {
VexNode list[100];
int v_num, e_num;
};
void init(ALGraph* ag) {
int n, m;
cin >> n >> m;
ag->v_num = n;
ag->e_num = m;
for (int i = 0; i < ag->v_num; i++) {
ag->list[i].first = NULL;
}
int a, b;
for (int i = 0; i < ag->e_num; i++) {
cin >> a >> b;
EdgeNode* node = (EdgeNode*)malloc(sizeof(EdgeNode));
node->data = b;
node->next = ag->list[a].first;
ag->list[a].first = node;
}
}
int flag1[100];
void DFS(ALGraph* ag,int k) {
cout << k << " ";
flag1[k] = 1;
EdgeNode* temp = ag->list[k].first;
while (temp) {
if (!flag1[temp->data]) {
DFS(ag, temp->data);
}
temp = temp->next;
}
}
void DFSTraverse(ALGraph* ag) {
for (int i = 0; i < ag->v_num; i++) {
if (!flag1[i]) {
DFS(ag, i);
}
}
}
int flag2[100];
void BFS(ALGraph* ag, int k) {
queue<int> q;
q.push(k);
flag2[k] = 1;
cout << k << " ";
EdgeNode* temp;
int m;
while (!q.empty()) {
m = q.front();
q.pop();
temp = ag->list[m].first;
while (temp) {
if (!flag2[temp->data]) {
q.push(temp->data);
flag2[temp->data] = 1;
cout << temp->data << " ";
}
temp = temp->next;
}
}
}
void BFSTraverse(ALGraph* ag) {
for (int i = 0; i < ag->v_num; i++) {
if (!flag2[i]) {
BFS(ag, i);
}
}
}
/*
8 9
0 1
0 2
2 5
2 6
5 6
1 3
1 4
3 7
4 7
*/
int main()
{
ALGraph* ag = (ALGraph*)malloc(sizeof(ALGraph));
init(ag);
BFSTraverse(ag);
return 0;
}