Data Structures

19. Graphs

Graphs 1
Graphs

• Consider this collection of vertices

– V = { v 1 , v2, . . . , v9}
– Where | V | = n

23-Graphs 2
Undirected Graphs

• Associated with these vertices are | E | = 5 edges

– E = {{v1, v2}, {v3, v5}, {v4, v8}, {v4, v9}, {v6, v9}}
• Pair { v j , v k } indicates following relations
– Vertex v j is adjacent to vertex v k
– Vertex v k is adjacent to vertex v j

Graphs 3
Undirected Graphs – Example

• Given | V | = 7 vertices and | E | = 9 edges

– 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}}

Graphs 4
Applications Of Graphs

• Driving Map
– Vertex = Intersection, destinations
– Edge = Road

• Airline Traffic
– Vertex = Cities serviced by the airline
– Edge = Flight exists between two cities

• Computer networks
– Vertex = Server nodes, end devices, routers
– Edge = Data link

Graphs 5
Applications Of Graphs

• Many real-world applications concern large graphs

• Web document graph - 1 trillion webpages

– Vertex = Webpage
– Edge = Hyperlink

• Social networks - 1.3 billion users

– Vertex = Users
– Edge = Friendship relation

Graphs 6
Categorizations

Undirected Graphs
Directed Graphs
Undirected Graphs – Definition

• An undirected Graph is defined as G=(V,E) consisting of

– Set V of vertices: V = { v 1 , v 2 , . . . , v n }
Number of vertices is denoted by | V | = n
– Set E of unordered pairs { v i , v j } termed edges
Edges connect the vertices

• Maximum number of edges in an undirected graph is O(|V | 2 )

 V  V V 1
E  
2 2
O V
2
 
– Assumption: A vertex is never adjacent to itself
– For example, { v 1 , v 1 } will not define an edge

• Many data structures can implement abstract undirected graphs

– Adjacency matrices, Adjacency lists

Graphs 8
Degree

• Degree of a vertex is defined as the number of adjacent vertices

– degree(A) = degree(D) = degree(C) = 3
– degree(B) = degree(E) = 4
– degree(F) = 1
– degree(G) = 0

• Vertices adjacent to a given vertex are its neighbors

Graphs 9
Subgraph

• A sub-graph of a graph G is defined by

– Subset of the vertices
– Subset of the edges that connected the subset of vertices in the
original graph
• Every graph is a subgraph of itself

Graphs 10
Path

• Path in an undirected graph is an ordered sequence of vertices

– Consecutive vertices are connected through edges

• Path from vertex 0 to vertex k is ( v 0 , v 1 , v 2 , . . . , v k )

– where { v j – 1 , v j } is an edge for j = 1 , . . . , k

• Length of a path is equal to the number of edges

• Example: Path from A to F

– Path: ( A , B, E, C, F)
– Length of the path is 4

Graphs 11
Path – Example

• Path of length 5: ( A, B, E, C, B, D)
– Repitition of vertex B

Graphs 12
Path – Example

• A trivial path of length 0: ( A )

Graphs 13
Simple Path

• A simple path has no repetitions other than perhaps the first and
last vertices

• A simple cycle is a simple path of at least two vertices with the first
and last vertices equal
– Note: these definitions are not universal

• A loop is an edge from a vertex onto itself

Graphs 14
Connectedness

• Two vertices v i , v j are said to be connected if there exists a path

from v i to v j
• A graph is connected if there exists a path from every vertex to
every other vertex

A connected graph An unconnected graph

Graphs 15
Weighted Graphs

• A weight may be associated with each edge in a graph

– This could represent distance, energy consumption, cost, etc.
– Such a graph is called a weighted graph
• Pictorially, we will represent weights by numbers next to the edges

Graphs 16
Weighted Graphs

• Length of a path within a weighted graph is the sum of all of the

edges which make up the path
• The length of the path ( A, D, G) in the following graph is 8. 8

Graphs 17
Weighted Graphs – Example

• Different paths may have different weights

– Another path is ( A, C, F, G) with length 1. 2 + 1. 4 + 4. 5 = 7. 1

Graphs 18
Weighted Graphs – Example

• Find the shortest path between two vertices A and G

• Shortest path is ( A , C, F, D, E, G) with length 5.7

Graphs 19
Trees

• A graph is a tree if it satisfies the following two conditions

– Graph is connected
– There is a unique path between any two vertices

• Consequences Three trees on

same 8 vertices
– The number of edges is | E| = | V| – 1
– The graph is acyclic, that is, it does not contain any cycles
– Adding one more edge must create a cycle
– Removing any one edge creates two disjoint non-empty sub-graphs
Graphs 20
Trees

• Any tree can be converted into a rooted tree by

– Choosing any vertex to be the root
– Defining its neighboring vertices as its children
• Recursively defining
– All neighboring vertices other than that one designated as parent to
be that vertex children

Unrooted Tree Tree rooted at A

Graphs 21
Trees – Example

Unrooted Tree Tree rooted at C

Graphs 22
Trees – Example

Unrooted Tree Tree rooted at B

Graphs 23
Forest

• A forest is any graph that has no cycles

• Consequences
– The number of edges is | E | < | V |
– The number of trees is | V | – | E |
– Removing any one edge adds one more tree to the forest

- Forest with 22 vertices and 18

edges
- Four trees

Graphs 24
Directed Graphs

• In a directed graph, the edges on a graph are associated with a

direction
– Edges are ordered pairs ( v j , v k ) denoting a connection from v j to v k
– The edge ( v j , v k ) is different from the edge ( v k , v j )

• Streets are directed graphs

– In most cases, you can go two ways unless it is a one-way street

