Data Structures Using C++ 2E
Chapter 12 Graphs
Objectives
Learn about graphs Become familiar with the basic terminology of graph theory Discover how to represent graphs in computer memory Examine and implement various graph traversal algorithms
Data Structures Using C++ 2E
Objectives (contd.)
Learn how to implement a shortest path algorithm Examine and implement the minimum spanning tree algorithm Explore topological sort Learn how to find Euler circuits in a graph
Data Structures Using C++ 2E
Introduction
Knigsberg bridge problem
Given: river has four land areas
A, B, C, D
Given: land areas connected using seven bridges
a, b, c, d, e, f, g
Starting at one land area
Is it possible to walk across all the bridges exactly once and return to the starting land area?
Euler represented problem as a graph
Answered question in the negative Marked birth of graph theory
Data Structures Using C++ 2E 4
Introduction (contd.)
FIGURE 12-1 The Knigsberg bridge problem
FIGURE 12-2 Graph representation of the Knigsberg bridge problem
Data Structures Using C++ 2E 5
Graph Definitions and Notations
Borrow definitions, terminology from set theory Subset
Set Y is a subset of X: Y X
If every element of Y is also an element of X
Intersection of sets A and B: A B
Set of all elements that are in A and B
Union of sets A and B: A U B
Set of all elements in A or in B
Cartesian product: A x B
Set of all ordered pairs of elements of A and B
Data Structures Using C++ 2E 6
Graph Definitions and Notations (contd.)
Graph G pair
G = (V, E), where V is a finite nonempty set
Called the set of vertices of G, and E V x V
Elements of E
Pairs of elements of V
E: set of edges of G
G called trivial if it has only one vertex
Directed graph (digraph)
Elements in set of edges of graph G: ordered
Undirected graph: not ordered
Data Structures Using C++ 2E 7
FIGURE 12-3 Various undirected graphs
FIGURE 12-4 Various directed graphs
Data Structures Using C++ 2E
Graph Definitions and Notations (contd.)
Graph H called subgraph of G
If V(H) V(G) and E(H) E(G) Every vertex of H: vertex of G Every edge in H: edge in G
Graph shown pictorially
Vertices drawn as circles
Label inside circle represents vertex
Undirected graph: edges drawn using lines Directed graph: edges drawn using arrows
Data Structures Using C++ 2E 9
Graph Definitions and Notations (contd.)
Let u and v be two vertices in G
u and v adjacent
If edge from one to the other exists: (u, v) E
Loop
Edge incident on a single vertex
e1 and e2 called parallel edges
If two edges e1 and e2 associate with same pair of vertices {u, v}
Simple graph
No loops, no parallel edges
Data Structures Using C++ 2E 10
Graph Definitions and Notations (contd.)
Let e = (u, v) be an edge in G
Edge e is incident on the vertices u and v Degree of u written deg(u) or d(u)
Number of edges incident with u
Each loop on vertex u
Contributes two to the degree of u
u is called an even (odd) degree vertex
If the degree of u is even (odd)
Data Structures Using C++ 2E
11
Graph Definitions and Notations (contd.)
Path from u to v
If sequence of vertices u1, u2, . . ., un exists
Such that u = u1, un = v and (ui, ui+ 1) is an edge for all i =1, 2, . . ., n 1
Vertices u and v called connected
If path from u to v exists
Simple path
All vertices distinct (except possibly first, last)
Cycle in G
Simple path in which first and last vertices are the same Data Structures Using C++ 2E
12
Graph Definitions and Notations (contd.)
G is connected
If path from any vertex to any other vertex exists
Component of G
Maximal subset of connected vertices
Let G be a directed graph and let u and v be two vertices in G
If edge from u to v exists: (u, v) E
u is adjacent to v v is adjacent from u
Data Structures Using C++ 2E
13
Graph Definitions and Notations (contd.)
Definitions of paths and cycles in G
Similar to those for undirected graphs
G is strongly connected
If any two vertices in G are connected
Data Structures Using C++ 2E
14
Graph Representation
Graphs represented in computer memory
Two common ways
Adjacency matrices Adjacency lists
Data Structures Using C++ 2E
15
Adjacency Matrices
Let G be a graph with n vertices where n > zero Let V(G) = {v1, v2, ..., vn}
Adjacency matrix
Data Structures Using C++ 2E
16
Adjacency Lists
Given:
Graph G with n vertices, where n > zero V(G) = {v1, v2, ..., vn}
For each vertex v: linked list exists
Linked list node contains vertex u: (v, u) E(G)
Use array A, of size n, such that A[i]
Reference variable pointing to first linked list node containing vertices to which vi adjacent
Each node has two components: vertex, link
Component vertex
Contains index of vertex adjacent to vertex i
Data Structures Using C++ 2E 17
Adjacency Lists (contd.)
Example 12-4
FIGURE 12-5 Adjacency list of graph G2 of Figure 12-4
FIGURE 12-6 Adjacency list of graph G3 of Figure 12-4
Data Structures Using C++ 2E
18
Operations on Graphs
Commonly performed operations
Create graph
Store graph in computer memory using a particular graph representation
Clear graph
Makes graph empty
Determine if graph is empty Traverse graph Print graph
Data Structures Using C++ 2E
19
Operations on Graphs (contd.)
Graph representation in computer memory
Depends on specific application
Use linked list representation of graphs
For each vertex v
Vertices adjacent to v (directed graph: called immediate successors) Stored in the linked list associated with v
Managing data in a linked list
Use class unorderedLinkedList
Labeling graph vertices
Depends on specific application
Data Structures Using C++ 2E 20
Graphs as ADTs
See code on pages 692-693
Defines a graph as an ADT Class specifying basic operations to implement a graph
Definitions of the functions of the class graphType
Data Structures Using C++ 2E
21
Graphs as ADTs (contd.)
Function createGraph
Implementation
Depends on how data input into the program
See code on page 694
Function clearGraph
Empties the graph
Deallocates storage occupied by each linked list Sets number of vertices to zero
See code on page 695
Data Structures Using C++ 2E
22
Graph Traversals
Processing a graph
Requires ability to traverse the graph
Traversing a graph
Similar to traversing a binary tree
A bit more complicated
Two most common graph traversal algorithms
Depth first traversal Breadth first traversal
Data Structures Using C++ 2E
23
Depth First Traversal
Similar to binary tree preorder traversal General algorithm
FIGURE 12-7 Directed graph G3
Data Structures Using C++ 2E 24
Depth First Traversal (contd.)
General algorithm for depth first traversal at a given node v
Recursive algorithm
Data Structures Using C++ 2E
25
Depth First Traversal (contd.)
Function dft implements algorithm
Data Structures Using C++ 2E
26
Depth First Traversal (contd.)
Function depthFirstTraversal
Implements depth first traversal of the graph
Data Structures Using C++ 2E
27
Depth First Traversal (contd.)
Function depthFirstTraversal
Performs a depth first traversal of entire graph
Function dftAtVertex
Performs a depth first traversal at a given vertex
Data Structures Using C++ 2E
28
Breadth First Traversal
Similar to traversing binary tree level-by-level
Nodes at each level
Visited from left to right
All nodes at any level i
Visited before visiting nodes at level i + one
Data Structures Using C++ 2E
29
Breadth First Traversal (contd.)
General search algorithm
Breadth first search algorithm with a queue
Data Structures Using C++ 2E
30
Data Structures Using C++ 2E
31
Shortest Path Algorithm
Weight of the graph
Nonnegative real number assigned to the edges connecting to vertices
Weighted graphs
When a graph uses the weight to represent the distance between two places
Weight of the path P
Given G as a weighted graph with vertices u and v in G and P as a path in G from u to v
Sum of the weights of all the edges on the path
Shortest path: path with the smallest weight
Data Structures Using C++ 2E 32
Shortest Path Algorithm (contd.)
Shortest path algorithm space (greedy algorithm) See code on page 700
class weightedGraphType
Extend definition of class graphType Adds function createWeightedGraph to create graph and weight matrix associated with the graph
Data Structures Using C++ 2E
33
Shortest Path
General algorithm
Initialize array smallestWeight
smallestWeight[u] = weights[vertex, u]
Set smallestWeight[vertex] = zero Find vertex v closest to vertex where shortest path is not determined Mark v as the (next) vertex for which the smallest weight is found
Data Structures Using C++ 2E
34
Shortest Path (contd.)
General algorithm (contd.)
For each vertex w in G, such that the shortest path from vertex to w has not been determined and an edge (v, w) exists
If weight of the path to w via v smaller than its current weight Update weight of w to the weight of v + weight of edge (v, w)
Data Structures Using C++ 2E
35
Shortest Path (contd.)
FIGURE 12-8 Weighted graph G
FIGURE 12-9 Graph after Steps 1 and 2 execute
Data Structures Using C++ 2E 36
Shortest Path (contd.)
FIGURE 12-10 Graph after the first iteration of Steps 3 to 5
FIGURE 12-11 Graph after the second iteration of Steps 3 to 5
Data Structures Using C++ 2E 37
Shortest Path (contd.)
FIGURE 12-12 Graph after the third iteration of Steps 3 to 5
FIGURE 12-13 Graph after the fourth iteration of Steps 3 through 5
Data Structures Using C++ 2E 38
Shortest Path (contd.)
See code on pages 704-705
C++ function shortestPath implements previous algorithm
Records only the weight of the shortest path from the source to a vertex
Review the definitions of the function printShortestDistance and the constructor and destructor on pages 705-706
Data Structures Using C++ 2E
39
Minimum Spanning Tree
Airline connections of a company
Between seven cities
FIGURE 12-14 Airline connections between cities and the cost factor of maintaining the connections
Data Structures Using C++ 2E 40
Minimum Spanning Tree (contd.)
Due to financial hardship
Company must shut down maximum number of connections
Still be able to fly (maybe not directly) from one city to another
FIGURE 12-15 Possible solutions to the graph of Figure 12-14
Data Structures Using C++ 2E 41
Minimum Spanning Tree (contd.)
Free tree T
Simple graph If u and v are two vertices in T
Unique path from u to v exists
Rooted tree
Tree with particular vertex designated as a root
Data Structures Using C++ 2E
42
Minimum Spanning Tree (contd.)
Weighted tree T
Weight assigned to edges in T Weight denoted by W(T): sum of weights of all the edges in T
Spanning tree T of graph G
T is a subgraph of G such that V(T) = V(G)
Data Structures Using C++ 2E
43
Minimum Spanning Tree (contd.)
Theorem 12-1
A graph G has a spanning tree if and only if G is connected From this theorem, it follows that to determine a spanning tree of a graph
Graph must be connected
Minimum (minimal) spanning tree of G
Spanning tree with the minimum weight
Data Structures Using C++ 2E
44
Minimum Spanning Tree (contd.)
Two well-known algorithms for finding a minimum spanning tree of a graph
Prims algorithm
Builds the tree iteratively by adding edges until a minimum spanning tree obtained
Kruskals algorithm
Data Structures Using C++ 2E
45
Minimum Spanning Tree (contd.)
General form of Prims algorithm
FIGURE 12-16 Weighted graph G
Data Structures Using C++ 2E
46
Minimum Spanning Tree (contd.)
See code on page 710
class msTreeType defines spanning tree as an ADT
See code on page 712
C++ function minimumSpanning implementing Prims algorithm Prims algorithm given in this section: O(n3)
Possible to design Prims algorithm order O(n2)
See function printTreeAndWeight code See constructor and destructor code
Data Structures Using C++ 2E 47
FIGURE 12-17 Graph G, V(T), E(T), and N after Steps 1 and 2 execute
Data Structures Using C++ 2E 48
Topological Order
Topological ordering of V(G)
Linear ordering vi1, vi2, . . ., vin of the vertices such that
If vij is a predecessor of vik, j k, 1 j n, 1 k n Then vij precedes vik, that is, j < k in this linear ordering
Algorithm topological order
Outputs directed graph vertices in topological order Assume graph has no cycles
There exists a vertex v in G such that v has no successor There exists a vertex u in G such that u has no predecessor
Data Structures Using C++ 2E 49
Topological Order (contd.)
Topological sort algorithm
Implemented with the depth first traversal or the breadth first traversal
Extend class graphType definition (using inheritance)
Implement breadth first topological ordering algorithm
Called class topologicalOrderType
See code on pages 714-715
Illustrating class including functions to implement the topological ordering algorithm
Data Structures Using C++ 2E 50
Breadth First Topological Ordering
General algorithm
Data Structures Using C++ 2E
51
Breadth First Topological Ordering (contd.)
Breadth First Topological order
0 9 1 7 2 5 4 6 3 8 10
FIGURE 12-18 Arrays predCount, topologicalOrder, and queue after Steps 1 and 2 execute
Data Structures Using C++ 2E
FIGURE 12-19 Arrays predCount, topologicalOrder, and queue after the first iteration of Step 3
52
FIGURE 12-20 Arrays predCount, topologicalOrder, and queue after the second iteration of Step 3
FIGURE 12-21 Arrays predCount, topologicalOrder, and queue after the third iteration of Step 3
Data Structures Using C++ 2E 53
Breadth First Topological Ordering (contd.)
See code on pages 718-719
Function implementing breadth first topological ordering algorithm
FIGURE 12-22 Arrays predCount, topologicalOrder, and queue after Step 3 executes
Data Structures Using C++ 2E
54
Euler Circuits
Eulers solution to Knigsberg bridge problem
Reduces problem to finding circuit in the graph
Circuit
Path of nonzero length
From a vertex u to u with no repeated edges
Euler circuit
Circuit in a graph including all the edges of the graph
Eulerian graph G
If either G is a trivial graph or G has an Euler circuit
Data Structures Using C++ 2E 55
Euler Circuits (contd.)
Graph of Figure 12-24: Euler circuit
FIGURE 12-23 A graph with all vertices of odd degree
FIGURE 12-24 A graph with all vertices of even degree
Data Structures Using C++ 2E 56
Euler Circuits (contd.)
Theorem 12-2
If a connected graph G is Eulerian, then every vertex of G has even degree
Theorem 12-3
Let G be a connected graph such that every vertex of G is of even degree; then, G has an Euler circuit
FIGURE 12-25 Graph of the Knigsberg bridge problem with two additional bridges
Data Structures Using C++ 2E 57
Euler Circuits (contd.)
Fleurys Algorithm
Data Structures Using C++ 2E
58
Euler Circuits (contd.)
Fleurys Algorithm (contd.)
FIGURE 12-26 A graph with all vertices of even degree
Data Structures Using C++ 2E
59
Summary
Many types of graphs
Directed, undirected, subgraph, weighted
Graph theory borrows set theory notation Graph representation in memory
Adjacency matrices, adjacency lists
Graph traversal
Depth first, breadth first
Shortest path algorithm Prims algorithm Euler circuit
Data Structures Using C++ 2E 60
