Transcript Graphs

Graphs
- Ed. 2. and 3.: Chapter 12
- Ed. 4.: Chapter 13
Graphs
• Graph ADT
- What is a graph?
- Graph methods
• Data structure for graphs
- Edge list structure, adjacency list
structure, adjacency matrix
• Graph Traversal
- Depth-first search
- Breadth-first search
• Directed graphs
The Graph Abstract Data Type
A salesman spends his time visiting n cities (or nodes)
cyclically. In one tour he visits each city just once, and finishes
up where he started. In what order should he visit them to
minimize the distance travelled?
graph: A set V of vertices (nodes) and a collection E of pairs
of vertices from V, called edges (arcs).
directed edge: The edge (u, v) is ordered, with the node u
preceding v.
Example:
If u represents Toronto and v represents Winnipeg, a directed
edge (u, v) can represent a trip from Toronto to Winnipeg while
(v, u) represents a trip from Winnipeg to Toronto. Therefore,
The edge (u, v) is not equal to (v, u).
u
(Toronto)
(u, v)
v
(Winnipeg)
(v, u)
undirected edge: The edge (u, v) is not ordered.
Example:
If u represents Winnipeg and v represents New York, and
assume that the edge (u, v) represents that both cities form
sister cities (for the sake of discussion), then the edge (u, v) is
undirected. In this case, the edge (u, v) is equal to (v, u).
u
(New York)
v
(Winnipeg)
(v, u)
Example 12.1
Graph of coauthorships among some authors
Snoeyink
Garg
Tollis
Tamassia
Goodrich
Vitter
Preparata
Chiang
Edges are undirected because coauthorship is a symmetric
relation.
Example 12.2
Inheritance between classes.
Object
Component
Container
Panel
Applet
JApplet
JComponent
Edges are directed because the inheritance relation is
asymmetric.
undirected graph: All the edges are undirected.
directed graph (digraph): All the edges are directed.
mixed graph: The graph have both directed and undirected
edges.
Example 12.1 is an undirected graph.
Example 12.2 is a digraph.
Example 12.3
A city map is a mixed graph with two-way and one-way
streets.
end vertices: The two vertices joined by an edge.
Edge
Winnipeg
Ottawa
endpoint
end vertex
endpoint
origin
desitination
end vertex
If the edge is directed, its first endpoint is its origin and the
other is the destination.
adjacent vertices: Endpoints of the same edge
Edge
Ottawa
Winnipeg
adjacent
vertices
An edge is said to be incedent on a vertex if the vertex is one
of the edge’s endpoints.
Edge
Ottawa
Winnipeg
incident on
both vertices
outgoing edge of a vertex: The vertex is the origin of the
directed edge.
Winnipeg
incoming edge of a vertex: The vertex is the destination of the
directed edge.
Ottawa
degree of a vertex v: The number of incident edges of v.
Denoted as deg(v).
Winnipeg
deg(v) = 4
in-degree of a vertex v: The number of the incoming edges.
Denoted as indeg(v).
out-degree of a vertex v: The number of the outgoing edges.
Denoted as outdeg(v).
Winnipeg
indeg(v) = 2
outdeg(v) = 2
Example: A flight network
AC201
AC112
Ottawa
JG120
Vancouver
AC200
Winnipeg
Calgary
JG131
WJ35
WJ75
JG130
Toronto
What are the degree, in-degree and out-degree of the airport in
Winnipeg?
Recall that in a set, all elements are unique. We refer to the
group of edges in a graph as a collection, not a set. This allows
duplicated edges called parallel edges or multiple edges.
Example:
There may be multiple flights from Winnipeg to Toronto.
Winnipeg
JG130
JG150
Toronto
self-loop: An edge whose two endpoints coincide.
Example:
self-loop
simple graph: A graph without parallel edges or self-loops.
We can say that the edges of a simple graph are a set of vertex
pairs. From now on, we assume all the graphs are simple unless
otherwise specified.
Example:
Some important properties of degree and the number of edges
in a graph.
Proposition 12.6: If G is a simple graph with m edges, then
 deg( v)  2m
vG
Number of edges: 4; The sum of degrees: 8
Proposition 12.7: If G is a directed graph with m edges, then
 indeg (v)   outdeg (v)  m
