Transcript CSC 2500 Computer Organization

CSC 2300
Data Structures & Algorithms
March 30, 2007
Chapter 9. Graph Algorithms
Today – Graphs

Graphs –




Overview
Definitions
Representation
Topological Sort
Graphs – Overview
Definitions
More Definitions
Conventions
Directed Graph – Example
Graph Representations
1.
2.
Adjacency matrix
Adjacency list
Adjacency Matrix



What does adjacency matrix look like?
There are |E| edges and |V| vertices.
How much space is used?
Adjacency List – Example


There are |E| edges and |V| vertices.
How much space is used?
Two More Examples
Graph Algorithms Overview
Topological Sort
Example – Course Prerequisites
Example – Indegrees



What are the indegrees of the seven vertices?
Is there a vertex with indegree = 0?
Is it possible that there exists no vertex with indegree = 0?
Topological Sort




Scan the array of vertices to look for a vertex with indegree 0
that has not been assigned a topological number.
There are |E| edges and |V| vertices.
What is the running time of this algorithm?
Is it possible to do better?
Improved Topological Sort






Why always scan through all the vertices?
Only a few vertices have their indegrees updated during
each iteration.
We keep all (unassigned) vertices of indegree 0 in a queue.
When a vertex v is removed from the queue, all vertices
adjacent to v will have their indegrees decremented. A
vertex is placed in the queue if its indegree has fallen to 0.
There are |E| edges and |V| vertices.
What is the running time of this new approach?
Improved Topological Sort
Topological Sort – Example

How many iterations? Big Oh of what?