TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
|
Classes | |
class | Graph |
class | HKGraph |
Represents Bipartite graph for Hopcroft Karp implementation. More... | |
class | LowestCommonAncestor |
class | RootedTree |
Functions | |
void | addEdge (std::vector< std::vector< int > > *adj, int u, int v) |
Function that add edge between two nodes or vertices of graph. | |
void | explore (const std::vector< std::vector< int > > *adj, int u, std::vector< bool > *visited) |
Utility function for depth first seach algorithm this function explores the vertex which is passed into. | |
int | getConnectedComponents (const std::vector< std::vector< int > > *adj) |
Function that perfoms depth first search algorithm on graph and calculated the number of connected components. | |
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. | |
void | explore (const std::vector< std::vector< size_t > > &adj, size_t v, std::vector< bool > *visited) |
Explores the given vertex, exploring a vertex means traversing over all the vertices which are connected to the vertex that is currently being explored. | |
void | depth_first_search (const std::vector< std::vector< size_t > > &adj, size_t start) |
initiates depth first search algorithm. | |
void | addEdge (std::vector< std::vector< std::pair< int, int > > > *adj, int u, int v, int w) |
Function that add edge between two nodes or vertices of graph. | |
int | dijkstra (std::vector< std::vector< std::pair< int, int > > > *adj, int s, int t) |
Function runs the dijkstra algorithm for some source vertex and target vertex in the graph and returns the shortest distance of target from the source. | |
bool | checkBipartite (const std::vector< std::vector< int64_t > > &graph, int64_t index, std::vector< int64_t > *visited) |
function to check whether the passed graph is bipartite or not | |
bool | isBipartite (const std::vector< std::vector< int64_t > > &graph) |
returns true if the given graph is bipartite else returns false | |
int | TravellingSalesmanProblem (std::vector< std::vector< uint32_t > > *cities, int32_t src, uint32_t V) |
Function calculates the minimum path distance that will cover all the cities starting from the source. | |
Graph Algorithms.
for assert
Check whether a given graph is bipartite or not.
for std::vector
Graph algorithms.
for IO operations for std::set
Graph Algorithms
A bipartite graph is the one whose nodes can be divided into two disjoint sets in such a way that the nodes in a set are not connected to each other at all, i.e. no intra-set connections. The only connections that exist are that of inter-set, i.e. the nodes from one set are connected to a subset of nodes in the other set. In this implementation, using a graph in the form of adjacency list, check whether the given graph is a bipartite or not.
References used: GeeksForGeeks
Graphical algorithms
for std::min for IO operations for limits of integral types for std::vector
Graph Algorithms
void graph::addEdge | ( | std::vector< std::vector< int > > * | adj, |
int | u, | ||
int | v ) |
Function that add edge between two nodes or vertices of graph.
adj | adjacency list of graph. |
u | any node or vertex of graph. |
v | any node or vertex of graph. |
Definition at line 46 of file connected_components.cpp.
void graph::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.
adj | Adjacency list representation of graph |
u | first vertex |
v | second vertex |
Definition at line 56 of file depth_first_search.cpp.
void graph::addEdge | ( | std::vector< std::vector< std::pair< int, int > > > * | adj, |
int | u, | ||
int | v, | ||
int | w ) |
Function that add edge between two nodes or vertices of graph.
u | any node or vertex of graph |
v | any node or vertex of graph |
Definition at line 48 of file dijkstra.cpp.
bool graph::checkBipartite | ( | const std::vector< std::vector< int64_t > > & | graph, |
int64_t | index, | ||
std::vector< int64_t > * | visited ) |
function to check whether the passed graph is bipartite or not
graph | is a 2D matrix whose rows or the first index signify the node and values in that row signify the nodes it is connected to |
index | is the valus of the node currently under observation |
visited | is the vector which stores whether a given node has been traversed or not yet |
< stores the neighbouring node indexes in squence of being reached
insert the current node into the queue
mark the current node as travelled
< stores the neighbour of the current node
check whether the neighbour node is travelled already or not
colour the neighbouring node with different colour than the current node
insert the neighbouring node into the queue
if both the current node and its neighbour has the same state then it is not a bipartite graph
return true when all the connected nodes of the current nodes are travelled and satisify all the above conditions
Definition at line 37 of file is_graph_bipartite2.cpp.
void graph::depth_first_search | ( | const std::vector< std::vector< size_t > > & | adj, |
size_t | start ) |
initiates depth first search algorithm.
adj | adjacency list of graph |
start | vertex from where DFS starts traversing. |
Definition at line 99 of file depth_first_search.cpp.
int graph::dijkstra | ( | std::vector< std::vector< std::pair< int, int > > > * | adj, |
int | s, | ||
int | t ) |
Function runs the dijkstra algorithm for some source vertex and target vertex in the graph and returns the shortest distance of target from the source.
adj | input graph |
s | source vertex |
t | target vertex |
n denotes the number of vertices in graph
setting all the distances initially to INF
creating a min heap using priority queue first element of pair contains the distance second element of pair contains the vertex
pushing the source vertex 's' with 0 distance in min heap
marking the distance of source as 0
second element of pair denotes the node / vertex
first element of pair denotes the distance
for all the reachable vertex from the currently exploring vertex we will try to minimize the distance
minimizing distances
Definition at line 66 of file dijkstra.cpp.
void graph::explore | ( | const std::vector< std::vector< int > > * | adj, |
int | u, | ||
std::vector< bool > * | visited ) |
Utility function for depth first seach algorithm this function explores the vertex which is passed into.
adj | adjacency list of graph. |
u | vertex or node to be explored. |
visited | already visited vertices. |
Definition at line 59 of file connected_components.cpp.
void graph::explore | ( | const std::vector< std::vector< size_t > > & | adj, |
size_t | v, | ||
std::vector< bool > * | visited ) |
Explores the given vertex, exploring a vertex means traversing over all the vertices which are connected to the vertex that is currently being explored.
adj | garph |
v | vertex to be explored |
visited | already visited vertices |
Definition at line 80 of file depth_first_search.cpp.
int graph::getConnectedComponents | ( | const std::vector< std::vector< int > > * | adj | ) |
Function that perfoms depth first search algorithm on graph and calculated the number of connected components.
adj | adjacency list of graph. |
Definition at line 77 of file connected_components.cpp.
bool graph::isBipartite | ( | const std::vector< std::vector< int64_t > > & | graph | ) |
returns true if the given graph is bipartite else returns false
graph | is a 2D matrix whose rows or the first index signify the node and values in that row signify the nodes it is connected to |
< stores boolean values which signify whether that node had been visited or not
if the current node is not visited then check whether the sub-graph of that node is a bipartite or not
Definition at line 76 of file is_graph_bipartite2.cpp.
int graph::TravellingSalesmanProblem | ( | std::vector< std::vector< uint32_t > > * | cities, |
int32_t | src, | ||
uint32_t | V ) |
Function calculates the minimum path distance that will cover all the cities starting from the source.
cities | matrix representation of cities |
src | Point from where salesman is starting |
V | number of vertices in the graph |
Definition at line 41 of file travelling_salesman_problem.cpp.