|
⇤ ← Revision 1 as of 2004-09-27 20:23:53
Size: 368
Comment:
|
Size: 1131
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| = Graph Theory = | = Graph Theory = |
| Line 4: | Line 4: |
== Notation == A graph is usually specified by: {{{ G = (V,E) }}} The size of input has two components {{{ |V|, |E| }}} In AsymptoticNotation we abuse the notation for size by writing {{{ O(VE) = O(|V|*|E|) }}} To denote the set of vertices in graph G in pseudocode as {{{ V[G] and the edges E[G] }}} |
|
| Line 14: | Line 39: |
| * TopologicallySortingDAG * DecomposingDAGintoStronglyConnectComponents |
* TopologicallySortingDag * DecomposingDagIntoStronglyConnectComponents |
| Line 18: | Line 43: |
* MinimumWeightSpanningTree * Minimum Spanning Trees are generally GreedyAlgorithms == 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.
Notation
A graph is usually specified by:
G = (V,E)
The size of input has two components
|V|, |E|
In AsymptoticNotation we abuse the notation for size by writing
O(VE) = O(|V|*|E|)
To denote the set of vertices in graph G in pseudocode as
V[G] and the edges E[G]
Chapter 22
Concepts
Applications
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