vG
vG
Number of edges = 4, sum of indeg(v) = 4,
sum of outdeg(v) = 4
Proposition 12.8: Let G be a simple graph with n vertices and
m edges. If G is undirected, then m  n(n – 1)/2, and if G is
directed, m  n(n – 1).
Number of vertices = 3, number of edges = 4
4 < 3 x (3 - 1) = 6
path of a graph: A sequence of alternating vertices and
edges, which starts at a vertex and ends at a vertex such that
each edge is incident to its predecessor and successor vertex.
Two examples
cycle: A path such that its start and end vertices are the same.
simple path: Each vertex on the path is distinct.
An example and a counter-example.
simple cycle: Each vertex on the cycle is distinct, except for
the first and last one.
An example and a counter-example
directed path: A path such that all the edges are directed and
are traversed along their direction.
An example and a counter-example
directed cycle: A cycle such that all the edges are directed and
are traversed along their direction.
Example and counter-example, depending on how the path is
traversed.
subgraph of a graph G: a graph H whose vertices and edges
are subsets of the vertices and edges of G, respectively.
spanning subgraph of G: A subgraph of G that contains all
the vertices of the graph G.
connected graph: For any two vertices, there is a path between
them.
An example and a counter-example
connected components of G: Its connected subgraphs.
Examples and counter-example
forest: A graph without cycles.
Example and counter-example
tree: A connected forest, that is, a connected graph without
cycles
Example and counter-example
Note:
The trees in graph theory do not have root. They are called free
trees.
Those trees we have learned before are called rooted trees.
spanning tree of a graph: A spanning subgraph that is a tree.
An example
Graph Methods
Recall that in a list or a rooted tree, we access objects by
positions. Vertices and edges in a graph are also positions
defined by its relation with neighbours.
Therefore, a graph is a positional container of elements that are
stored as the graph’s vertices and edges.
Graphs are more complicated and thus have a large number of
methods in its abstract data type.
General Methods
The graph abstract data type supports the following
fundamental methods:
numVertices():
numEdge():
vertices():
edges():
Return the number of vertices in G
Return the number of edges in G
Return an iterator of the vertices of G
Return an iterator of the edges of G
Since a graph does not have a special vertex like a root in a
rooted tree, we have a method that returns an arbitrary vertex
of the graph:
aVertex(): Return a vertex of G
Accessor methods
degree(v):
adjacentVertices(v):
incidentEdges(v):
endVertices(v):
opposite(v,e):
areAdjacent(v,w):
Return the degree of v
Return an iterator of the vertices adjacent to v
Return an iterator of the edges incident upon v
Return an array of size 2 storing the end vertices of e
Return the endpoint of edge e distinct from v
Return whether vertices v and w are adjacent
Methods dealing with directed edges
directedEdges():
undirectedEdges():
destination(e):
origin(e):
isDirected(e):
Return an iterator of all directed edges
Return an iterator of all undirected edges
Return the destination of the directed edge e
Return the origin of the directed edge e
Return true if and only if the edge e is directed
Additional methods dealing with directed edges
inDegree(v):
outDegree(v):
inIncidentEdges(v):
outIncidentEdges(v):
inAdjacentVertices(v):
Return the in-degree of v
Return the out-degree of v
Return an iterator of all the incoming edges to v
Return an iterator of all the outgoing edges from v
Return an iterator of all the vertices adjacent to v
along incoming edges to v
outAdjacentVertices(v): Return an iterator of all the vertices adjacent to v
along outgoing edges from v
Methods for updating graphs
insertEdge(v,w,o): Insert and return an undirected edge between
vertices v and w, storing the object o at this
position
insertDirectedEdge(v,w,o): Insert and return a directed edge from vertex v to
vertex w, storing the object o at this position
insertVertex(o): Insert and return a new (isolated) vertex storing
the object o at this position
removeVertex(v): Remove vertex v and all its incident edges
removeEdge(e): Remove edge e
reverseDirection(e): Reverse the direction of directed edge e
setDirectionFrom(e,v): Make edge e directed away from vertex v
setDirectionTo(e,v): Make edige e directed into vertex v
Data Structure Exercises 20.1
Data Structure for Graphs
A salesman spends his time visiting n cities (or nodes)
cyclically. In one tour he visits each city just once, and finishes
up where he started. In what order should he visit them to
minimize the distance traveled?
How can we represent this problem in a computer program so
we can solve it?
The Edge List Structure
The simplest representation of a graph is the edge list structure.
In this approach, all the vertices are stored in a container V that
can be a list, vector, or dictionary.
On the other hand, all the edges are stored in a container E that
can also be a list, vector, or dictionary.
E
V
Vertex Objects
The vertex object for a vertex v storing element o contains data
fields for
 A reference to o
 Counters for the number of incident undirected edges,
incoming directed edges, and outgoing directed edges
 A reference to the position of the vertex-object in
container V.
Note: The last data field is the rank of the vertex object in the
container V if V is a vector.
c1
c2
element
rank
c3
Edge Objects
The edge object for an edge e storing element o has data fields
for




