Breadth-First Search (BFS)
The following sequence of graph states represents a trace of the BFS algorithm starting from source
vertex s. The trace should be read from left to right, then from top to bottom. The numeric value
associated with each vertex represents its distance field, i.e., the distance between s and the vertex.
Each trace step includes the state of queue Q. The left side of the queue represents its head, and the
right side represents its tail. As vertexes are discovered, the traversed edges are represented as thick
gray lines. These edges form. the breadth-first tree at the end of the trace.
Depth-First Search (DFS)
The following sequence of states represents a trace of the DFS algorithm using source vertex s. The
values in the circles represent the timestamps associated with each vertex, shown as “time_in /
time_out”. When a vertex is discovered, it is colored gray, and its time_in field is populated. When it is
left permanently, it is colored black, and its time_out field is set.
As new vertexes are discovered, the traversed edges are made part of the final depth-first tree, and are
represented as thick gray lines in the trace. The final group of tick gray lines represents the complete set
of tree edges. The remaining edges are labeled F, B, and C, based on whether they are forward, back, or
cross edges, respectively.
Bellman-Ford
The Bellman-Ford algorithm calculates single-source shortest paths on a directed, weighted graph
where edges can have negative weights. Input graphs with negative cycles are not allowed.
The following trace shows the application of this algorithm using vertex s as the source. The values in
the circles represent the distance field of each vertex, that is, the minimum distance between s and each
vertex calculated so far. The thick gray lines represent the shortest paths calculated so far, as the parent
fields of each vertex are progressively updated.
The states below correspond to: (a) The situation just before the first pass over the edges. (b)–(d) The
situation after each successive pass over the edges. (e) Final state, where the distance and parent fields
in all vertexes are final values. The algorithm returns true in this example.
Dijkstra
Dijkstra's algorithm calculates single-source shortest paths in a directed, weighted graph with non-
negative weights.
The following trace shows the execution of this algorithm, taking vertex s as the source. The values in
the circles represent the distance field of each vertex, while thick gray lines represent the predecessor-
successor relationship in shortest paths, as captured by the parent field of each vertex.
The states below correspond to: (a) The situation just before the first iteration of the outer while loop.
The shaded vertex has the minimum distance value and is chosen as vertex u within the loop. (b)–(f)
The situation after each successive iteration of the outer while loop. The shaded vertex in each part is
chosen as vertex u in the next iteration. Black circles represent those vertexes that have been already
extracted from the tree. (f) Situation after the while loop, with final states for all distance and parent
fields.
Implementation
File Graph.h
#ifndef GRAPH_H
#define GRAPH_H
#include
class Graph
{
struct Edge
{
int v;
int weight;
Edge *next;
};
enum Color
{
White,
Gray,
Black
};
struct Vertex
{
// Used in BFS and DFS
Color color;
// Used in all algorithms, either to record a sub-graph forming
// a tree (breadth-first or depth-first tree) or to record
// shortest paths.
int parent;
// Used in BFS
int distance;
// Used in DFS
int time_in;
int time_out;
// Used in Dijkstra(). This are references to the positions in a
// multimap (binary search tree) where a vertex has been stored.
std::multimap::iterator it;
// Adjacency list
Edge *edges;
};
// Number of vertices
int size;
// Array of vertices
Vertex *V;
// Auxiliary function for DFS
int DFSVisit(int u, int time);
// Auxiliary function for shortest paths
void Relax(int u, Edge *edge);
public:
// Constructor
Graph(int size);
// Destructor
~Graph();
// Return the number of vertices
int getSize() { return size; }
// Add a new edge connecting vertex 'u' with 'v'.
void AddEdge(int u, int v, int weight = 1);
// Adds a new undirected (or bidirectional) edge. This consists in
// adding one edge u->v and another edge v->u. This function is defined
// inline.
void AddUndirectedEdge(int u, int v, int weight = 1);
// Print the graph
void Print();
// Run breadth-first search, starting at the given source vertex.
void BFS(int s);
// Print the sequence of vertices to traverse for one shortest path
// connecting u and v. This function relies on a previous call to
// BFS(u) or any version of the shortest-path algorithms.
void PrintShortestPath(int u, int v);
// Run depth-first search, starting at the given source vertex.
void DFS(int s);
// Bellman-Ford algorithm to calculate single-source shortest paths on a
// weighted, directed graph with possibly negative weights, but no
// negative-weighted cycles. The function returns false only in the
// presence of negative cycles.
bool BellmanFord(int s);
// Dijkstra algorithm to calculate single-source shortest paths on a
// weighted, directed graph with non-negative weights.
void Dijkstra(int s);
};
#endif
File Graph.cc
#include
#include
#include
#include "Graph.h"
Graph::Graph(int size)
{
this->size = size;
V = new Vertex[size]();
for (int i = 0; i next;
delete edge;
}
}
delete[] V;
}
void Graph::AddEdge(int u, int v, int weight)
{
Edge *edge = new Edge();
edge->v = v;
edge->weight = weight;
edge->next = V[u].edges;
V[u].edges = edge;
}
void Graph::AddUndirectedEdge(int u, int v, int weight)
{
AddEdge(u, v, weight);
AddEdge(v, u, weight);
}
void Graph::Print()
{
std::cout = 0)
std::cout = 0)
std::cout = 0)
std::cout next)
std::cout " v;
std::cout Q;
Q.push(s);
// Process queue
while (Q.size())
{
// Extract vertex from queue
int u = Q.front();
Q.pop();
// Traverse adjacency list
for (Edge *edge = V[u].edges; edge; edge = edge->next)
{
int v = edge->v;
if (V[v].color == White)
{
V[v].color = Gray;
V[v].parent = u;
V[v].distance = V[u].distance + 1;
Q.push(v);
}
}
// Finish processing vertex
V[u].color = Black;
}
}
void Graph::PrintShortestPath(int u, int v)
{
if (u == v)
{
std::cout " next)
{
int v = edge->v;
if (V[v].color == White)
{
V[v].parent = u;
time = DFSVisit(v, time);
}
}
// Color black
V[u].color = Black;
V[u].time_out = time++; // Post-increment
return time;
}
void Graph::DFS(int s)
{
// Initialize all verteces
for (int i = 0; i v;
if (V[u].distance + edge->weight weight;
}
}
bool Graph::BellmanFord(int s)
{
// Initialize
for (int i = 0; i next)
Relax(j, edge);
// Check for negative cycles
for (int i = 0; i next)
if (V[edge->v].distance > V[i].distance + edge->weight &&
V[i].distance != INT_MAX)
return false;
// All good
return true;
}
void Graph::Dijkstra(int s)
{
// Initialize
for (int i = 0; i tree;
for (int i = 0; i (V[i].distance, i));
// Iterate until tree is empty
while (tree.size())
{
// Get minimum element in tree
std::multimap::iterator it = tree.begin();
int u = it->second;
// Remove element from the tree and set its associated iterator
// to a past-the-end iterator.
tree.erase(it);
V[u].it = tree.end();
// Traverse edges
for (Edge *edge = V[u].edges; edge; edge = edge->next)
{
// Obtain destination vertex
int v = edge->v;
// Check if vertex is in the tree
bool is_in_tree = V[v].it != tree.end();
// Extract v from tree to update its key (distance)
if (is_in_tree)
tree.erase(V[v].it);
// Relax edge
Relax(u, edge);
// Insert v again with its new key (distance)
if (is_in_tree)
V[v].it = tree.insert(std::pair(V[v].distance, v));
}
}
}
File main.cc
#include
#include "Graph.h"
int main()
{
// Undirected graph shown in this document for the trace of the BFS
// algorithm.
Graph g(8);
g.AddUndirectedEdge(0, 1);
g.AddUndirectedEdge(0, 4);
g.AddUndirectedEdge(1, 5);
g.AddUndirectedEdge(2, 3);
g.AddUndirectedEdge(2, 5);
g.AddUndirectedEdge(2, 6);
g.AddUndirectedEdge(3, 6);
g.AddUndirectedEdge(3, 7);
g.AddUndirectedEdge(5, 6);
g.AddUndirectedEdge(6, 7);
g.BFS(1);
// Print graph and shortest paths
std::cout
#include
class Graph
{
struct Edge
{
int weight;
int distance;
int parent;
};
int size;
Edge *E;
public:
// Constructor
Graph(int size);
// Destructor
~Graph();
// Getter
int getSize() { return size; }
// Return edge u -> v
Edge *getEdge(int u, int v);
// Add a new edge connecting vertex 'u' with 'v'.
void AddEdge(int u, int v, int weight = 1);
// Add a new undirected (or bidirectional) edge. This consists in
// adding one edge u->v and another edge v->u.
void AddUndirectedEdge(int u, int v, int weight = 1);
// All-sources shortest paths
void FloydWarshall();
// Print shortest path for u->v. This function assumes that a
// previous call has been made to FloydWarshall()
void PrintShortestPath(int u, int v);
};
#endif
File Graph.cc
#include
#include "Graph.h"
Graph::Graph(int size)
{
this->size = size;
E = new Edge[size * size]();
for (int i = 0; i = 0 && u = 0 && v weight = weight;
}
void Graph::AddUndirectedEdge(int u, int v, int weight)
{
AddEdge(u, v, weight);
AddEdge(v, u, weight);
}
void Graph::FloydWarshall()
{
// Initialize
for (int i = 0; i parent = -1;
edge->distance = edge->weight;
if (i == j)
edge->distance = 0;
if (edge->weight != INT_MAX)
edge->parent = i;
}
}
// Shortest paths
for (int k = 0; k distance > i_k->distance + k_j->distance &&
i_k->distance != INT_MAX &&
k_j->distance != INT_MAX)
{
i_j->distance = i_k->distance + k_j->distance;
i_j->parent = k_j->parent;
}
}
}
}
}
void Graph::PrintShortestPath(int u, int v)
{
Edge *edge = getEdge(u, v);
if (u == v)
{
std::cout parent == -1)
{
std::cout parent);
std::cout "
#include "Graph.h"
int main()
{
// Undirected graph shown in the trace for the Floyd-Warshall algorithm
// on this document.
Graph g(5);
g.AddEdge(0, 1, 3);
g.AddEdge(0, 2, 8);
g.AddEdge(0, 4, -4);
g.AddEdge(1, 4, 7);
g.AddEdge(1, 3, 1);
g.AddEdge(2, 1, 4);
g.AddEdge(3, 0, 2);
g.AddEdge(3, 2, -5);
g.AddEdge(4, 3, 6);
g.FloydWarshall();
// Print shortest paths
for (int i = 0; i < g.getSize(); i++)
{
std::cout << "Shortest paths from vertex " << i << ":\n";
for (int j = 0; j < g.getSize(); j++)
{
std::cout << "Path from " << i << " to "
<< j << ": ";
g.PrintShortestPath(i, j);
std::cout << '\n';
}
std::cout << '\n';
}
}