Graphs

ORD
SFO

LAX DFW

© 2010 Goodrich, Tamassia Graphs 1

 Graphs
 way of representing relationships that exist between pairs of objects
 A graph is a pair (V, E), where
 V is a set of nodes, called vertices
 E is a collection of pairs of vertices, called edges
 Vertices and edges are positions and store elements
 Example:
 A vertex represents an airport and stores the three-letter airport code
 An edge represents a flight route between two airports and stores the
mileage of the route

PSH
LHR
DUB
ISB
HNL
SHR KHR
© 2010 Goodrich, Tamassia QTA
 Edge Types
 Directed edge
 ordered pair of vertices (u,v)
first vertex u is the origin flight
ISB LHR


 second vertex v is the destination AA 1206

 e.g., a flight
 Undirected edge
 unordered pair of vertices (u,v) 849
e.g., a flight route ISB LHR

miles
 Directed graph
 all the edges are directed
 e.g., route network
 Undirected graph
 all the edges are undirected
 e.g., flight network
 Mixed graph
 Combination of directed and undirected graph
© 2010 Goodrich, Tamassia Graphs 3
 Applications
cslab1a cslab1b

 General [Link]
 Social networks
 Google map
[Link]
 Electronic Circuits
 Transportation networks [Link]
 Highway network [Link]
 Flight network [Link]

 Computer networks
 Local area network [Link]
 Internet John

 Web Paul
David

 Databases
 Entity-relationship diagram
© 2010 Goodrich, Tamassia Graphs 4
 Terminology
 End vertices (or endpoints) of an edge
 U and V are the endpoints of a
 Edges incident on a vertex V
a, d, and b are incident on V a b

h j
 Adjacent vertices
 U and V are adjacent U d X Z
Degree of a vertex c

e i
 X has degree 5
 Parallel edges W g
 h and i are parallel edges
 Self-loop f
 j is a self-loop
Y

© 2010 Goodrich, Tamassia Graphs 5

 Terminology (cont.)
 Path
 sequence of alternating vertices and edges
 begins with a vertex
 ends with a vertex
 each edge is preceded and followed by its endpoints
 Simple path
 path such that all its vertices and edges are V
distinct a b
P1
Examples

U d X Z
 P1=(V,b,X,h,Z) is a simple path
P2=(U,c,W,e,X,g,Y,f,W,d,V) is a path that is P2 h

not simple c e
 Simple Graph W g
 No parallel edges or self-loops
 edges of a simple graph are a et of vertex pairs
(and not just a collection).
f
Y
© 2010 Goodrich, Tamassia Graphs 6
 Terminology (cont.)
 Cycle
 Circular sequence of alternating
vertices and edges
 each edge is preceded and followed V
by its endpoints a b
Simple cycle

U d X Z
 cycle such that all its vertices
and edges are distinct C2 h
 Examples c e C1
 C1=(V,b,X,g,Y,f,W,c,U,a,) is a W g
simple cycle
 C2=(U,c,W,e,X,g,Y,f,W,d,V,a,) f
is a cycle that is not simple Y

© 2010 Goodrich, Tamassia Graphs 7

 Properties
Property 1 Notation
Sv deg(v) = 2m n number of vertices
Proof: each edge is counted m number of edges
twice deg(v) degree of vertex v
Property 2
In an undirected simple graph Example
m  n (n - 1)/2
 n = 4
Proof: each vertex has degree
at most (n - 1)  m = 6

 deg(v) = 3

© 2010 Goodrich, Tamassia Graphs 8

 Main Methods of the Graph ADT
As an ADT, a graph is a collection of elements that are stored at the
graph’s positions—its vertices and edges
Vertic v: *v: reference to element associated with vertex v
Edge e: *e: reference to element associated with edge e
 Access methods  Update methods
 insertVertex(o):
 [Link]():  insert a vertex storing element o
 a list of the two endvertices of e  insertEdge(v, w, o):
 [Link](v):  insert an edge (v,w) storing element o
 the vertex opposite of v on e  eraseVertex(v):
 remove vertex v (and its incident edges)
 [Link](v):  eraseEdge(e):
 true if u and v are adjacent  remove edge e
 [Link](v):  Iterable collection methods
 Test whether e is incident on v.  incidentEdges(v):
 list of edges incident to v

 vertices():
 list of all vertices in the graph
 edges():
© 2010 Goodrich, Tamassia Graphs  list of all edges in the graph 9
 Data Structures for graphs
 Graph Representation
 Edge List
 Adjacency List
 Adjacency Matrix

