Lecture Notes for CS 512, Algorithm Design

7 September 1999

1. Topological sorting.

   1. Graph terms: directed, in-degree, out-degree, path, cycle, acyclic.

   2. Models this before that relations.

      1. nodes are activities; directed edges are do this before that relations.

      2. Examples: programming languages; activity charts (pert or gantt charts); related mathematically to the partial order.

         Observations - acyclic, definite starting points.

   3. Objective: linearize the graph to produce a list of tasks in the proper order (a topological order).

      1. Observation - Many topological orders per graph; do a first nodes first, then consider the rest.

      2. Questions: Are we doing it correctly? Are we making progress?

   4. Algorithm: find in-degrees and leaders; peel off each leader, adjusting in-degrees and new leaders each time.

   5. Cost: touch each node and each edge, so cost is O(|V| + |E|).

2. Graph Traversals.

   1. Graph terminology: child, sibling, parent, ancestor, descendent, level, subgraphs, tree, spanning tree.

   2. Lots of them: Hamiltonian, Eulerian

   3. Depth-first search.

      1. mark; work; recurse; work - pre and post work for each vertex.

      2. all nodes and edges touched at least once (undirected).

      3. ergo, cost is O(|V| + |E|).

      4. depth-first numbering - ancestor numbers are smaller than child numbers.

      5. depth-first spanning tree - Edges go up and down, not across.

      6. directed graphs - dfs numbers preserve ancestry over edges.

         1. edges - tree, back, forward, and cross.

         2. back edges indicate cycles.

   4. Breadth-first search.

      1. visit children first - a queue; pre-work but no post-work.

      2. properties - parents get to children first; the paths from node 1 to all other nodes is shortest in the graph; non-tree edges span adjacent levels only.

3. Single-source shortest paths.

   1. Objective - given n, find the shortest paths from n to all other nodes in the graph.

   2. Graph terminology - weights, path weights.

   3. acyclic graphs - use a topological sort to order the nodes; bottom up.

   4. arbitrary graphs - start from the top down; blob out for new paths.

      1. is the new path truly the minimal path from v?

      2. greed.

      3. heap insertion or deletion can take log steps; |V| deletions and |E| modifications (additions) leads to O(|V|log(|V|) + |E|log(|V|)) cost.

4. Minimum-cost spanning tree.

   1. Objective - A least cost tree subgraph; broadcast.

   2. Observation - this is almost sssp, except now edges are important.

This page last modified on 7 September 1999.