Next: GraphObject Attributes Up: Algorithms Previous: Algorithms

## Algorithm Specifications

The starred algorithms are finished, and the other algorithms are ranked in order of urgency. Hopefully these rankings will not be necessary after July 31st, 1996.

Figure 2.2: Depth-First Search
Priority | Algorithm/Property | input | output | attr's & algs used
2 | Biconnected | Undir. | Set<Set<Vertex*> > | DFS - back
| Components | G |  | DFS - low
|  |  |  | DFS - discovery_time
5 | Bipartite Matching | Undir. | Set<Edge*> | weight
|  | G |  | Ford-Fulkerson - flow
* | Breadth-First Search | G,v | Sequence<Vertex*> | color
|  |  |  | distance
|  |  |  | ???
* | Depth-First Search | G | Sequence<Vertex*> | color
|  |  |  | starttime
|  |  |  | finishtime
|  |  |  | back
|  |  |  | low
|  |  |  | pred
3 | Dijkstra's Single | G, v | Set<double> | weight
| Source Shortest |  |  | distance
| Paths |  |  | pred
4 | Ford-Fulkerson | Network | double | flow
| Maximum Flow | s, t |  | capacity
|  |  |  | partition
7* | Floyd-Warshall | G | Matrix<double> | weight
| All Pairs Shortest |  |  | distance
| Paths |  |  | pred
* | Kruskal's MST | G | Set<Edge*> | weight
|  |  |  | mark
|  |  |  | parent
|  |  |  | pred
6 | Prim's MST | G | Set<Edge*> | weight
|  |  |  | key
|  |  |  | pred
1 | Strongly-Connected | Digraph | Set<Set<Vertex*> > | DFS - mark
| Components |  |  | DFS - finishtime
* | TopSort | DAG | Sequence<Vertex*> | DFS - finishtime

Next: GraphObject Attributes Up: Algorithms Previous: Algorithms