Graph Algorithms

Graph Searches (HSM Ch.6.2)
- Depth first search (HSM Ch.6.2.1)
  - Algorithm (HSM Prog.6.1), Examples (HSM Fig.6.16), Analysis
  - Implementation using LEDA
    - DFS.cpp
    - Run as DFS <number of nodes> <number of edges>
- Breadth first search (HSM Ch.6.2.2)
  - Algorithm (HSM Prog.6.2), Examples (HSM Fig.6.16), Analysis
- Spanning trees (HSM Ch.6.2.4)
  - Examples (HSM Fig.6.18)
Connected Components (HSM Ch.6.2.3)
- Definition (HSM p.334)
- Examples (HSM Fig.6.5-6)
- Algorithm (HSM Prog.6.3), Analysis (HSM p.348)
- Biconnected components (HSM Ch.6.2.5)
  - Motivation (HSM p.351), Example (HSM Fig.6.19)
  - Definitions (HSM p.350-2)
  - Depth first spanning trees (HMS Fig.6.20)
  - Depth First numbers, Lowest Ancestor numbers (HSM Prog.6.4)
  - Algorithm (HSM Prog.6.5), Analysis
  - Implementation using LEDA
    - BCComponents.cpp
    - Run as BCComponents <number of nodes> <number of edges>
    - Most interesting results occur when <number of nodes> == <number of edges>
Minimum Cost Spanning Trees (HSM Ch.6.3)
- Definition (HSM p.356-7)
- Example (HSM Fig.6.22(a))
- Kruskal's Algorithm (HSM Ch.6.3.1)
  - Example (HSM Fig.6.22)
  - Algorithm (HSM Prog.6.6)
  - Implementation
    - Sorting the edges (O(elog(e))) and taking in order (O(e))
    - Constructing a MIN heap (O(e)) and taking (O(elog(e)))
    - Detecting cycles (O(elog(e)))
- Prim's Algorithm (HSM Ch.6.3.2)
  - Example (HSM Fig.6.23)
  - Algorithm (HSM Prog.6.7), Analysis
- Sollin's Algorithm (HSM Ch.6.3.3)
  - Example (HSM Fig.6.24)
  - Algorithm
```
Form a forest consisting of the nodes of the graph
While the forest has more than one tree
    Foreach tree in the forest
        Choose the cheapest edge 
        from a vertex in the tree to a vertex not in the tree
        (If none exists, exit with failure)
    Merge trees with common vertices
```
    Analysis
Shortest Paths in Directed Graphs (HSM Ch.6.4)
- Single source, All destinations, Nonnegative weights (HSM Ch.6.4.1)
  - Example (HSM Fig.6.25)
  - Motivation for algorithm (HSM p.364-5)
  - Example (HSM Fig.6.25)
  - Dijkstra's Algorithm (HSM Prog.6.8), Analysis
  - Another example (HSM Fig.6.26-7)
  - Gives an MST rooted at the source
- Single source, All destinations, General weights (HSM Ch.6.4.2)
  - No negative weight cycles (HSM Fig.6.29)
  - Algorithm fails (HSM Fig 6.28)
  - Motivation for algorithm (HSM p.370)
  - Example (HSM Fig.6.30)
  - Bellman-Ford Algorithm (HSM Prog.6.9), Analysis
  - Example (HSM Fig.6.30)
- All pairs shortest paths (HSM Ch.6.4.3)
  - Do single source for each vertex, expensive
  - Motivation for algorithm (HSM p.372)
  - Example (HSM Fig.6.31)
  - Algorithm (HSM Prog.6.10), Analysis
  - Example (HSM Fig.6.31)
Transitive Closure (HSM Ch.6.4.4)
- Definition (HSM p.373)
- Example (HSM Fig.6.32)
- Directed graphs
  - Use all-pairs shortest paths to compute A⁺
  - Modify to have Boolean rather than numeric entries
- Undirected graphs
  - Use connected components to compute A⁺

Exercises

Graph Searches: HSM Ch.6.2, exercise 1-4.
Connected Components: HSM Ch.6.2, exercise 6.
Minimum Cost Spanning Trees: HSM Ch.6.3, exercise 3, 5.
Shortest Paths: HSM Ch.6.4, exercise 5, 7, 10.
Transitive Closure: HSM Ch.6.4, exercise 19.

Lab Tasks

Breadth First Search

Exam Style Questions

Give the algorithm for a {DFS,BFS} of a graph.
List the nodes visited in the order of a {DFS,BFS} of this graph.
[Picture of some graph, make up your own :-]
Draw a {DFS,BFS} spanning tree of this graph.
[Picture of some graph, make up your own :-]
Compute the DFN and LOW values (as used in determining bi-connected components) of the node of this graph.
[Picture of some graph, make up your own :-]
Give {Kruskal's,Prim's,Sollin's} algorithm for finding a minimal cost spanning tree of a graph.
List the order in which edges of the graph below are added to a minimal spanning tree, using {Kruskal's,Prim's,Sollin's} algorithm.
[Picture of some graph, make up your own :-]
Give {Dijkstra's,Bellman-Ford,all-pairs shortest paths} algorithm for find shortest paths in a graph.
Show the successive values computed in the the execution of {Dijkstra's,Bellman-Ford,all-pairs shortest paths} algorithm on this graph.
[Picture of some graph, make up your own :-]
Write out the adjacency matrix for the transitive closure of this graph.
[Picture of some graph, make up your own :-]
What is the asymptotic complexity of the {DFS,BFS,bi-connected components, Kruskal's,Prim's,Sollin's,Dijkstra's,Bellman-Ford,all-pairs shortest paths} algorithm?
Given below is the {DFS,BFS,bi-connected components, Kruskal's,Prim's,Sollin's,Dijkstra's,Bellman-Ford,all-pairs shortest paths} algorithm.
[Pretend the algorithm is written out here]
Derive, using using step counts or reasonable explanation, the asymptotic complexity of this algorithm.