A reference to o
A Boolean indicator of whether e is directed or not
References to the vertex objects in V associated with the
endpoint vertices of e (if the edge e is undirected) or to
the origin and destination vertices of e (if the edge e is
directed)
A reference to the position of the edge -object in container
E
Note: The last data field is the rank of the edge object in the
container E if E is a vector.
With an edge list, some methods (edge -based) are fast while
others need some efforts.
For example, methods endVertices(), origin(), and destination()
are fast because we can access edges directly.
end vertex
element
1 or 0
end vertex
Method incidentEdges( v ), on the other hand, needs to search
the entire container E to count the number of incident edges for
vertex v.
V container
element
element
element
A simplified example:
We have this flight network.
AC201
AC112
Ottawa
JG120
Vancouver
AC200
Winnipeg
Calgary
JG131
WJ35
WJ75
JG130
Toronto
E
AC112
V
WJ35
Calgary
JG120
Ottawa
WJ75
JG130
Toronto
JG131
AC200
AC201
Vancouver Winnipeg
Now if we want to find out the number of incident edges to the
vertex Toronto, we have to search the entire container V.
Let the graph G has n vertices and m edges. The table here
is a summary of the running time for the methods.
Operation
size, isEmpty, replaceElement, swapElements
numVertices, numEdges, aVertex
vertices
edges, directedEdges, undirectedEdges
elements, positions
endVertices, opposite, origin, destination, isDirected,
degree, inDegree, outDegree
icidentEdges, inIncidentEdges, outIncidentEdges,
adjacentVertices, inAdjacentVertices,
outAdjacentVertices, AreAdjacent
insertVertex, insertEdge, insertDirectedEdge,
removeEdge, makeUndirected, reverseDirection,
setDirectionFrom, setDirectionTo
removeVertex
Time
fast
fast
O(n)
O(m)
O(n+m)
fast
O(m)
fast
O(m)
The Adjacency List Structure
The adjacency list structure for a graph G extends the edge list
structure. Like the edge list structure, the adjacency list
structure has a container V for the vertices and E for the edges.
More data structures and fields are added to vertex objects and
edge objects.

The vertex object v holds a reference to a container I(v),
called the incidence container, that stores references to
the edges incident on v. If directed edges are allowed,
then we partition I(v) into Iin(v), Iout(v), and Iun(v) that
store the in-coming, out-going, and undirected edges
incident to v.

The edge object for an edge (u, v) holds references to the
positions of the edge in the incidence containers I(u) and
I(v).
Example:
AC201
AC112
Ottawa
JG120
Vancouver
AC200
Winnipeg
Calgary
JG131
WJ35
WJ75
JG130
Toronto
E
AC112
V
WJ35
Calgary
in
WJ35
JG120
out
WJ75
JG120
WJ75
JG130
JG131
AC200
AC201
Ottawa
Toronto
Vancouver Winnipeg
in
out
in
out
in
out
AC200
AC201
JG131
AC112
WJ35
JG130
AC200
in
out
WJ75
JG131
AC112
JG120
JG130
AC201
The added data structures improve running time. Here is a
summary.
Operation
size, isEmpty, replaceElement, swapElements
numVertices, numEdges, aVertex
vertices
edges, directedEdges, undirectedEdges
elements, positions
endVertices, opposite, origin, destination,
isDirected, degree, inDegree, outDegree
icidentEdges, inIncidentEdges, outIncidentEdges,
adjacentVertices, inAdjacentVertices,
outAdjacentVertices,
AreAdjacent
insertVertex, insertEdge, insertDirectedEdge,
removeEdge, makeUndirected, reverseDirection,
setDirectionFrom, setDirectionTo
removeVertex
Time
fast
fast
O(n)
O(m)
O(n+m)
fast
O(deg(v))
O(min(deg(v), deg(v) ))
fast
O(deg(v))
The Adjacency Matrix Struture
Here is yet another extension to the edge list approach. We add
a two-dimensional matrix to store information of adjacency.
To use a 2-D matrix, we map vertices to integers. For example,
0
1
2
3
Calgary
Ottawa
Toronto
Vancouver Winnipeg
The adjacency matrix has a size of 5 x 5 = 25.
4
Here is how the information is stored: Assume there are n
vertices in the graph


A vertex v also stores a distinct integer key in the range 0,
1, …, n - 1, called the index of v (or simply “index v”).
In the n x n array A, the cell A[i, j] holds a reference to
the edge object e that goes from the vertex with index i to
the vertex with index j, if such edge exists. If the edge e is
undirected, we store references to e in both A[i, j] and
A[j, i]. If there is no edge from vertex i to vertex j, we
store a null object in both A[i, j] and A[j, i].
Example:
Calgary
Ottawa
Toronto
Vancouver Winnipeg
0
1
2
3
4
0
WJ75
1
AC201
2
AC200
3
WJ35
4
JG120
JG131
JG130
AC112
Running time:
Operation
size, isEmpty, replaceElement, swapElements
numVertices, numEdges, aVertex
vertices
edges, directedEdges, undirectedEdges
elements, positions
endVertices, opposite, origin, destination, isDirected,
degree, inDegree, outDegree
icidentEdges, inIncidentEdges, outIncidentEdges,
adjacentVertices, inAdjacentVertices, outAdjacentVertices,
AreAdjacent
insertEdge, insertDirectedEdge, removeEdge,
makeUndirected, reverseDirection, setDirectionFrom,
setDirectionTo
insertVertex, removeVertex
Time
fast
fast
O(n)
O(m)
O(n+m)
fast
O(n)
fast
fast
O(n2)
Data Structure Exercises 20.2