TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
depth_first_search_with_stack.cpp
Go to the documentation of this file.
1
31
32#include <iostream>
33#include <stack>
34#include <vector>
35#include <cassert>
36#include <limits>
37
38constexpr int WHITE = 0;
39constexpr int GREY = 1;
40constexpr int BLACK = 2;
41constexpr int64_t INF = std::numeric_limits<int16_t>::max();
42
43
48namespace graph {
53namespace depth_first_search {
64void addEdge(std::vector<std::vector<size_t>> *adj, size_t u, size_t v) {
65 /*
66 *
67 * Here we are considering undirected graph that's the
68 * reason we are adding v to the adjacency list representation of u
69 * and also adding u to the adjacency list representation of v
70 *
71 */
72 (*adj)[u - 1].push_back(v - 1);
73}
74
87std::vector<size_t> dfs(const std::vector<std::vector<size_t> > &graph, size_t start) {
89 std::vector<size_t> checked(graph.size(), WHITE), traversed_path;
90
91 checked[start] = GREY;
92 std::stack<size_t> stack;
93 stack.push(start);
94
96 while (!stack.empty()) {
97 int act = stack.top();
98 stack.pop();
99
100 if (checked[act] == GREY) {
102 traversed_path.push_back(act + 1);
103
105 for (auto it : graph[act]) {
106 stack.push(it);
107 if (checked[it] != BLACK) {
108 checked[it] = GREY;
109 }
110 }
111 checked[act] = BLACK;
112 }
113 }
114 return traversed_path;
115}
116} // namespace depth_first_search
117} // namespace graph
118
123static void tests() {
124 size_t start_pos;
125
127 std::cout << "Case 1: " << std::endl;
128 start_pos = 1;
129 std::vector<std::vector<size_t> > g1(3, std::vector<size_t>());
130
134
135 std::vector<size_t> expected1 {1, 2, 3};
136 assert(graph::depth_first_search::dfs(g1, start_pos - 1) == expected1);
137 std::cout << "Passed" << std::endl;
138
140 std::cout << "Case 2: " << std::endl;
141 start_pos = 1;
142 std::vector<std::vector<size_t> > g2(4, std::vector<size_t>());
143
148
149 std::vector<size_t> expected2 {1, 3, 2, 4};
150 assert(graph::depth_first_search::dfs(g2, start_pos - 1) == expected2);
151 std::cout << "Passed" << std::endl;
152
154 std::cout << "Case 3: " << std::endl;
155 start_pos = 2;
156 std::vector<std::vector<size_t> > g3(4, std::vector<size_t>());
157
162
163 std::vector<size_t> expected3 {2, 4, 1, 3};
164 assert(graph::depth_first_search::dfs(g3, start_pos - 1) == expected3);
165 std::cout << "Passed" << std::endl;
166
167}
168
173int main() {
174 tests(); // execute the tests
175
176 size_t vertices = 0, edges = 0, start_pos = 1;
177 std::vector<size_t> traversal;
178
179 std::cout << "Enter the Vertices : ";
180 std::cin >> vertices;
181 std::cout << "Enter the Edges : ";
182 std::cin >> edges;
183
185 std::vector<std::vector<size_t> > adj(vertices, std::vector<size_t>());
186
188 std::cout << "Enter the vertices which have edges between them : " << std::endl;
189 while (edges--) {
190 size_t u = 0, v = 0;
191 std::cin >> u >> v;
193 }
194
196 std::cout << "Enter the starting vertex [1,n]: " << std::endl;
197 std::cin >> start_pos;
198 start_pos -= 1;
199 traversal = graph::depth_first_search::dfs(adj, start_pos);
200
202 for (auto x : traversal) {
203 std::cout << x << ' ';
204 }
205
206 return 0;
207}
constexpr int64_t INF
for assert
for std::invalid_argument
Definition stack.hpp:19
void pop()
Definition stack.hpp:62
void push(const value_type &item)
Definition stack.hpp:47
value_type top() const
Definition stack.hpp:56
constexpr int GREY
indicates the node hasn't been explored
static void tests()
std::vector< size_t > dfs(const std::vector< std::vector< size_t > > &graph, size_t start)
Explores the given vertex, exploring a vertex means traversing over all the vertices which are connec...
constexpr int BLACK
indicates node is in stack waiting to be explored
void addEdge(std::vector< std::vector< size_t > > *adj, size_t u, size_t v)
Adds and edge between two vertices of graph say u and v in this case.
int main()
Main function.
constexpr int WHITE
Functions for Depth First Search algorithm.
Graph Algorithms.