# 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 graph-processing problems:

s-t Path

Is there a path between vertices s and t?

Shortest s-t 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).