technical-recipes.blogspot.com

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: [tabs] [tab title="C++"] [code language="cpp"] #include <iostream> #include <list> #include <memory> class Graph { int _V; bool _directed; std::unique_ptr< std::list<int> > adj; public: Graph(int V, bool directed); ...

Problem description Given a directed or undirected graph, determine whether it is connected or not. Specifically is it possible for any pair of nodes to communicate with each other? This brief post reproduces this web page whereby the problem was to determine whether a graph is strongly connected or not. I use a slight modification of Graph so that the user can define whether the graph consists of directed or undirected edges. When setting the directed parameter to false, the Graph class assumes that the edges are undirected, and so adds an additional link in the opposite direction to maintain bi-connectivity between edges (links).

Problem Outline This I tackled previously when working on the design and implementation of routing optimization algorithms for telecommunications networks. Given that a wide area network with nodes and interconnecting links can be modelled as a graph with vertices and edges, the problem is to find all path combinations