# Basic Graph Algorithms

## bfs

``````std::vector<int> BreadthFirstSearch(Graph &graph, int start_vertex) {
if (start_vertex > graph.GetVertexesCount() or start_vertex <= 0)
return {};

std::vector<int> enter_order;
std::vector<short> visited(graph.GetVertexesCount());
std::queue<int> q;

// Функция принимает вершину, нумерация которой начинается с 1
// Для удобства уменьшаем ее значение на 1, чтобы нумерация начиналась с 0
--start_vertex;
visited[start_vertex] = true;
q.push(start_vertex);
enter_order.emplace_back(start_vertex + 1);

while (!q.empty()) {
auto from = q.front();
q.pop();

for (int to = 0, size = graph.GetVertexesCount(); to != size; ++to) {
if (!visited[to] and graph(from, to) != 0) {
visited[to] = true;
q.push(to);
enter_order.emplace_back(to + 1);
}
}
}

return enter_order;
}``````

## DFS

``````std::vector<int> DepthFirstSearch(Graph &graph, int start_vertex) {
if (start_vertex > graph.GetVertexesCount() or start_vertex <= 0)
return {};

std::vector<int> enter_order;
std::vector<short> visited(graph.GetVertexesCount());
std::stack<int> s;

--start_vertex;
visited[start_vertex] = true;
s.push(start_vertex);
enter_order.emplace_back(start_vertex + 1);

while (!s.empty()) {
auto from = c.top();
bool is_found = false;

for (int to = 0, size = graph.GetVertexesCount(); to != size; ++to) {
if (!visited[to] and graph(from, to) != 0) {
is_found = true;
visited[to] = true;
s.push(to);
enter_order.emplace_back(to + 1);
from = to;
}
}

if (!is_found)
s.pop();
}

return enter_order;
}``````

Note that the code is practically the same, so they can be combined into one function, and just pass the container type there

``````//
// If Container type = std::stack<int> it will be DepthFirstSearch
// If Container type = std::queue<int> it will be BreadthFirstSearch
//
template <typename Container = std::stack<int>>
std::vector<int> FirstSearch(Graph &graph, int start_vertex)
{
if (start_vertex > graph.GetVertexesCount() or start_vertex <= 0)
return {};

constexpr bool is_stack = std::is_same_v<Container, std::stack<int>>;

std::vector<int> enter_order;
std::vector<short> visited(graph.GetVertexesCount());
Container c;

--start_vertex;
visited[start_vertex] = true;
c.push(start_vertex);
enter_order.emplace_back(start_vertex + 1);

while (!c.empty()) {
int from = -1;
if constexpr (is_stack) from = c.top();
else {
from = c.front();
c.pop()
}

bool is_found = false;

for (int to = 0, size = graph.GetVertexesCount(); to != size; ++to) {
if (!visited[to] and graph(from, to) != 0) {
is_found = true;
visited[to] = true;
c.push(to);
enter_order.emplace_back(to + 1);
if (is_stack)
from = to;
}
}

if (is_stack and !is_found)
c.pop();
}

return enter_order;
}``````

• Then the BFS & DFS code will look like this:
``````std::vector<int> BreadthFirstSearch(Graph &graph, int start_vertex) {
return FirstSearch<std::queue<int>>(graph, start_vertex);
}

std::vector<int> DepthFirstSearch(Graph &graph, int start_vertex) {
return FirstSearch<std::stack<int>>(graph, start_vertex);
}``````