Graphs 25
Directed Graphs

• Given our graph of nine vertices V = { v 1 , v 2 , …v 9 }

– These six pairs ( v j , v k ) are directed edges
– E = { ( v 1, v 2) , ( v 3, v 5) , ( v 5, v 3) , ( v 6, v 9) , ( v 8, v 4) ,
(v9, v4)}

Graphs 26
In and Out Degree

• Degree of a vertex must be modified to consider both cases:

– Out-degree of a vertex is the number of vertices which are adjacent to
the given vertex
Number of outgoing edges
– In-degree of a vertex is the number of vertices which this vertex is
adjacent to
Number of incoming edges

• In this graph:
– In-degree(v1) = 0 out-degree(v1) = 2
– In-degree(v5) = 2 out-degree(v5) = 3

Graphs 27
Path

• A path in a directed graph is an ordered sequence of vertices

– ( v 0 , v1, v2, . . . , vk)
– where ( v j – 1 , v j ) is an edge for j = 1 , . . . , k

• A path of length 5 in this graph is

– ( v 1 , v4, v5, v3, v5, v2)

• A simple cycle of length 3 is

– ( v 8 , v4, v5, v8)

Graphs 28
Connectedness

• Two vertices v j , v k are said to be connected if there exists a path

from v j to v k
– A graph is strongly connected if there exists a directed path between
any two vertices
– A graph is weakly connected if there exists a path between any two
vertices that ignores the direction

Graphs 29
Connectedness – Example

• The sub-graph { v 3 , v 4 , v 5 , v 8 } is strongly connected

• The sub-graph { v 1 , v 2 , v 3 , v 4 , v 5 , v 8 } is weakly connected

Graphs 30
Weighted Directed Graphs

• Each edge is associated with a value

• If both ( v j , v k ) and ( v j , v k ) are edges
– It is not required that they have the same weight

6.4

7.5
6.7 6.8
7.3 5.9

4.1
3.2
4.7
5.4 4.5

Graphs 31
Representation

• How do we store the adjacency relations?

– Adjacency matrix
– Adjacency list

Graphs 32
Adjacency Matrix

• Two dimensional matrix of size n x n where n = | V|

• a [ i , j ] = 0 ( F ) if there is no edge between vertices v i and v j
• a [ i , j ] = 1 ( T ) if there is an edge between vertices v i and v j
• Adjacency matrix of undirected graphs is symmetric
– a[i, j ] = a[j, i ]

F
F
F

F
F
F

Graphs 33
Adjacency Matrix – Weighted Graph

• The matrix entry [ j , k ] is set to the weight of the edge ( v j , v k )

• How to indicate absence of an edge in the graph?

Graphs 34
Adjacency Matrix – Directed Graph

• For directed graph the matrix would not necessarily be symmetric

Graphs 35
Adjacency Matrix – Analysis

1 2 3 4 5 6 7 8 9
1 1 1
2
3 1
4 1 1
5 1 1 1
6 1
7 1
8 1
9

• Requires memory : O (|V | 2 )

• Determining if v j is adjacent to v k : O(1)
• Finding all neighbors of v j : O ( | V | )

Graphs 36
Adjacency Matrix – Problem

• Very sparsely populated

– Out of 81 cells only 11 are 1 (or T)

1 2 3 4 5 6 7 8 9
1 1 1
2
3 1
4 1 1
5 1 1 1
6 1
7 1
8 1
9

Graphs 37
Adjacency List

• Each vertex is associated with a list of its neighbors

– A vertex w is inserted in the list for vertex v if edge ( v, w) exists

1 • →2→4
2 •
3 • →5
4 • →2→5
5 • →2→3→ 8
6 • →9
7 • →9
8 • →4
9 •

• Requires memory : O(|V| + | E | )

Graphs 38
Adjacency List – Weighted Graphs

• An adjacency list for a weighted graph contains two elements

– First element for the vertex
– Second element for the weight of that edge
Array

Linked list

• When the vertices are identified by a name (i.e., string)

– Hash-table of lists is used to implement the adjacency list

Graphs 39
Adjacency List – Implementation

• Node to store adjacent vertex and weight of the edge

cl ass Si ngl eNode {

private:
i n t a d j a c e nt _v er t ex ;
double edge_weight;
Si ngl eNode * next _node;
};

• Define and create Array

SingleNode * a r r a y ;
a r r a y = new SingleNode[16];

Graphs 40
Graph Problems – Euler Tour

• A sequence of vertices that traverse all edges in the graph exactly

once
– Leonhard Euler in 1736
– Laid the foundations of graph theory

• Problem: To devise a walk through the city that would cross each
of the seven bridges of Königsberg once and only once
– Euler proved problem has no solution

Graphs 41
Graph Problems – Hamiltonian Cycle

• Is there a simple cycle that connects all vertices in the graph

– NP-Complete

• Knight’s Tour of chessboard

– A sequence of knight’s moves
– Visit every square of a chessboard precisely once
– Returns to its initial square

Graphs 42
Graph Problems – Traveling Salesman

• A salesman wishes to
– Visit a number of towns, and then
– Return to his starting town
• Given the travelling times between towns, how should the travel be
planned, so that:
– He visits each town exactly once, and
– He travels in as short time as possible

• Problem: Given a weighted graph G, provide shortest cycle that

contains all vertices in G
– NP-Hard problem

Graphs 43
Graph Problems – Others

• Minimum-cost spanning tree

– Given a weighted graph G, determine a spanning tree with minimum
total edge cost

• Single-source shortest path

– Given a weighted graph G and a source vertex v in G, determine the
shortest paths from v to all other vertices in G

Graphs 44
Any Question So Far?

Graphs 45