CSE 421Introduction to Algorithms

Table of Contents

CSE 421Introduction to Algorithms

Undirected Depth-First Search

Undirected Depth-First Search

Directed Depth First Search

An Application:

Strongly Connected Components

PPT Slide

PPT Slide

Uses for SCC’s

Two Simple SCC Algorithms

Goal:

Lemma 1

Definition

Lemma 2

Subgoal

Definition

PPT Slide

Lemma 3

Lemma 4

How to Find Exits (in 1st component)

PPT Slide

Finding Other Components

Lemma 3’

Lemma 4’

How to Find Exits (in 1st component)

SCC Algorithm

PPT Slide

Complexity

Email: ruzzo@cs.washington.edu

Home Page: http://www.cs.washington.edu/education/courses/421

Other information:
(c) 1998, University of Washington, CSE