Graph Theory
This page contains over view information and links to concepts covered in "Intro to Algorithms" by Cormen, Leiserson & Rivest.
See Also TreeStructures
Notation
A graph is usually specified by:
The size of input has two components [[latex2($$|V|,|E|$$)]]
In AsymptoticNotation we abuse the notation for size by writing
[[latex2($$O(VE)=O(|V|*|E|)$$)]]
Denote the set of vertices in graph G in pseudocode as latex2($$V[G]$$) and the edges latex2($$E[G]$$)
Chapter 22
Concepts
Applications
Decomposing a graph into its StronglyConnectedComponents
Chapter 23
Minimum Spanning Trees are generally GreedyAlgorithms
Chapter 24-25
- 24: Shortest Path to all vertices from a single vertex
Chapter 26
This general problem arises in many forms and a good algorithm for computer MaxFlow can be used to solve a variety of related problems