Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
Public Member Functions | |
void | add_edge (T u, T v, bool bidir=true) |
std::map< T, bool > | breadth_first_search (T src) |
Graph (size_t N, const std::vector< std::pair< int, int > > &undirected_edges) | |
Populate the adjacency list for each vertex in the graph. Assumes that evey edge is a pair of valid vertex indices. | |
int | number_of_vertices () const |
Public Attributes | |
std::vector< std::vector< int > > | neighbors |
for each vertex it stores a list indicies of its neighbors | |
Private Attributes | |
std::map< T, std::list< T > > | adjacency_list |
Class for representing a graph as an adjacency list. Its vertices are indexed 0, 1, ..., N - 1.
|
inline |
Populate the adjacency list for each vertex in the graph. Assumes that evey edge is a pair of valid vertex indices.
N | number of vertices in the graph |
undirected_edges | list of graph's undirected edges |
|
inline |
add_edge(u,v,bidir) is used to add an edge between node u and node v by default , bidir is made true , i.e graph is bidirectional . It means if edge(u,v) is added then u-->v and v-->u both edges exist.
to make the graph unidirectional pass the third parameter of add_edge as false which will
|
inline |
this function performs the breadth first search on graph and return a mapping which maps the nodes to a boolean value representing whether the node was traversed or not.
mapping to keep track of all visited nodes
initialise every possible vertex to map to false initially none of the vertices are unvisited
queue to store the nodes which are yet to be traversed
push the source vertex to queue to begin traversing
mark the source vertex as visited
traverse the graph till no connected vertex are left extract a node from queue for further traversal
remove the node from the queue
check every vertex connected to the node which are still unvisited
if the neighbour is unvisited , push it into the queue
mark the neighbour as visited
|
inline |
Function to get the number of vertices in the graph
|
private |
adjacency_list maps every vertex to the list of its neighbours in the order in which they are added.