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).