Data Structures Using C++ 2E

Chapter 12
Graphs
Jordan University of Science and Technology
 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

2
 Graph Definitions and Notations
• 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
3
V(G4)={1,2,3,4,5}

E(G4)={(1,2),(1,3) G4
,(1,4),(2,5), (3,4), (3,5)}

FIGURE 12-3 Various undirected graphs

FIGURE 12-4 Various directed graphs

4
 Graph Definitions and Notations
• 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

5
 Undirected Graph Definitions and Notations
• Let u and v be two vertices in the undirected graph G
– u and v adjacent
• If edge from one to the other exists: (u, v)  E
– A and B are adjacent
A B C
• Loop
– Edge incident on a single vertex
• e1 and e2 called parallel edges D

– edges e1 and e2 associate with same pair of vertices {u, v}

A B C
• Simple graph
– No loops, no parallel edges
D

6
Undirected Graph Definitions and Notations

• 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 A B C
• Each loop on vertex u
– Contributes two to the degree of u
D
• Deg(C) = 3, Deg(D)=2
• u is called an even (odd) degree vertex
– If the degree of u is even (odd)
• A is an odd degree vertex; B is an even degree vertex.
7
 Undirected Graph Definitions and Notations
A B C

• Path from u to v Connected graph

– If sequence of vertices u1, u2, . . ., un exists D
• 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, otherwise, it is called disconnected
– If path from u to v exists
• Simple path
– All vertices distinct (except possibly first, last)
– A-B-C-D, C-D-C are simple paths, A-B-C-D-C-B is not
– A-B-C-D-C? not a simple path
• Cycle in G
– Simple path in which first and last vertices are the same
– C-D-C, and 5-4-3-6-5 are Cycles
• G are connected if there is a path from any
vertex to any other vertex, otherwise it is called
disconnected. Disconnected graph
8
 Directed Graph Definitions and Notations

• Definitions of paths and cycles in G A B C

– Similar to those for undirected graphs

D
• 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
• There is a path from A to D but not from D to A
• B-C-D-B is a cycle

9
 directed Graph Definitions and
Notations
• G is strongly connected, or simply strong, if it contains a directed path
from u to v and a directed path from v to u for every pair of vertices u, v.
• G is weakly connected if replacing all of its directed edges with undirected
edges produces a connected (undirected) graph

A B C A B C

Strongly connected Weakley connected

D D

• 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
» A adjacent to B and B adjacent from A

10
 Graph Representation
• Graphs represented in computer memory
– Two common ways
• Adjacency matrices
• Adjacency lists

11
 Adjacency Matrices
• Let G be a graph with n vertices where n > 0
• Let V(G) = {v1, v2, ..., vn}
– Adjacency matrix

12
Adjacency Matrices: Undirected Graphs

Symmetric Adjacency matrix

13
 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
14
 Adjacency Lists (cont’d.)

FIGURE 12-4 Various directed graphs

Adjacency list of graph G2 Adjacency list of graph G3

15
 Adjacency Lists: Undirected Graphs

Adjacency list of graph G2

16
 Graph Traversals
• Similar to traversing a binary tree
• A bit more complicated
• A Graph could have cycles
• Not necessarily be able to traverse the entire graph
from a single vertex (E.g., not connected graph ).
• Must keep track of the vertices that have been visited.

• Two most common graph traversal algorithms

– Depth first traversal
– Breadth first traversal

17
 Depth First Traversal
• Similar to binary tree preorder traversal
• General algorithm:

A B
A C F
C D E A D H

B D E E G F

F
H G

A C E F G D B H

18
 Depth First Traversal (cont’d.)
• General algorithm for depth first traversal at a given
node v
– Recursive algorithm

Data Structures Using C++ 2E 19

 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

A B
A C F

C D E A D H

B D E E G F

H G F

A C D E G F B H
20
 Breadth First Traversal in Queue way

A C F

B D E
A C D E G F B H
G
H

A C D E G F B H

21
 Breadth First Traversal (cont’d.)
• General search algorithm
– Breadth first search algorithm with a queue
A C F

B D E

G
H

A C D E G F B H

22
 Shortest Path (greedy 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 23

 Shortest Path Algorithm (cont’d.)
• 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 24

 Shortest Path
• General algorithm
– Initialize array smallestWeight
smallestWeight[u] = weights[vertex, u]
– Set smallestWeight[vertex] = 0
– 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 25

 Shortest Path (cont’d.)
• General algorithm (cont’d.)
– 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)
• weightFound : keeps track of the vertices for which
the smallest weight from the source vertex has been
found.
Data Structures Using C++ 2E 26
 Shortest Path (cont’d.)

FIGURE 12-8 Weighted graph G

FIGURE 12-9 Graph after Steps 1 and 2 execute

Data Structures Using C++ 2E 27

 Shortest Path (cont’d.)

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 28

 Shortest Path (cont’d.)

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 29
 Example
A
2 5  Depth First
3 ABCDE
E 6
B  Breadth First
10 5 ABCED
1
4 2  Shortest Path

D C
2
 20
A C F  Depth First
10 ABDFCGE
8
12 20 4  Breadth First
5 D 3 E ABCDEGF
B 5
 Shortest Path
G

31