Transcript PPT printable

Mark Allen Weiss: Data Structures and Algorithm Analysis in Java
Chapter 9: Graphs
Summary
Lydia Sinapova, Simpson College
Summary of Graph Algorithms
 Basic Concepts
 Topological Sort
 Shortest Paths
 Spanning Trees
 Scheduling Networks
 Breadth-First and Depth First Search
 Connectivity
2
Basic Concepts
 Basic definitions: vertices and edges
 More definitions: paths, simple paths,
cycles, loops
 Connected and disconnected graphs
 Spanning trees
 Complete graphs
 Weighted graphs and networks
 Graph representation
Adjacency matrix
 Adjacency lists

3
Topological Sort
RULE: If there is a path from u to v,
then v appears after u in the ordering.
Graphs: directed, acyclic
Degree of a vertex U: the number of outgoing edges
Indegree of a vertex U: the number of incoming edges
The algorithm for topological sort uses "indegrees" of vertices.
Implementation: with a queue
Complexity: Adjacency lists: O(|E| + |V|),
Matrix representation: O(|V|2)
4
Shortest Path in Unweighted
Graphs
Data Structures needed:
Distance Table
Queue
Implementation: Breadth-First search using a queue
Complexity:
Matrix representation: O(|V|2)
Adjacency lists - O(|E| + |V|)
5
Algorithm
1. Store s in a queue, and initialize
distance = 0 in the Distance Table
2. While there are vertices in the queue:
Read a vertex v from the queue
For all adjacent vertices w :
If distance = -1 (not computed)
Distance = (distance to v) + 1
Parent = v
Append w to the queue
6
Shortest Path in Weighted
Graphs – Dijkstra’s Algorithm
1. Store s in a priority queue with distance = 0
2. While there are vertices in the queue
DeleteMin a vertex v from the queue
For all adjacent vertices w:
Compute new distance
Store in / update Distance table
Insert/update in priority queue
7
Complexity
O(E logV + V logV) = O((E + V) log(V))
Each vertex is stored only once in the queue – O(V)
DeleteMin operation is :
O( V logV )
Updating the priority queue –
search and inseart:
performed at most for each edge:
O(log V)
O(E logV)
8
Spanning Trees
Spanning tree: a tree that contains all vertices
in the graph.
Number of nodes: |V|
Number of edges: |V|-1
9
Spanning Trees of Unweighted
Graphs
Breadth-First Search using a queue
Complexity: O(|E| + |V|) - we process all
edges and all nodes
10
Min Spanning Trees of Weighted
Graphs – Prim’s Algorithm
Find a spanning tree with the minimal sum
of the weights.
Similar to shortest paths in a weighted graphs.
Difference: we record the weight of the
current edge, not the length of the path.
Implementation: with a Priority Queue
Complexity: O(|E| log (|V|) )
11
Min Spanning Trees of Weighted
Graphs – Kruskal’s Algorithm
The algorithm works with the set of
edges, stored in Priority queue.
The tree is built incrementally starting
with a forest of nodes only and adding
edges as they come out of the priority
queue
Complexity: O(|E| log (|V|))
12
Scheduling Networks
Directed simple acyclic graph
Nodes: events, Source, Sink
Edges: activities (name of the task, duration)
 Find the earliest occurrence time (EOT) of an
event
 Find the earliest completion time (ECT) of an
activity
 Find the slack of an activity: how much the
activity can be delayed without delaying the
project
 Find the critical activities: must be completed on
time in order not to delay the project
13
EOT and ECT
Earliest occurrence time of an event
EOT(source) = 0
EOT( j ) = max ( EOTs of all activities preceding the event)
Earliest completion time of an activity
ECT( j, k ) = EOT( j ) + duration( j, k)
1. Sort the nodes topologically
2. For each event j : initialize EOT(j) = 0
3. For each event i in topological order
For each event j adjacent from i :
ECT(i,j) = EOT(i) + duration (i,j)
EOT(j) = max(EOT(j) , ECT(i,j))
14
Slack of activities
Compute latest occurrence time LOT(j) , slack(i, j)
1. Initialize
LOT(sink) = EOT(sink)
2. For each non-sink event i in the reverse topological order:
LOT(i) = min(LOT( j ) – duration( i, j))
3. For each activity (i,j)
slack( i, j ) = LOT( j ) – ECT( i, j)
Critical activities: slack(j) = 0
Critical path in the project:
all edges are activities with slack = 0
The critical path is found using breadth-first (or depth-first) search on the
edges
Complexity:
O(V + E) with adjacency lists,
O(V2)
with adjacency matrix
15
bfs(G)
list L = empty
tree T = empty
choose a starting vertex x
visit(x)
while(L nonempty)
remove edge (v,w) from
beginning of L
if w not visited
add (v,w) to T
visit(w)
Visit ( vertex v)
mark v as visited
for each edge (v,w)
add edge (v,w) to end of L
BFS and DFS
dfs(G)
list L = empty
tree T = empty
choose a starting vertex x
visit(x)
while(L nonempty)
remove edge (v,w) from
end of L
if w not visited
add (v,w) to T
visit(w)
Complexity: O( V + E)
16
Graph Connectivity
 Connectivity
 Biconnectivity – no cut vertices
 Articulation Points and Bridges
 Connectivity in Directed Graphs
 Strongly
connected
 Unilaterally connected
 Weakly connected
17