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