# Category: Graph Algorithms

## Getting started with the Boost Graph Library

Introduction Some simple walk-throughs on how to use the Boost Graph Library. I find much of the documentation, both online and printed, to be a bit impenetrable. I am sure …

## Graph Traversals in C++ and C#

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 …

## Determining if paths are Hamiltonian in C++

A Hamiltonian path in a graph is a path whereby each node is visited exactly once. A number of graph-related problems require determining if the interconnections between its edges and …

## Using depth first search to test graph connectivity in C++

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 …

## Kruskal’s Algorithm in C++

A simple C++ implementation of Kruskal’s algorithm for finding minimal spanning trees in networks. Though I have a previous posting that accomplishes exactly the same thing, I thought that a …

## Modeling networks as graphs in C++

After playing around with some graph algorithm code as implemented by Sedgewick and others, I have come to the conclusion that while these are efficient and concise, improvements could be …

## The K-Shortest Paths Algorithm in C++

Introduction Following on from a previous post which was concerned with finding all possible combinations of paths between communicating end nodes, this algorithm finds the top k number of paths: …

## Implementing Dijkstra’s Algorithm using Sedgewick’s C++ Code

Introduction Dijkstra’s algorithm solves the shortest path problem for a graph with nonnegative edge weights, producing a shortest path tree. This algorithm is often used in routing and as a …

## A Recursive Algorithm to Find all Paths Between Two Given Nodes in C++ and C#

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 …

## Implementing Kruskal’s Algorithm in C#

This post is essentially a blatant lifting of Omar Gamil’s CodeProject article on the same subject. I have been using the project as means of getting into C# programming and …