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