Transcript CSE 326: Data Structures Lecture #7 Branching Out

CSE 326: Data Structures
Lecture #20
Graphs I.5
Alon Halevy
Spring Quarter 2001
Outline
•
•
•
•
•
Some definitions
Topological Sort
Graph Data Structures
Graph Properties
Shortest Path Problem
Directed vs. Undirected Graphs
• In directed graphs, edges have a specific direction:
Han
Luke
aka: di-graphs
Leia
• In undirected graphs, they don’t (edges are two-way):
Han
Luke
Leia
• Vertices u and v are adjacent if (u, v)  E
Weighted Graphs
Each edge has an associated weight or cost.
Clinton
20
Mukilteo
Kingston
30
Bainbridge
35
Edmonds
Seattle
60
Bremerton
There may be more
information in the graph as well.
Paths
A path is a list of vertices {v1, v2, …, vn} such
that (vi, vi+1)  E for all 0  i < n.
Chicago
Seattle
Salt Lake City
San Francisco
Dallas
p = {Seattle, Salt Lake City, Chicago, Dallas, San Francisco, Seattle}
Path Length and Cost
Path length: the number of edges in the path
Path cost: the sum of the costs of each edge
3.5
Chicago
Seattle
2
2
2
Salt Lake City
2.5
2.5
2.5
3
San Francisco
Dallas
length(p) = 5
cost(p) = 11.5
Simple Paths and Cycles
A simple path repeats no vertices (except that the first can
be the last):
– p = {Seattle, Salt Lake City, San Francisco, Dallas}
– p = {Seattle, Salt Lake City, Dallas, San Francisco, Seattle}
A cycle is a path that starts and ends at the same node:
– p = {Seattle, Salt Lake City, Dallas, San Francisco, Seattle}
A simple cycle is a cycle that repeats no vertices except
that the first vertex is also the last (in undirected
graphs, no edge can be repeated)
Connectivity
Undirected graphs are connected if there is a path between
any two vertices
Directed graphs are strongly connected if there is a path from
any one vertex to any other
Di-graphs are weakly connected if there is a path between any
two vertices, ignoring direction
A complete graph has an edge between every pair of vertices
Graph Density
A sparse graph has O(|V|) edges
A dense graph has (|V|2) edges
Anything in between is either sparsish or densy depending on
the context.
We use V and E as the parameters in our analysis.
Trees as Graphs
• Every tree is a graph with
some restrictions:
– the tree is directed
– there are no cycles (directed
or undirected)
– there is a directed path from
the root to every node
A
B
C
D
E
F
G
I
H
J
Directed Acyclic Graphs (DAGs)
DAGs are directed
graphs with no
cycles.
main()
mult()
add()
access()
Trees  DAGs  Graphs
read()
Topological Sort
Given a graph, G = (V, E), output all the vertices
in V such that no vertex is output before any other
vertex with an edge to it.
reserve
flight
call
taxi
taxi to
airport
pack
bags
check in
airport
take
flight
locate
gate
Topo-Sort Take One
Label each vertex’s in-degree (# of inbound edges)
While there are vertices remaining
Pick a vertex with in-degree of zero and output it
Reduce the in-degree of all vertices adjacent to it
Remove it from the list of vertices
runtime:
Topo-Sort Take Two
Label each vertex’s in-degree
Initialize a queue to contain all in-degree zero vertices
While there are vertices remaining in the queue
Pick a vertex v with in-degree of zero and output it
Reduce the in-degree of all vertices adjacent to v
Put any of these with new in-degree zero on the queue
Remove v from the queue
runtime:
Graph Representations
• List of vertices + list of edges
Han
Luke
Leia
• 2-D matrix of vertices (marking edges in the cells)
“adjacency matrix”
• List of vertices each with a list of adjacent vertices
“adjacency list”
Adjacency Matrix
A |V| x |V| array in which an element (u, v)
is true if and only if there is an edge from u to v
Han
Luke
Han
Han
Luke
Luke
Leia
Leia
runtime:
space requirements:
Leia
Adjacency List
A |V|-ary list (array) in which each entry stores a
list (linked list) of all adjacent vertices
Han
Han
Luke
Luke
Leia
Leia
runtime:
space requirements:
Single Source, Shortest Path
Given a graph G = (V, E) and a vertex s  V,
find the shortest path from s to every vertex in V
Many variations:
–
–
–
–
weighted vs. unweighted
cyclic vs. acyclic
positive weights only vs. negative weights allowed
multiple weight types to optimize
The Trouble with
Negative Weighted Cycles
A
2
-5
C
B
1
2
10
E
D
What’s the shortest path from A to E?
(or to B, C, or D, for that matter)
Unweighted Shortest Path Problem
Assume source vertex is C…
B
A
F
H
G
C
D
E
Distance to:
A
B
C
D
E
F
G
H
Dijkstra
Legendary figure in computer science; now a
professor at University of Texas.
Supports teaching introductory computer courses
without computers (pencil and paper programming)
Supposedly wouldn’t (until recently) read his e-mail;
so, his staff had to print out messages and put them
in his box.
Dijkstra’s Algorithm for
Single Source Shortest Path
• Classic algorithm for solving shortest path in
weighted graphs without negative weights
• A greedy algorithm (irrevocably makes decisions
without considering future consequences)
• Intuition:
–
–
–
–
shortest path from source vertex to itself is 0
cost of going to adjacent nodes is at most edge weights
cheapest of these must be shortest path to that node
update paths for new node and continue picking
cheapest path
Intuition in Action
2
A
1
4
D
2
B
1
2
10
9
4
C
2
7
3
F
1
G
8
E
H
1
Dijkstra’s Pseudocode
(actually, our pseudocode for Dijkstra’s algorithm)
Initialize the cost of each node to 
Initialize the cost of the source to 0
While there are unknown nodes left in the graph
Select the unknown node with the lowest cost: n
Mark n as known
For each node a which is adjacent to n
a’s cost = min(a’s old cost, n’s cost + cost of (n, a))
Dijkstra’s Algorithm in Action
2
A
1
4
D
2
B
1
2
10
9
4
C
2
E
known
cost
H
1
G
8
7
vertex
A
B
C
D
E
F
G
H
3
F
1
The Cloud Proof
Next shortest path from
inside the known cloud
G
Better path
to the same node
P
THE KNOWN
CLOUD
Source
But, if the path to G is the next shortest path,
the path to P must be at least as long.
So, how can the path through P to G be shorter?
Inside the Cloud (Proof)
Everything inside the cloud has the correct shortest path
Proof is by induction on the # of nodes in the cloud:
– initial cloud is just the source with shortest path 0
– inductive step: once we prove the shortest path to G is
correct, we add it to the cloud
Negative weights blow this proof away!
Revenge of the Dijkstra
Pseudocode
Initialize the cost of each node to 
s.cost = 0;
heap.insert(s);
While (! heap.empty)
n = heap.deleteMin()
For (each node a which is adjacent to n)
if (n.cost + edge[n,a].cost < a.cost) then
a.cost = n.cost + edge[n,a].cost
a.path = n;
if (a is in the heap) then heap.decreaseKey(a)
else heap.insert(a)
Data Structures
for Dijkstra’s Algorithm
|V| times:
Select the unknown node with the lowest cost
findMin/deleteMin
O(log |V|)
|E| times:
a’s cost = min(a’s old cost, …)
decreaseKey O(log |V|)
find by name O(1)
runtime: