Understanding graph traversals
To make use of graphs, information needs to be mined from them. Graph traversal is defined as the strategy used to make sure that every vertex and edge is visited in an orderly manner. An effort is made to make sure that each vertex and edge is visited exactly once; no more and no less. Broadly, there can be two different ways of traveling a graph to search the data in it. Going by breadth is called breadth-first search (BFS) and going by depth is called depth-first search (DFS). Let's look at them one by one.
Breadth-first search
BFS works best when there is a concept of layers or levels of neighborhoods in the aGraph we are dealing with. For example, when the connections of a person in LinkedIn are expressed as a graph, there are first-level connections and then there are second-level connections, which directly translate to the layers.The BFS algorithm starts from a root vertex and explores the vertices in the...
