## 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#>