© 2010 Goodrich, Tamassia Graphs 10

 Edge List Structure
 Vertex object u
 element a c
 reference to position in
vertex sequence b d
v w z
 Edge object
 element
 origin vertex object
 destination vertex object
 reference to position in edge
sequence u v w z
 Vertex sequence
 sequence of vertex objects
 Unsorted
 Space O(n) a b c d
 Edge sequence
 sequence of edge objects
 Unsorted
 Space O(m)

© 2010 Goodrich, Tamassia Graphs 11

 Edge List Structure
 Advantages
 easy to implement
 [Link]()
 Disadvantages
 Have to examine the entire edge sequence O(m) for the
following operations
 [Link]()
 [Link](w)
 eraseVertix(v)

© 2010 Goodrich, Tamassia Graphs 12

 How to Improve Edge List
Structure?
 The problem with edge list structure
 [Link]() takes O(m)
 Each vertex does not know which edges are incident on it

 Solution: put p pointers (reference) from each vertex

to the edge object incident on this vertex
 Each vertex can have lots of edges incident on it
 Thus we need a sequence of incident vertices
 this sequence is called Adjacency List, because it’s usually
implemented as a list

u
a c
b d
v w z
© 2010 Goodrich, Tamassia Graphs 13
 Adjacency List Structure
 Edge list structure
 Incidence sequence for each
vertex I(u):
 sequence of references to
edge objects of incident
edges
 Example: I(v) consists of
References to edges a and b
 Augmented edge objects:
 references to associated
positions in incidence
sequences of end vertices
 Example: Edge b has references
to associated positions in I(w)
and I(v)

© 2010 Goodrich, Tamassia Graphs 14

 Adjacency List Structure
 Complexity
 Space Complexity
 Vertex sequence: O(n)
 Edge sequence: O(m)
 Adjacency lists: O(Σv deg(v) ) = 2m = O(m)
 For vertex v, O(deg(v)) for the adjacency list of v.

 Thus total space is O(n + m)

© 2010 Goodrich, Tamassia Graphs 15

 Adjacency List Structure
 Complexity
 Time Complexity

© 2010 Goodrich, Tamassia Graphs 16

 Adjacency List Structure
 Advantages:
 adjacency list structure provides improved running
times for the following functions:
 Method [Link]() takes time proportional to the
number of incident vertices of v, that is, O(deg(v))
time.
 Method [Link](w) can be performed by inspecting
either the incidence collection of v or that of w.
 By choosing the smaller of the two, we get O(min(deg(v),deg(w)))
running time.
 Method eraseVertex(v) takes O(deg(v)) time.
 Disadvantages:
 Implementation complexity
© 2010 Goodrich, Tamassia Graphs 17
 Adjacency Matrix Structure
 Edge list structure
 Augmented vertex objects (V)
 Integer key (index) associated
with vertex
 2D-array adjacency array (A)
 two-dimensional n × n array A
 A[i, j] holds a reference to the
edge (v,w), where v is the vertex
with index i and w is the vertex
with index j. if it exists, If there is
no such edge, then A[i, j] = null.
 Cost adjacency matrix
 Weighted graphs
 Directed graphs
 Undirected graphs

© 2010 Goodrich, Tamassia Graphs 18

 Adjacency Matrix Structure
 Complexity:
 Space: O(n2)
 Time:

© 2010 Goodrich, Tamassia Graphs 19

 Graph Data Structures: Performance
 n vertices, m edges
 no parallel edges
Edge Adjacency Adjacency
 no self-loops List List Matrix
Space n+m n+m n2
[Link]() m deg(v) n
[Link] (v) m min(deg(v), deg(w)) 1
insertVertex(o) 1 1 n2
insertEdge(v, w, o) 1 1 1
eraseVertex(v) m deg(v) n2
eraseEdge(e) 1 1 1

© 2010 Goodrich, Tamassia Graphs 20

 Summary of Graph Data Structures
 Edge list structure
 To be used only out of laziness
 Any lazy Student here ?
 Why did we study it?
 It’s a good starting point (as well as part of) for the other data structures
 Adjacency list
 Good performance for any graph
 Most complicated to implement
 2D adjacency array, to be used when:
 Good choice only for dense graphs (m is O(n2), that is it has a lot of edges)
 And used only in case when the set of vertices stays fixed (no vertex
insertion or deletion)
 In cases when the above 2 conditions hold, adjacency array is the best
choice

© 2010 Goodrich, Tamassia Graphs 21