Graph Algorithms

In this section, we discuss algorithms involving graphs.

We will look at several such algorithms:
 Graph Traversal

Visit each vertex in a graph once.
 Shortest path

find the shortest path between two vertices.
 Travelling salesman

Find a path that contains a permutation of every node in the graph with minimized total cost.
 Minimum spanning tree (MST)

Construct a spanning tree connecting all the vertices in a graph minimizing the cost.

And here are some more graphprocessing problems:
 st Path

Is there a path between vertices s and t?
 Shortest st Path

What is the shortest path between vertices s and t?
 Cycle

Does the graph contain any cycles?
 Euler Tour

Is there a cycle that uses every edge exactly once?
 Hamilton Tour

Is there a cycle that uses every vertex exactly once?
 Connectivity

Is the graph connected, i.e. is there a path between all vertex pairs?
 Biconnectivity

Is there a vertex whose removal disconnects the graph?
 Planarity

Can you draw the graph on a piece of paper with no crossing edges?
 Isomorphism

Are two graphs isomorphic (the same graph in disguise).