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. <#7245#>
Figure 3.7: Depth-First Search
Priority Algorithm/Property input output attr's & algs used
2 Biconnected Undir. Set<#7253#>;SPMlt;<#7253#>Set<#7255#>;SPMlt;<#7255#>Vertex*<#7257#>;SPMgt;<#7257#> <#7259#>;SPMgt;<#7259#> DFS - back
  Components G   DFS - low
        DFS - discovery_time
5 Bipartite Matching Undir. Set<#7261#>;SPMlt;<#7261#>Edge*<#7263#>;SPMgt;<#7263#> weight
    G   Ford-Fulkerson - flow
* Breadth-First Search G,v Sequence<#7265#>;SPMlt;<#7265#>Vertex*<#7267#>;SPMgt;<#7267#> color
        distance
        ???
* Depth-First Search G Sequence<#7269#>;SPMlt;<#7269#>Vertex*<#7271#>;SPMgt;<#7271#> color
        starttime
        finishtime
        back
        low
        pred
3 Dijkstra's Single G, v Set<#7273#>;SPMlt;<#7273#>double<#7275#>;SPMgt;<#7275#> weight
  Source Shortest     distance
  Paths     pred
4 Ford-Fulkerson Network double flow
  Maximum Flow s, t   capacity
        partition
7* Floyd-Warshall G Matrix<#7277#>;SPMlt;<#7277#>double<#7279#>;SPMgt;<#7279#> weight
  All Pairs Shortest     distance
  Paths     pred
* Kruskal's MST G Set<#7281#>;SPMlt;<#7281#>Edge*<#7283#>;SPMgt;<#7283#> weight
        mark
        parent
        pred
6 Prim's MST G Set<#7285#>;SPMlt;<#7285#>Edge*<#7287#>;SPMgt;<#7287#> weight
        key
        pred
1 Strongly-Connected Digraph Set<#7289#>;SPMlt;<#7289#>Set<#7291#>;SPMlt;<#7291#>Vertex*<#7293#>;SPMgt;<#7293#> <#7295#>;SPMgt;<#7295#> DFS - mark
  Components     DFS - finishtime
* TopSort DAG Sequence<#7297#>;SPMlt;<#7297#>Vertex*<#7299#>;SPMgt;<#7299#> DFS - finishtime
<#7245#>