Breadth First Search
From WikiPedia:
“Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’) and explores the neighbor nodes first, before moving to the next level neighbors”
I have borrowed heavily the C++ code listing used at the ‘Geeks for geeks’ website and made a few modifications of my own, such as using smart pointers. I have also produced C# equivalents of the code. For reference the website is here:
http://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/
Full C++/C# code listings:
Consider the following 6-node directed graph, as created using calls to the AddEdge
function shown in the above code:
Running the breadth-first search to traverse the graph gives the following output, showing the graph nodes discovered by the graph traversal:
From Wikipedia:
“Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.”
Again I’ve modified the version of the Depth First Search algorithm from the ‘Geeks for Geeks’ site and done some modifications, including replacing normal pointers with smart pointers, and allowing the graphs to be directed or undirected:
Output of the depth-first search traversal as shown: