vertex.h
1 #ifndef _VERTEX_H_
2 #define _VERTEX_H_
3 #include <ostream>
4
5 enum BFS_VERTEX_COLOR {
6 WHITE,
7 GRAY,
8 BLACK,
9 };
10
11 struct Vertex {
12 int index;
13 BFS_VERTEX_COLOR color = WHITE;
14 int d = -1;
15 int pre_index = -1;
16
17 bool operator==(const Vertex& v) {
18 return index == v.index;
19 }
20
21 void set(BFS_VERTEX_COLOR color, int d, int pre_index) {
22 this->color = color;
23 this->d = d;
24 this->pre_index = pre_index;
25 }
26 };
27
28 std::ostream & operator<<(std::ostream & os, const Vertex &v);
29
30 #endif
vertex.cpp
1 #include <string>
2 #include "vertex.h"
3
4 using namespace std;
5
6 ostream & operator<<(ostream & os, const Vertex &v) {
7 os << static_cast<char>(v.index) << "(";
8
9 string color_str = "";
10 if (v.color == WHITE) {
11 color_str = "WHITE";
12 } else if (v.color == GRAY) {
13 color_str = "GRAY";
14 } else if (v.color == BLACK) {
15 color_str = "BLACK";
16 }
17 os << color_str << ",";
18
19 if (v.d == -1) {
20 os << "INF";
21 } else {
22 os << v.d;
23 }
24 os << ",";
25
26 if (v.pre_index == -1) {
27 os << "NIL";
28 } else {
29 os << static_cast<char>(v.pre_index);
30 }
31 os << ")";
32 return os;
33 }
edge.h
1 #ifndef _EDGE_H_ 2 #define _EDGE_H_ 3 4 #include <utility> 5 #include <ostream> 6 #include "vertex.h" 7 8 using Edge = std::pair<Vertex, Vertex>; 9 std::ostream & operator<<(std::ostream & os, const Edge &e); 10 11 #endif
edge.cpp
1 #include "edge.h"
2
3 using namespace std;
4
5 ostream & operator<<(ostream & os, const Edge &e) {
6 os << e.first << "-" << e.second << endl;
7 return os;
8 }
graph.h
1 #ifndef _GRAPH_H_ 2 #define _GRAPH_H_ 3 #include <vector> 4 #include <ostream> 5 #include "edge.h" 6 7 using Graph = std::vector<Edge>; 8 9 std::ostream & operator<<(std::ostream & os, const Graph &g); 10 11 #endif
graph.cpp
1 #include "graph.h"
2 #include <iostream>
3
4 using namespace std;
5
6 ostream & operator<<(ostream & os, const Graph &g) {
7 for (const auto& e: g) {
8 os <<e;
9 }
10 return os;
11 }
adj_list.h
1 #ifndef _ADJ_LIST_H_
2 #define _ADJ_LIST_H_
3
4 #include <vector>
5 #include <map>
6 #include <ostream>
7 #include "vertex.h"
8 #include "graph.h"
9
10 using Relation = std::vector<int>;
11
12 struct AdjList {
13 std::vector<Vertex> vertexs;
14 std::map<int, Relation> relations;
15
16 AdjList(const Graph& g);
17 Vertex *get_vertex(int index);
18 Relation *get_relation(int index);
19 };
20
21 std::ostream & operator<<(std::ostream & os, const AdjList &adj_list);
22
23 #endif
adj_list.cpp
1 #include <algorithm>
2 #include "adj_list.h"
3 #include "graph.h"
4
5 using namespace std;
6
7 ostream & operator<<(ostream & os, const Relation &relation) {
8 for (const auto& i: relation) {
9 os << static_cast<char>(i) << "->";
10 }
11 return os;
12 }
13
14 ostream & operator<<(ostream & os, const AdjList &adj_list) {
15 for (const auto& vertex: adj_list.vertexs) {
16 os << vertex << "->";
17 }
18 os << endl;
19 for (auto it = adj_list.relations.begin(); it != adj_list.relations.end(); it++) {
20 os << static_cast<char>(it->first) << "->" << it->second << endl;
21 }
22 return os;
23 }
24
25 static void add_to_vertexs(vector<Vertex> &vertexs, const Vertex& v) {
26 if (find(begin(vertexs), end(vertexs), v) == vertexs.end()) {
27 vertexs.push_back(v);
28 }
29 }
30
31 static void add_to_relation(Relation &relation, int index) {
32 if (find(begin(relation), end(relation), index) == relation.end()) {
33 relation.push_back(index);
34 }
35 }
36
37 static void add_to_relations(std::map<int, Relation> &relations, int index0, int index1) {
38 auto search = relations.find(index0);
39 if (search != relations.end()) {
40 add_to_relation(search->second, index1);
41 } else {
42 relations[index0] = Relation{index1};
43 }
44 }
45
46 AdjList::AdjList(const Graph& g) {
47 for (auto& e: g) {
48 add_to_vertexs(vertexs, e.first);
49 add_to_vertexs(vertexs, e.second);
50 add_to_relations(relations, e.first.index, e.second.index);
51 add_to_relations(relations, e.second.index, e.first.index);
52 }
53 }
54
55 Vertex *AdjList::get_vertex(int index) {
56 for (auto &i: vertexs) {
57 if (i.index == index) {
58 return &i;
59 }
60 }
61 return nullptr;
62 }
63
64 Relation *AdjList::get_relation(int index) {
65 auto search = relations.find(index);
66 if (search != relations.end()) {
67 return &search->second;
68 }
69 return nullptr;
70 }
bfs.cpp
1 #include <iostream>
2 #include <deque>
3 #include "adj_list.h"
4
5 using namespace std;
6
7 void BFS(AdjList &adj_list, int s) {
8 Vertex *p_s = adj_list.get_vertex(s);
9 p_s->set(GRAY, 0, -1);
10
11 deque<int> q;
12 q.push_back(s);
13
14 while (q.size() != 0) {
15 int u = q[0];
16 q.pop_front();
17
18 Vertex *p_u = adj_list.get_vertex(u);
19 Relation *p_u_relation = adj_list.get_relation(u);
20
21 for (auto v: *p_u_relation) {
22 Vertex *p_v = adj_list.get_vertex(v);
23 if (p_v->color == WHITE) {
24 p_v->set(GRAY, p_u->d + 1, p_u->index);
25 q.push_back(v);
26 }
27 }
28 p_u->color = BLACK;
29 }
30 }
31
32 int main() {
33 Graph g {
34 Edge{{'r'}, {'s'}},
35 Edge{{'r'}, {'v'}},
36 Edge{{'s'}, {'w'}},
37 Edge{{'w'}, {'t'}},
38 Edge{{'w'}, {'x'}},
39 Edge{{'t'}, {'x'}},
40 Edge{{'t'}, {'u'}},
41 Edge{{'x'}, {'u'}},
42 Edge{{'x'}, {'y'}},
43 Edge{{'u'}, {'y'}},};
44 cout << "Graph:" << endl;
45 cout << g;
46
47 AdjList adj_list{g};
48 cout << "AdjList:" << endl;
49 cout << adj_list;
50
51 BFS(adj_list, 's');
52 cout << "After BFS:" << endl;
53 cout << adj_list;
54 }