Scribd
Upload
71 views60 pages

Algorithms Ch22A

The document is a lecture on graph algorithms from a computer science course. It covers introductory graph concepts like representations and connectivity. It then discusses depth-first search and breadth-first search algorithms along with examples of applying them to directed and undirected graphs. Finally, it discusses applications of DFS and BFS like topological sorting of directed acyclic graphs.

Uploaded by

samroni
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
71 views60 pages

Algorithms Ch22A

The document is a lecture on graph algorithms from a computer science course. It covers introductory graph concepts like representations and connectivity. It then discusses depth-first search and breadth-first search algorithms along with examples of applying them to directed and undirected graphs. Finally, it discusses applications of DFS and BFS like topological sorting of directed acyclic graphs.

Uploaded by

samroni
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 60

UMass Lowell Computer Science 91.

404
Analysis of Algorithms
Prof. Karen Daniels
Spring, 2007

Overview: Graph Algorithms


Chapter 22
Graph Algorithms

Introductory Graph Concepts

A B A B
C C

D F D E F
E
Introductory Graph Concepts:
Motivation

Introductory Graph Concepts:


Representations

A B A B
C C
D E F D E F

0 1 1 0 0 0
0 1 1 0 0 0
1 0 1 0 1 1
0 0 1 0 1 1
1 1 0 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
0 1 0 1 0 1
0 1 0 1 0 0
0 1 0 0 1 0
0 0 0 0 1 0
Introductory Graph Concepts:
Paths, Cycles
A B
C
D E F

A B
C
D E F

A B
C
D E F

Introductory Graph Concepts:


Connectivity A B
C
D E F

A B
C
D E F

A B
C
D E F
A B
C
D E F
Depth-First Search (DFS)
&
Breadth-First Search (BFS)

Depth-First Search (DFS)


Example:
DFS of Directed Graph

DFS PseudoCode
Vertex Color Changes

Edge Classification
Example: (continued)
DFS of Directed Graph

Example: (continued)
DFS of Directed Graph
Example: (continued)
DFS of Directed Graph

Example: (continued)
DFS of Directed Graph
Example: (continued)
DFS of Directed Graph

Example: (continued)
DFS of Directed Graph
Example: (continued)
DFS of Directed Graph

Example: (continued)
DFS of Directed Graph
Example: (continued)
DFS of Directed Graph

Example: (continued)
DFS of Directed Graph
Example: (continued)
DFS of Directed Graph

Example: (continued)
DFS of Directed Graph
Example: (continued)
DFS of Directed Graph

Example: (continued)
DFS of Directed Graph
Example: (continued)
DFS of Directed Graph

Example: (continued)
DFS of Directed Graph
Example: (continued)
DFS of Directed Graph

Example: (continued)
DFS of Directed Graph
Example: (continued)
DFS of Directed Graph

Example: (continued)
DFS of Directed Graph
Example: (continued)
DFS of Directed Graph

Example: (continued)
DFS of Directed Graph
Example: (continued)
DFS of Directed Graph

Example: (continued)
DFS of Directed Graph
Example: (continued)
DFS of Directed Graph

Example: (continued)
DFS of Directed Graph
Example: (continued)
DFS of Directed Graph

Example: (continued)
DFS of Directed Graph
Example:
DFS of Undirected Graph

Example:
DFS of Undirected Graph
Example:
DFS of Undirected Graph

Example:
DFS of Undirected Graph
Example:
DFS of Undirected Graph

Example:
DFS of Undirected Graph
Example:
DFS of Undirected Graph

Example:
DFS of Undirected Graph
Example:
DFS of Undirected Graph

Example:
DFS of Undirected Graph
Example:
DFS of Undirected Graph

Example:
DFS of Undirected Graph
Example:
DFS of Undirected Graph

Example:
DFS of Undirected Graph
Example:
DFS of Undirected Graph

Example:
DFS of Undirected Graph
Example:
DFS of Undirected Graph

Example:
DFS of Undirected Graph
Example:
DFS of Undirected Graph

Example:
DFS of Undirected Graph
Example:
DFS of Undirected Graph

Example:
DFS of Undirected Graph
Example:
DFS of Undirected Graph

Example:
DFS of Undirected Graph
Example:
DFS of Undirected Graph

Example:
DFS of Undirected Graph
Example: (continued)
DFS of Undirected Graph

Elementary Graph Algorithms:


DFS

A
A B Tree Edge
Back
C
Edge Tree Edge
F
B Tree Edge
E Tree Edge
D E F
C Cross Edge
Tree Edge

D
Breadth-First Search (BFS)

BFS PseudoCode
Example:
BFS of Directed Graph

Example:
BFS of Directed Graph
Example:
BFS of Directed Graph

Example:
BFS of Directed Graph
Example:
BFS of Directed Graph

Example:
BFS of Directed Graph
Example:
BFS of Directed Graph

Example:
BFS of Directed Graph
Example:
BFS of Directed Graph

Example:
BFS of Directed Graph
Example:
BFS of Directed Graph

Example:
BFS of Directed Graph
Example:
BFS of Directed Graph

Example:
BFS of Directed Graph
Example:
BFS of Directed Graph

Example: (continued)
BFS of Directed Graph
Example:
BFS of Undirected Graph

Example:
BFS of Undirected Graph
Example:
BFS of Undirected Graph

Example:
BFS of Undirected Graph
Example:
BFS of Undirected Graph

Example:
BFS of Undirected Graph
Example:
BFS of Undirected Graph

Example:
BFS of Undirected Graph
Example:
BFS of Undirected Graph

Example:
BFS of Undirected Graph
Example:
BFS of Undirected Graph

Example:
BFS of Undirected Graph
Example:
BFS of Undirected Graph

Example:
BFS of Undirected Graph
Example:
BFS of Undirected Graph

Example: (continued)
BFS of Undirected Graph
Depth-First Search (DFS)
&
Breadth-First Search (BFS)

Depth-First Search (DFS)


&
Breadth-First Search (BFS)
Using the Results of DFS & BFS

Using the Results of DFS & BFS


Running Time Analysis

∑ time to construct DFS tree i


i =1

ri

∑ AdjList[ jth vertex in DFS tree i]


j =1
Running Time Analysis
ri
t
∑ ∑ AdjList[ jth vertex in DFS tree i]
i =1
j =1

O (| V | + | E |)

Topological Sort
Definition: DAG

Definition: Topological Sort


Elementary Graph Algorithms:
Topological Sort

for Directed, Acyclic Graph (DAG)


G=(V,E)

Topological Sort
Example

Example
Topological Sort

Topological Sort

You might also like