Edited with the trial version of

Foxit Advanced PDF Editor

To remove this notice, visit:
www.foxitsoftware.com/shopping

Graphs

CSC-114 Data Structure and Algorithms

slides credit: Ms. Saba Anwar, CIIT Lahore

 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Outline www.foxitsoftware.com/shopping

 Non-Linear Data Structures

 Graphs
 Intro
 Application
 Terminologies
 Representation
 Adjacency List
 Adjacency Matrix

2
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Graph www.foxitsoftware.com/shopping

 A graph is a way of representing relationships between pairs of objects.

 It is a set of objects, called vertices, together with a collection of pairwise
connections between them, called edges

3
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Graph www.foxitsoftware.com/shopping

 Graph is a mathematical structure that is defined as G= (v, e), where v is a set

of vertices{v1, v2, …vn} and e is a set of edges {e1,e2,e3,…em}
 Where edge e is an ordered pair of two vertices, represents a connection between two vertices
 Graph can be directed, or undirected
 Example:
 V = {A, B, C, D, E, F, G}
 E = { {A, B}, {A, D}, {A, E}, {B, C}, {B, D}, {B, E}, {C, E}, {C, F}, {D, E} }
 Then the graph G=(V,E) is:
B B
 |V|= 7 A A
 |E|=9 C C

D E F G D F G
E
4
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Applications www.foxitsoftware.com/shopping

 Maps

 Communication Networks Social networks

5
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Applications www.foxitsoftware.com/shopping

 Flight routes

 Web graphs Maze (games)

6
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Terminologies www.foxitsoftware.com/shopping

 Directed Graph  Un-Directed Graph

 Also called digraph  Edge has no direction and considered
 Every edge has a direction, an as two-ways
incoming edge is not equal to outgoing  Vertex order is not important
edge V

U X Z

 Vertex order is important

7
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Terminologies www.foxitsoftware.com/shopping

 End Points  Parallel Edges

 Vertices at both ends of an edge
 Edges with same end points
 Incident Edge
 If vertex is an end point of edge, edge is incident  h and i are parallel edges
on that vertex
 a is incident on u and v
 Adjacent/Neighbor Vertices V
 Vertices that are end points of same edge a b
h
 u, v and w are adjacent
d
 Self Loop U X Z j
 Node connected to itself
 Z is in self loop and j is self edge c e i
 Degree of Node W g
S
 Number of incident edges
 U has degree 2, X has degree 5 f
 Self edge is considered twice, so z has degree 4
Y

8
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Terminologies www.foxitsoftware.com/shopping

 In a directed graph we can distinguish between

 Incoming Edges
 Directed edges for which the given vertex is destination
 c is incoming edge of U
 Outgoing Edges
 Directed edges for which the given vertex is origin
 a is outgoing edge of U
V
 In-Degree of Vertex a b
h
 Number of incoming edges
 Out-Degree of Vertex d
U X Z
 Number of outgoing edges
 Source Vertices c e i
 Vertices with an in-degree of zero
 w is source vertex W g
 Sink Vertices
 Vertices with an out-degree of zero f
 v is sink vertex Y

9
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Terminologies www.foxitsoftware.com/shopping

 Path
 A path between two vertices is sequence of alternating vertices and edges, where each
successive vertex is connected.

V
V

U X Z
U X Z

W W

Y Y

10
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Terminologies www.foxitsoftware.com/shopping

 Simple Path
 A path with distinct nodes
 One of the possible paths from u to v is u-w-v
 Cycle
 A path that starts and finish at same vertex V
V

U X Z
U X Z

W W

Y Y

11
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Terminologies www.foxitsoftware.com/shopping

 Reachability of Vertex
 A vertex is v reachable from other vertex if there exists a path from other vertex to
vertex v
 In undirected graph, edge is considered as 2-ways, so every vertex is reachable in following
example.

V V

U X Z U X Z

 U , V and X are not reachable from Z all vertices are reachable from each other

12
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Terminologies www.foxitsoftware.com/shopping

 Connected Graph  Disconnected Graph

 Each vertex is reachable from every other  A graph that is not connected
vertex, in other words there exists a path
from each vertex to every other vertex

V V

U X Z U X Z

13
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Terminologies www.foxitsoftware.com/shopping

 Strongly Connected Graph  Weakly Connected Graph

 If there exists a directed path between  If there exists a path between each pair
each pair of vertices of vertices which ignores direction

V V

U X Z U X Z

14
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Terminologies www.foxitsoftware.com/shopping

 Completely Connected Graph

 If there exists an edge between each pair of vertices
 Directed  Undirected
V

V
U X

U X
X

 Maximum Edges?  Maximum Edges

 |E|=|V|*|V-1| =O(|V|2)  |E|=|V|*|V-1|/2= O(|V|2)

15
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Terminologies www.foxitsoftware.com/shopping

 Sub Graph V
 A graph that is consists of subset of vertices and edges of G

U X Z
 Two possible sub-graphs
V

U X Z
U X

 Following is not valid sub-graph of G, why?

 Look at definition of sub-graph

U X Z

16
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Terminologies www.foxitsoftware.com/shopping

 Simple Graph
 A graph with no parallel and self edges
V

U X Z

17
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Terminologies www.foxitsoftware.com/shopping

 Weighted Graph  Non-Weighted Graph

 Weights on edge means cost or distance
between end points of edge

