Repository navigation
Expand file tree
/
Copy pathbfs_graph_traversal.cpp
More file actions
143 lines (112 loc) · 2.83 KB
/
Copy pathbfs_graph_traversal.cpp
File metadata and controls
143 lines (112 loc) · 2.83 KB
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <bits/stdc++.h>
#include <unordered_map>
#include <string>
using namespace std;
string ltrim(const string &);
string rtrim(const string &);
// DO NOT EDIT
// Vertex class
class Vertex {
public:
char id;
vector<Vertex*> edges;
Vertex(char id) {
this->id = id;
}
};
/*
* Complete the 'bfs' function below.
*
* The function is expected to return a STRING.
* The function accepts following parameters:
* 1. Vertex origin
*/
/*
* For your reference:
*
* Vertex {
* char id;
* vector<Vertex*> edges;
* }
*
*/
string bfs(Vertex *origin) {
if (origin == nullptr)
{
return "";
}
std::shared_ptr<std::queue<Vertex*>> myQueue = make_shared<std::queue<Vertex*>>();
std::shared_ptr<std::unordered_set<Vertex *>> visited =
make_shared<std::unordered_set<Vertex *>>();
myQueue->push(origin);
visited->insert(origin);
std::string s ="";
while(!myQueue->empty())
{
Vertex *current = myQueue->front();
myQueue->pop();
for(Vertex* edge : current->edges)
{
if(visited->find(edge) == visited->end())
{
myQueue->push(edge);
visited->insert(edge);
}
}
s += current->id;
}
return s;
}
// DO NOT EDIT// generate graph from int and array of arrays
Vertex *deserialize(string vertices, vector<string> &edges){
unordered_map<char, Vertex*> container;
for (int i = 0; i < vertices.length(); i++) {
container[vertices[i]] = new Vertex(vertices[i]);
}
char v1;
char v2;
for (int i = 0; i < edges.size(); i++) {
string edge = edges[i];
v1 = edge[0];
v2 = edge[1];
container[v1]->edges.push_back(container[v2]);
container[v2]->edges.push_back(container[v1]);
}
return container[vertices[0]];
}
int main()
{
ofstream fout(getenv("OUTPUT_PATH"));
string vertices;
getline(cin, vertices);
string edges_count_temp;
getline(cin, edges_count_temp);
int edges_count = stoi(ltrim(rtrim(edges_count_temp)));
vector<string> edges(edges_count);
for (int i = 0; i < edges_count; i++) {
string edges_item;
getline(cin, edges_item);
edges[i] = edges_item;
}
Vertex *origin = deserialize(vertices, edges);
string result = bfs(origin);
fout << result << "\n";
fout.close();
return 0;
}
string ltrim(const string &str) {
string s(str);
s.erase(
s.begin(),
find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
);
return s;
}
string rtrim(const string &str) {
string s(str);
s.erase(
find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
s.end()
);
return s;
}