Size: 1162
Comment:
|
Size: 1250
Comment:
|
Deletions are marked like this. | Additions are marked like this. |
Line 4: | Line 4: |
'''See Also''' TreeStructures |
|
Line 9: | Line 11: |
{{{ G = (V,E) }}} |
[[latex2($$G=(V,E)$$)]] |
Line 13: | Line 13: |
The size of input has two components {{{ |V|, |E| }}} |
The size of input has two components [[latex2($$|V|,|E|$$)]] |
Line 21: | Line 17: |
{{{ O(VE) = O(|V|*|E|) }}} |
<<latex($O(VE)=O(|V|*|E|)$)>> |
Line 25: | Line 19: |
To denote the set of vertices in graph G in pseudocode as {{{ V[G] and the edges E[G] }}} |
Denote the set of vertices in graph G in pseudocode as [[latex2($$V[G]$$)]] and the edges [[latex2($$E[G]$$)]] |
Line 41: | Line 32: |
* DecomposingDagIntoStronglyConnectComponents | * Decomposing a graph into its StronglyConnectedComponents |
Line 47: | Line 38: |
* KruskalAlgorithm * PrimAlgorithm |
|
Line 57: | Line 50: |
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
<<latex($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