Transcript Graphs (Breadth-first search, Depth

Chapter 20:
Graphs
CS 302 - Data Structures
Mehmet H Gunes
Modified from authors’ slides
What is a graph?
• A data structure that consists of a set of nodes
(vertices) and a set of edges between the
vertices.
• The set of edges describes relationships
among the vertices.
1
2
3
4
Terminology
• Definition:
– A set of points that are joined by lines
• Graphs also represent the relationships
among data items
• G={V,E}
– a graph is a set of vertices and edges
• A subgraph consists of a subset of a graph’s
vertices and a subset of its edges
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Formally
• a graph G is defined as follows:
G = (V,E)
• where
– V(G) is a finite, nonempty set of vertices
– E(G) is a set of edges
• written as pairs of vertices
An undirected graph
A graph in which the
edges have no direction
The order of vertices in E
is not important for
undirected graphs!!
A directed graph
A graph in which each
edge is directed from
one vertex to another
(or the same) vertex
The order of vertices in E
is important for
directed graphs!!
A directed graph
Trees are special
cases of graphs!
Terminology
• Undirected graphs: edges do not indicate a
direction
• Directed graph, or digraph: each edge has a
direction
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Terminology
• (a) A campus map as a graph;
(b) a subgraph
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Terminology
• Graphs that are (a) connected;
(b) disconnected; and (c) complete
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Terminology
• (a) A multigraph is not a simple graph;
(b) a self edge is not allowed in a simple graph
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Graph terminology
• Path: A sequence of vertices that connects
two nodes in a graph
• The length of a path is the number of edges
in the path.
1
2
e.g., a path from 1 to 4
<1, 2, 3, 4>
3
4
Terminology
• Simple path: passes through vertex only once
• Cycle: a path that begins and ends at same
vertex
• Simple cycle: cycle that does not pass through
other vertices more than once
• Connected graph: each pair of distinct vertices
has a path between them
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Graph terminology
Complete graph: A graph in which every vertex
is directly connected to every other vertex
Terminology
• Complete graph: each pair of distinct vertices
has an edge between them
• Graph cannot have duplicate edges between
vertices
– Multigraph: does allow multiple edges
• When labels represent numeric values, graph
is called a weighted graph
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Graph terminology (cont.)
• What is the number of edges E in a
complete undirected graph with V
vertices?
E=V* (V-1) / 2
or O(V2)
Graph terminology (cont.)
• What is the number of edges E in a
complete directed graph with V vertices?
E=V * (V-1)
or O(V2)
A weighted graph
Weighted graph: A graph in which each edge carries a value
18
Terminology
• (a) a weighted graph; (b) a directed graph
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Graphs as ADTs
ADT graph operations
– Test whether graph is empty.
– Get number of vertices in a graph.
– Get number of edges in a graph.
– See whether edge exists between two given
vertices.
– Insert vertex in graph whose vertices have distinct
values that differ from new vertex’s value.
– Insert edge between two given vertices in graph.
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Graphs as ADTs
ADT graph operations, ctd.
– Remove specified vertex from graph and any
edges between the vertex and other vertices.
– Remove edge between two vertices in graph.
– Retrieve from graph vertex that contains given
value.
• View interface for undirected, connected
graphs, Listing 20-1
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Array-Based Implementation
• Use a 1D array to represent the vertices
• Use a 2D array (i.e., adjacency matrix) to
represent the edges
• Adjacency Matrix:
– for a graph with N nodes,
• an N by N table that shows the existence
(and weights) of all edges in the graph
Adjacency Matrix for Flight Connections
from node x ?
to node x ?
Array-Based Implementation (cont.)
• Memory required
– O(V+V2)=O(V2)
• Preferred when
– The graph is dense: E = O(V2)
• Advantage
– Can quickly determine if there is an edge between two vertices
• Disadvantage
– Consumes significant memory for sparse large graphs
Linked Implementation
• Use a 1D array to represent the vertices
• Use a list for each vertex v which contains the
vertices which are adjacent from v (i.e.,
adjacency list)
• Adjacency List:
– A linked list that identifies all the vertices to
which a particular vertex is connected;
• each vertex has its own adjacency list
Adjacency List Representation of Graphs
from node x ?
to node x ?
Link-List-based Implementation (cont.)
• Memory required
– O(V + E)
O(V) for sparse graphs since E=O(V)
O(V2) for dense graphs since E=O(V2)
• Preferred when
– for sparse graphs: E = O(V)
• Disadvantage
– No quick way to determine the
vertices adjacent to a given vertex
• Advantage
– Can quickly determine the vertices adjacent from a given vertex
Implementing Graphs
• (a) A directed graph and
(b) its adjacency matrix
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Implementing Graphs
• (a) A weighted undirected graph and
(b) its adjacency matrix
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Implementing Graphs
• (a) A directed graph and
(b) its adjacency list
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Implementing Graphs
• (a) A weighted undirected graph and
(b) its adjacency list
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Graph Traversals
• Visits all of the vertices that it can reach
– Happens if graph is connected
• Connected component is subset of vertices
visited during traversal that begins at given
vertex
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Graph searching
• Problem: find if there is a path between
two vertices of the graph
– e.g., Austin and Washington
• Methods: Depth-First-Search (DFS) or
Breadth-First-Search (BFS)
Depth-First-Search (DFS)
• Main idea:
– Travel as far as you can down a path
– Back up as little as possible when you reach a
"dead end“
• i.e., next vertex has been "marked" or there is no next
vertex
startVertex
endVertex
Depth First Search: Follow Down
3
2
1
DFS uses Stack !
startVertex
(initialization)
endVertex
36
37
endVertex
38
Depth-First Search
• Goes as far as possible from a vertex before backing
up
• Recursive algorithm
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Depth-First Search
• Iterative algorithm, using a stack
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Depth-First Search
• Iterative algorithm, using a stack, ctd.
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Depth-First Search
• Visitation order for (a) a depth-first search;
(b) a breadth-first search
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Depth-First Search
• A connected graph with cycles
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Depth-First Search
• The results of a depth-first traversal,
beginning at vertex a, of the graph
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Breadth-First-Searching (BFS)
• Main idea:
– Look at all possible paths at the same depth
before you go at a deeper level
– Back up as far as possible when you reach a
"dead end“
• i.e., next vertex has been "marked" or there is no next
vertex
startVertex
endVertex
Breadth First: Follow Across
1
4
3
8
7
6
2
BFS uses Queue !
5
Breadth First Uses Queue
startVertex
endVertex
(initialization)
48
49
50
Breadth-First Search
• Visits all vertices adjacent to vertex before
going forward
• Breadth-first search uses a queue
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Breadth-First Search
• The results of a breadth-fi rst traversal,
beginning at vertex a, of the graph
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Applications of Graphs
• A directed graph without cycles
• Topological Sorting
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Applications of Graphs
• The graph arranged according to the
topological orders (a) a, g, d, b, e, c, f and
(b) a, b, g, d, e, f, c
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Applications of Graphs
• Topological sorting algorithm
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Applications of Graphs
• A trace of topSort1 for the graph
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Applications of Graphs
• A trace of topSort1 for the graph
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Applications of Graphs
• A trace of topSort1 for the graph
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Applications of Graphs
• A trace of topSort1 for the graph
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Applications of Graphs
• A trace of topSort2 for the graph
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Spanning Trees
• Tree: an undirected connected graph without
cycles
• Observations about undirected graphs
1. Connected undirected graph with n vertices
must have at least n – 1 edges.
2. Connected undirected graph with n vertices and
exactly n – 1 edges cannot contain a cycle
3. A connected undirected graph with n vertices
and more than n – 1 edges must contain at least
one cycle
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Spanning Trees
• The DFS spanning tree rooted at vertex a for
the graph
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Spanning Trees
• DFS spanning tree algorithm
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Spanning Trees
• BFS spanning
tree algorithm
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Spanning Trees
• The BFS spanning tree rooted at vertex a for
the graph
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Minimum Spanning Trees
• A weighted, connected, undirected graph
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Minimum Spanning Trees
• Minimum spanning tree algorithm
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Minimum Spanning Trees
• A trace of primsAlgorithm for the graph,
beginning at vertex a
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Minimum Spanning Trees
• A trace of primsAlgorithm for the graph,
beginning at vertex a
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Minimum Spanning Trees
• A trace of primsAlgorithm for the graph,
beginning at vertex a
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Graph Algorithms
• Depth-first search
– Visit all the nodes in a branch to its deepest point
before moving up
• Breadth-first search
– Visit all the nodes on one level before going to the next
level
• Single-source shortest-path
– Determines the shortest path from a designated
starting node to every other node in the graph
71
Single Source Shortest Path
72
Single Source Shortest Path
• What does “shortest” mean?
• What data structure should you use?
73
Shortest-path problem
• There might be multiple paths from a source
vertex to a destination vertex
• Shortest path: the path whose total weight
(i.e., sum of edge weights) is minimum
AustinHoustonAtlantaWashington:
1560 miles
AustinDallasDenverAtlantaWashington:
2980 miles
74
Variants of Shortest Path
• Single-pair shortest path
– Find a shortest path from u to v
• for given vertices u and v
• Single-source shortest paths
– G = (V, E)  find a shortest path from a given source
vertex s to each vertex v  V
75
Variants of Shortest Paths (cont’d)
• Single-destination shortest paths
– Find a shortest path to a given destination vertex t
from each vertex v
– Reversing the direction of each edge  single-source
• All-pairs shortest paths
– Find a shortest path from u to v for every pair of
vertices u and v
76
Shortest Paths
• Shortest path between two vertices in a
weighted graph has smallest edge-weight sum
(a) A weighted directed graph
and (b) its adjacency matrix
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Notation
t
3
• Weight of path p = v0, v1, . . . , vk
k
w( p )   w(vi 1 , vi )
i 1
x
9
6
3
s 0
1
2
4
2
7
3
5
5
y
6
11
z
• Shortest-path weight from s to v:
δ(v) =
min w(p) : s
∞
p
v if there exists a path from s to v
otherwise
78
Negative Weights and Negative Cycles
a
3
• Negative-weight edges may
form negative-weight cycles.
s
0
-4
b
4
c
d
6
5
g
8
-3
2
7
3
e
-6
f
• If negative cycles are reachable from the source, the shortest
path is not well defined.
– i.e., keep going around the cycle, and get
w(s, v) = -  for all v on the cycle
79
Could shortest path solutions contain cycles?
• Negative-weight cycles
– Shortest path is not well defined
• Positive-weight cycles:
– By removing the cycle, we can get a shorter path
• Zero-weight cycles
– No reason to use them; can remove them to obtain a
path with same weight
80
Shortest-path algorithms
• Solving the shortest path problem in a brute-force
manner requires enumerating all possible paths.
– There are O(V!) paths between a pair of vertices in an
acyclic graph containing V nodes.
• We will discuss two algorithms
– Dijkstra’s algorithm
– Bellman-Ford’s algorithm
81
Shortest-path algorithms
• Dijkstra’s and Bellman-Ford’s algorithms are
“greedy” algorithms!
– Find a “globally” optimal solution by making “locally”
optimum decisions.
• Dijkstra’s algorithm
– Does not handle negative weights.
• Bellman-Ford’s algorithm
– Handles negative weights but not negative cycles
reachable from the source.
82
Shortest-path algorithms (cont’d)
• Both Dijkstra’s and Bellman-Ford’s
algorithms are iterative:
– Start with a shortest path estimate for every
vertex: d[v]
– Estimates are updated iteratively until
convergence:
d[v]δ(v)
83
Shortest-path algorithms (cont’d)
• Two common steps:
(1) Initialization
(2) Relaxation (i.e., update step)
84
Initialization Step
• Set d[s]=0
– i.e., source vertex
• Set d[v]=∞ for v  s
– i.e., large value
t

-2
6
8
s 0

-3
7
-4
2
7

85
x
5
9

Relaxation Step
Relaxing an edge (u, v) implies testing whether we can
improve the shortest path to v found so far by going through u:
If d[v] > d[u] + w(u, v)
we can improve the shortest path to v
 d[v]=d[u]+w(u,v)
s
s
u
5
2
v
u
9
5
2
RELAX(u, v, w)
u
5
86
2
v
7
v
6
RELAX(u, v, w)
u
5
2
v
6
no change
Bellman-Ford Algorithm
• Can handle negative weights.
• Detects negative cycles reachable from the source.
• Returns FALSE if negative-weight cycles are reachable
from the source s  no solution
87
Bellman-Ford Algorithm (cont’d)
• Each edge is relaxed |V–1| times by making |V-1|
passes over the whole edge set
– to make sure that each edge is relaxed exactly |V – 1| times
• it puts the edges in an unordered list and goes over
the list |V – 1| times
(t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y)
t
x
5

-2
6
s
8
0
-3
7
-4
2
7

y
88

9

z
Example
t

-2
6
s
5
8
0
x
t


6
7
-4
2
7

y
9
-2
6
-3
Pass 1
8
s 0

-3
7
-4
2
7

z
x
5

7
y
9

z
E: (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y)
89
Example
t
Pass 1
6
(from
6
previous
8
slide) s 0
(t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y)
x
t
x
5
Pass 2

4
6

11
5
-2
7
-4
9

z
t
5
x
-2
6
8
2
9
-4
2
Pass 4
5
-2
s
8
0
4

11
-3
7
-4
2
7
2

z
2

z
x
9
62
6
-4
7
y
7
7
y
t
-3
7
7
90
0
4

11
62
-3
8
7
7
y
Pass 3
s 0
s
2
7
-2
6
-3
7
y
9
2

-2
z
Detecting Negative Cycles: needs an extra iteration
s
for each edge (u, v)  E do
if d[v] > d[u] + w(u, v)
then return FALSE
return TRUE
0-3
-8
2

5
b
s

2
-6
-3
3
-8
2

3

c
Consider edge (s, b):
b
2
2-1
3
d[b] = -1
d[s] + w(s, b) = -4
52
c
c
(s,b) (b,c) (c,s)
91
-8
2nd pass
1st pass
s
0
b
d[b] > d[s] + w(s, b)
 d[b]=-4
(d[b] keeps changing!)
BELLMAN-FORD Algorithm
1.
2.
3.
4.
5.
6.
7.
8.
92
INITIALIZE-SINGLE-SOURCE(V, s)
for i ← 1 to |V| - 1
for each edge (u, v)  E
RELAX(u, v, w)
for each edge (u, v)  E
if d[v] > d[u] + w(u, v)
return FALSE
return TRUE
Time: O(V+VE+E)=O(VE)
O(V)
O(V)
O(VE)
O(E)
O(E)
Dijkstra’s Algorithm
• Cannot handle negative-weights!
– w(u, v) > 0,  (u, v)  E
• Each edge is relaxed only once!
93
Dijkstra’s Algorithm (cont’d)
• At each iteration, it maintains two sets of vertices:
V
S
d[v]=δ (v)
estimates have converged
to the shortest path solution
V-S
d[v]≥δ (v)
estimates have not
converged yet
Initially, S is empty
94
Dijkstra’s Algorithm (cont.)
• Vertices in V–S reside in a min-priority queue Q
– Priority of u determined by d[u]
– The “highest” priority vertex will be the one having the
smallest d[u] value.
95
Dijkstra (G, w, s)
Q=<y,t,x,z>
S=<s>
S=<> Q=<s,t,x,z,y>
Initialization
t
1

2
0

10

6
7

y
2
s
4
3
6
7
5

z

9
2
0
x
1
10
4
3
5
96
t
9
10
s
x

5
y
2

z
Example (cont.)
S=<s,y> Q=<z,t,x>
t
8
10
1
s
2
0
t
14

8
6
7
5
y
2
13
14
9
2
s 0
4
3
6
7
5
7

z
x
1
10
4
3
5
97
x
9
10
Q=<t,x>
S=<s,y,z>
5
y
2
7
z
Example (cont.)
S=<s,y,z,t,x> Q=<>
S=<s,y,z,t> Q=<x>
t
1
8
t
13
9
8
2
4
3
6
5
y
2
7
z
9
9
2
0
4
3
6
7
5
7
5
s
x
1
10
9
10
s 0
x
5
y
2
7
z
Note: use back-pointers to recover the shortest path solutions!
98
Dijkstra (G, w, s)
INITIALIZE-SINGLE-SOURCE(V, s)
S← 
 O(V)
build priority heap
Q ← V[G]
 O(V logV)
while Q  
 O(V) times
u ← EXTRACT-MIN(Q)
 O(logV)
S ← S  {u}
for each vertex v  Adj[u]
 O(Evi)
O(Evi logV)
RELAX(u, v, w)
Update Q (DECREASE_KEY)
 O(logV)
Overall: O(V+2VlogV+(Ev1+Ev2+...)logV) =O(VlogV+ElogV)=O(ElogV)
99
Improving Dijkstra’s efficiency
• Suppose the shortest path from s to w is the
following:
s
x
…
u
w
…
• If u is the i-th vertex in this path, it can be shown
that d[u]  δ (u) at the i-th iteration:
– move u from V-S to S
– d[u] never changes again
100
Add a flag for efficiency!
INITIALIZE-SINGLE-SOURCE(V, s)
S← 
Q ← V[G]
while Q  
u ← EXTRACT-MIN(Q)
S ← S  {u};
 mark u
for each vertex v  Adj[u]
If v not marked
RELAX(u, v, w)
Update Q (DECREASE_KEY)
101
Dijkstra vs Bellman-Ford
• Bellman-Ford
O(VE)
• Dijkstra
O(ElogV)
V2
if G is sparse: E=O(V)
V3
if G is dense: E=O(V2)
VlogV
V2logV
102
if G is sparse: E=O(V)
if G is dense: E=O(V2)
Shortest Paths
• Dijkstra’s shortest-path algorithm
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Shortest Paths
• Dijkstra’s shortest-path algorithm, ctd.
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Shortest Paths
• A trace of the shortest-path algorithm
applied to the graph
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Shortest Paths
• Checking weight [u] by examining the graph:
(a) weight [2] in step 2; (b) weight [1] in step 3;
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Shortest Paths
• Checking weight [u] by examining the graph:
(c) weight [3] in step 3; (d) weight [3] in step 4
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Revisiting BFS
• BFS can be used to solve the shortest path
problem when the graph is weightless or
when all the weights are equal.
– Path with lowest number of edges
• i.e., connections
• Need to “mark” vertices before Enqueue!
– i.e., do not allow duplicates
108
Circuits
• Another name for a type of cycle common in
statement of certain problems
• Circuits either visit every vertex once or visit
every edge once
• An Euler circuit begins at a vertex v, passes
through every edge exactly once, and
terminates at v
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Circuits
• (a) Euler’s bridge problem and
(b) its multigraph representation
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Circuits
• Pencil and paper drawings
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Circuits
• Connected undirected graphs based on the
drawings
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Circuits
• The steps to determine an Euler circuit for
the graph
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Circuits
• The steps to determine an Euler circuit for
the graph
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Some Difficult Problems
• Hamilton circuit
– Path that begins at a vertex v, passes through
every vertex in the graph exactly once, and
terminates at v
• The traveling salesperson problem
– Variation of Hamilton circuit
– Involves a weighted graph that represents a road
map
– Circuit traveled must be the least expensive
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Some Difficult Problems
• The three utilities problem
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Some Difficult Problems
• Planar graph
– Can draw it in a plane in at least one way so that
no two edges cross
• The four-color problem
– Given a planar graph, can you color the vertices so
that no adjacent vertices have the same color, if
you use at most four colors?
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Some Difficult Problems
1. Describe the graphs in Figure 20-32 . For
example, are they directed? Connected?
Complete? Weighted?
2. Use the depth-first strategy and the breadthfirst strategy to traverse the graph in Figure
20-32 a, beginning with vertex 0. List the
vertices in the order in which each traversal
visits them.
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Some Difficult Problems
3. Write the adjacency matrix for the graph in
Figure 20-32 a.
4. Add an edge to the directed graph in Figure
20-14 that runs from vertex d to vertex b.
Write all possible topological orders for the
vertices in this new graph.
5. Is it possible for a connected undirected
graph with fi ve vertices and four edges to
contain a simple cycle? Explain.
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Some Difficult Problems
6. Draw the DFS spanning tree whose root is
vertex 0 for the graph in Figure 20-33 .
7. Draw the minimum spanning tree whose root
is vertex 0 for the graph in Figure 20-33 .
8. What are the shortest paths from vertex 0 to
each vertex of the graph in Figure
20-24 a? (Note the weights of these paths in
Figure 20-25 .)
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Some Difficult Problems
• FIGURE 20-32 Graphs for Checkpoint
Questions 1, 2, and 3
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Some Difficult Problems
• FIGURE 20-33 A graph for Checkpoint
Questions 6 and 7 and for Exercises 1 and 4
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013