18
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Terminologies www.foxitsoftware.com/shopping

 Path Length
 Sum of weights of edges on path from one vertex to other.
 Length of path between u and w is 2
 Length of path between u and y is 3
V
 There are two paths from u to x 1 2
2
 Path u-w-x has length 6 and path u-w-y-x has length 5
2
 Shortest Path U X Z
 Path with minimum length 2 4 1
 From u to x is 5
W 2
 From u to v is 4
1
Y

19
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Terminologies www.foxitsoftware.com/shopping

 Tree
 An undirected graph G is tree if it fulfills any of the following condition:
 G has V-1 edges and no cycles
 G has V-1 edges and is connected
 G is connected, but removing any edge disconnects it
 G is acyclic, but adding any edges creates a cycle
 Exactly one simple path between each pair of vertices in G

V V

U X Z U X Z

20
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Terminologies www.foxitsoftware.com/shopping

 Directed Acyclic Graph (DAG)

 Directed graph without cycles
V

U X Z

 Following graph is not DAG, as it contains a cycle

U X Z

21
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Terminologies www.foxitsoftware.com/shopping

 Directed Acyclic Graph (DAG) B D

 A directed graph without cycles
A
 Applications: C E
 The parse tree constructed by a compiler to execute sequential statements
 Dependency graphs for task scheduling
 Dependency graphs between classes formed by inheritance relationships in object-oriented
programming languages
 Information categorization systems, such as folders in a computer
 Course pre-requisites
CS16 CS141 CS242
CS15

CS17 CS32
CS18 CS123 CS224

22
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Graph ADT www.foxitsoftware.com/shopping

 Common methods for Graph ADT can be:

 numVertices()
 vertices()
 numEdges()
 edges()
 outgoingEdges(v)
 incomingEdges(v)
 getEdge(v1, v2)
 endVertices(e)
 opposite(v, e)
 insertVertex(value)
 insertEdge(v1, v2, value)
 removeVertex(v)
 removeEdge(e)

 Run time depends upon underlying implementation

23
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Memory Representation www.foxitsoftware.com/shopping

 There are multiple ways to represent a graph in memory:

 Adjacency Matrix
 Adjacency List
 Edge List
 Adjacency Map

 Assume following example for all representations

v1 v3

v5

v2 v4

24
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Adjacency Matrix www.foxitsoftware.com/shopping

 The adjacency matrix of a graph G = (V, E) is a |V | × |V | matrix E, where each

entry Eij is equal to 1 if there exists an edge e = (vi, vj ) ∈ E and 0 otherwise.
 1 and 0 can also be replaced with true/false.
 Vertex list itself is stored in 1D array
0 1 2 3 4
“V1” “V2” “V3” “V4” “V5”

V1 V2 V3 V4 V5
V1 0 1 1 0 0
v1 v3 V2 1 0 1 1 0

v5 V3 1 1 0 1 1
V4 0 1 1 0 1
v2 v4 V5 0 0 1 1 0

25
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Adjacency Matrix www.foxitsoftware.com/shopping

 If graph is directed?
 Then entry Eij is equal to 1 if there exists an edge e = from vi to vj and 0 otherwise.
V1 V2 V3 V4 V5
V1 0 1 1 0 0
v1 v3
V2 0 0 1 0 0
V3 0 0 0 1 1 v5
V4 0 1 0 0 0 v4
v2
V5 0 0 0 1 0

 Weighted Graph:
 1 and 0 are replaced with respective weights
 0 or -1 presents no edge

26
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Example www.foxitsoftware.com/shopping

27
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Adjacency Matrix www.foxitsoftware.com/shopping

 Vertex list and Edge list are given

 Running Time? 0 1 2 3 4
 Get a vertex’s out-edges “V1” “V2” “V3” “V4” “V5”
 Get a vertex’s in-edges
 Decide if some edge exists V1 V2 V3 V4 V5
 Insert an edge V1 0 1 1 0 0
 Delete an edge V2 0 0 1 0 0
 Inset a vertex V3 0 0 0 1 1
 Remove a vertex
V4 0 1 0 0 0
 Memory
V5 0 0 0 1 0
 O(|V|2)
 Good for?
 Dense graphs
 Edges are close to |V|2

28
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Adjacency List www.foxitsoftware.com/shopping

 Each vertex is associated with its list of adjacent nodes.

 Vertices themselves are stored in an array or hashmap

1 “V1” 2 3

2 “V2” 1 3 4

5 v1 v3
3 “V3” 1 2 4
v5
4 “V4” 2 3 5
v2 v4
5 “V5” 3 4

 List can be of simple integers/ characters/ strings which represents vertex label or number
 Here assumes a hashmap with <key,value> pair where key is vertex label and values is list of its
connected vertices

29
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
www.foxitsoftware.com/shopping

30
 Edited with the trial version of
Foxit Advanced PDF Editor
To remove this notice, visit:
Adjacency List www.foxitsoftware.com/shopping

 Running Time?
 Get a vertex’s out-edges 1 “V1” 2 3
 Get a vertex’s in-edges
2 “V2” 1 3 4
 Decide if some edge exists
 Insert an edge 3 “V3” 1 2 4 5
 Delete an edge
4 “V4” 2 3 5
 Inset a vertex
 Remove a vertex “V5”
5 3 4
 Memory
 O(|V|+|E|)
 Good for?
 Sparse
 Edges are significantly less than |V|2

31