# Graph Algorithms

A graph is a way of representing relationships that exist between pairs of objects.
That is, a graph is a set of objects, called vertices, together with a collection of
pairwise connections between them, called edges.

Course Outline

## Topological Sort

Let ~G be a directed graph with n vertices and m edges, using
an adjacency list representation. The topological sorting algorithm runs in O(n+m)
time using O(n) auxiliary space, and either computes a topological ordering of ~G
or fails to include some vertices, which indicates that ~G has a directed cycle.

View details »

## Minimum Spanning Trees

Suppose we wish to connect all the computers in a new office building using the
least amount of cable. We can model this problem using an undirected, weighted
graph G whose vertices represent the computers, and whose edges represent all
the possible pairs (u,v) of computers, where the weight w(u,v) of edge (u,v) is
equal to the amount of cable needed to connect computer u to computer v. Rather
than computing a shortest-path tree from some particular vertex v, we are interested
instead in finding a tree T that contains all the vertices of G and has the minimum
total weight over all such trees. Algorithms for finding such a tree are the focus of
this section.

View details »

## Shortest Path

we might want to use a graph to represent the roads between
cities, and we might be interested in finding the fastest way to travel cross-country.
In this case, it is probably not appropriate for all the edges to be equal to each other,
for some inter-city distances will likely be much larger than others. Likewise, we
might be using a graph to represent a computer network (such as the Internet), and
we might be interested in finding the fastest way to route a data packet between
two computers. In this case, it again may not be appropriate for all the edges to
be equal to each other, for some connections in a computer network are typically
much faster than others (for example, some edges might represent low-bandwidth
connections, while others might represent high-speed, fiber-optic connections). It
is natural, therefore, to consider graphs whose edges are not weighted equally.

View details »