Lecture Notes for CS 512, Algorithm Design

Graph Traversals - 24 January 2000

1. graph traversals

   1. breadth first

      1. visit a child before a grandchild

      2. depth-first trees

      3. shortest path

   2. depth first

      1. visit a grandchild before a child

      2. depth-first trees

         1. start-stop intervals

         2. interval nesting

         3. edge types

      3. topological sorting

         1. dag

   3. other uses

      1. connected components

      2. finding trees and cycles

      3. two-coloring graphs - bipartite

      4. articulation vertices

This page last modified on 31 January 2000.