368
Comment:
|
1239
|
Deletions are marked like this. | Additions are marked like this. |
Line 1: | Line 1: |
= Graph Theory = | = Graph Theory = |
Line 4: | Line 4: |
'''See Also''' TreeStructures == Notation == A graph is usually specified by: <<latex($G=(V,E)$)>> The size of input has two components <<latex2($|V|,|E|$)>> In AsymptoticNotation we abuse the notation for size by writing <<latex($O(VE)=O(|V|*|E|)$)>> Denote the set of vertices in graph G in pseudocode as <<latex($V[G]$)>> and the edges <<latex($E[G]$)>> |
|
Line 9: | Line 25: |
* 22.1: RepresentingGraphs | |
Line 14: | Line 31: |
* TopologicallySortingDAG * DecomposingDAGintoStronglyConnectComponents |
* TopologicallySortingDag * Decomposing a graph into its StronglyConnectedComponents |
Line 18: | Line 35: |
* MinimumWeightSpanningTree * Minimum Spanning Trees are generally GreedyAlgorithms * KruskalAlgorithm * PrimAlgorithm == Chapter 24-25 == * 24: Shortest Path to all vertices from a single vertex * 25: AllPairsShortestPathProblem == Chapter 26 == * MaxFlowNetwork * This general problem arises in many forms and a good algorithm for computer MaxFlow can be used to solve a variety of related problems |
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:
<<latex($G=(V,E)$)>>
The size of input has two components <<latex2($|V|,|E|$)>>
In AsymptoticNotation we abuse the notation for size by writing
<<latex($O(VE)=O(|V|*|E|)$)>>
Denote the set of vertices in graph G in pseudocode as <<latex($V[G]$)>> and the edges <<latex($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