next up previous contents
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 up previous contents
Next: GraphObject Attributes Up: Algorithms Previous: Algorithms
RHS Linux User
1/26/1998