Algorithms_in_C++
1.0.0
Set of algorithms implemented in C++.
|
Classes | |
class | Graph |
class | LowestCommonAncestor |
class | RootedTree |
Functions | |
void | add_directed_edge (std::vector< std::vector< int >> *graph, int u, int v) |
Adds a directed edge from vertex u to vertex v. More... | |
void | add_undirected_edge (std::vector< std::vector< int >> *graph, int u, int v) |
Adds an undirected edge from vertex u to vertex v. Essentially adds too directed edges to the adjacency list reprsentation of the graph. More... | |
std::vector< bool > | breadth_first_search (const std::vector< std::vector< int >> &graph, int start) |
Function performs the breadth first search algorithm over the graph. More... | |
void | addEdge (std::vector< std::vector< int >> *adj, int u, int v) |
Function that add edge between two nodes or vertices of graph. More... | |
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. More... | |
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. More... | |
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. More... | |
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. More... | |
void | depth_first_search (const std::vector< std::vector< size_t >> &adj, size_t start) |
initiates depth first search algorithm. More... | |
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. More... | |
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. More... | |
void graph::add_directed_edge | ( | std::vector< std::vector< int >> * | graph, |
int | u, | ||
int | v | ||
) |
void graph::add_undirected_edge | ( | std::vector< std::vector< int >> * | graph, |
int | u, | ||
int | v | ||
) |
Adds an undirected edge from vertex u to vertex v. Essentially adds too directed edges to the adjacency list reprsentation of the graph.
graph | Adjacency list representation of graph |
u | first vertex |
v | second vertex |
void graph::addEdge | ( | std::vector< std::vector< int >> * | adj, |
int | u, | ||
int | v | ||
) |
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 |
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 |
std::vector<bool> graph::breadth_first_search | ( | const std::vector< std::vector< int >> & | graph, |
int | start | ||
) |
Function performs the breadth first search algorithm over the graph.
graph | Adjacency list representation of graph |
start | vertex from where traversing starts |
vector to keep track of visited vertices
a queue that stores vertices that need to be further explored
mark the starting vertex as visited
if the vertex is not visited then mark it as visited and push it to the queue
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. |
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
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. |
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 |
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. |