(JAVA)
Hira Awais
Lecturer (DCS)
DDSA (FOC)
Slide courtesy: Dr. Zahid Halim
A graph G is denoted by G = (V, E) where
V is the set of vertices or nodes of the graph
E is the set of edges or arcs connecting the vertices in V
Each edge E is denoted as a pair (v,w) where v,w e V
For example in the graph below
1 V = {1, 2, 3, 4, 5, 6}
3
E = {(1, 2) (2, 5) (3, 6) (4, 6) (5, 6)}
This is an example of an unordered or
undirected graph
6 4
5
If the pair of vertices is ordered then the graph is a directed
graph or a di-graph
2
1 3 Here,
V = {1, 2, 3, 4, 5, 6}
E = {(1, 2) (2, 5) (5, 6) (6, 3) (6, 4)}
6 4
• Vertex v is adjacent to w iff (v,w) e E
• Sometimes an edge has another component called a weight or cost. If
the weight is absent it is assumed to be 1
A path is a sequence of vertices w1, w2, w3, ....wn such that (wi,
wi+1) e E
Length of a path = # edges in the path
A loop is an edge from a vertex onto itself. It is denoted by (v, v)
A simple path is a path where no vertices are repeated along the
path
A cycle is a path with at least one edge such that the first and last
vertices are the same, i.e. w1 = wn
Weakly Connected Graph:
If there does not exit any path between two pair of vertices, hence if a graph G
does not contain a directed path(from u to v or v to u for every pair of vertices
u,v) then it is weakly connected.
Elements of such a path matrix of this graph is random
Strongly Connected Graph:
A graph is said to be strongly connected if every pair of vertices(u, v) in the
graph contains a path between each other.
In an unweighted directed graph G, every pair of vertices u and v should have a
path in each direction between them i.e., bidirectional path.
The elements of the path matrix of such a graph will contain all 1’s.
Strongly Connected
Weakly Connected
Driving Map
Edge = Road
Vertex = Intersection
Edge weight = Time required to cover the road
Airline Traffic
Vertex = Cities serviced by the airline
Edge = Flight exists between two cities
Edge weight = Flight time or flight cost or both
Computer networks
Vertex = Server nodes
Edge = Data link
Edge weight = Connection speed
CAD/VLSI
Adjacency Matrix
Two dimensional matrix of size n x n where n is the number of vertices in the graph
a[i, j] = 0 if there is no edge between vertices i and j
a[i, j] = 1 if there is an edge between vertices i and j
Undirected graphs have both a[i, j] and a[j, i] = 1 if there is an edge between
vertices i and j
a[i, j] = weight for weighted graphs
Space requirement is Q(N2)
Problem: The array is very sparsely populated. For example if a directed
graph has 4 vertices and 3 edges, the adjacency matrix has 16 cells only 3
of which are 1
Adjacency List
Array of lists
Each vertex has an array entry
A vertex w is inserted in the list for vertex v if there is an outgoing edge
from v to w
Space requirement = Q(E+V)
Sometimes, a hash-table of lists is used to implement the adjacency list
when the vertices are identified by a name (string) instead of an integer
2 1 2
1 3 2 5
3
4
6 4 6
5
5 6 3 4
Graph Adjacency List
An adjacency list for a weighted graph should contain two elements in the list nodes
– one element for the vertex and the second element for the weight of that edge
