DS Module 4

GRAPHS
 Graphs
DEFINITIONS
• A graph, G, consists of two sets V and E. V is a finite non-
empty set of vertices. E is a set of pairs of vertices, these pairs
are called edges.
• V(G) and E(G) will represent the sets of vertices and edges of
graph G.
• We will also write G = (V, E) to represent a graph.
• In an undirected graph the pair of vertices representing any
edge is unordered. Thus, the pairs (v1, v2) and (v2, v1)
represent the same edge.
• In a directed graph each edge is represented by a directed pair
(v1, v2). v1 is the tail and v2 the head of the edge. Therefore
<v2, v1> and <v1, v2> represent two different edges.
 The graphs G1 and G2 are undirected. G3 is a
directed graph.
• V (G1) = {1,2,3,4}; E (G1) = {(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}
• V (G2) = {1,2,3,4,5,6,7}; E (G2) = {(1,2), (1,3), (2,4), (2,5), (3,6), (3,7)}
• V (G3) = {1,2,3}; E (G3) = {<1,2>, <2,1>, <2,3>}.
TERMINOLOGIES

• If (v1, v2) is an edge in E(G), then we shall say the vertices v1

and v2 are adjacent and that the edge (v1, v2) is incident on
vertices v1 and v2.
• The vertices adjacent to vertex 2 in G2 are 4, 5 and 1. The
edges incident on vertex 3 in G2 are (1,3), (3,6) and (3,7).
• If <v1, v2> is a directed edge, then vertex v1 will be said to be
adjacent to v2 while v2 is adjacent from v1.
• The edge <v1, v2> is incident to v1 and v2. In G3 the edges
incident to vertex 2 are <1,2>, <2,1> and <2,3>.
Multigraph:
• Multi Graph: Any graph which contain some parallel edges but
doesn't contain any self-loop is called multi graph.

Figure 6.3 Example of a multigraph that is not a graph.

Subgraph
• A subgraph of G is a graph G' such that V(G') ⊆V(G) and E(G')
⊆ E(G). Figure 6.4 shows some of the subgraphs of G1 and
G3.
• The length of a path is the number of edges on it.
• A simple path is a path in which all vertices except possibly the
first and last are distinct.
• A path such as (1,2) (2,4) (4,3) we write as 1,2,4,3. Paths
1,2,4,3 and 1,2,4,2 is both of length 3 in G1.
• The first is a simple path while the second is not.
• 1,2,3 is a simple directed path in G3. 1,2,3,2 is not a path in G3
as the edge <3,2> is not in E(G3).
• A cycle is a simple path in which the first and last vertices are
the same. 1,2,3,1 is a cycle in G1. 1,2,1 is a cycle in G3.
• In an undirected graph, G, two vertices v1 and v2 are said to be
connected if there is a path in G from v1 to v2 (since G is
undirected, this means there must also be a path from v2 to
v1).
• A connected component or simply a component of an
undirected graph is a maximal connected subgraph. G4 has
two components H1 and H2.
• A tree is a connected acyclic (i.e., has no cycles) graph.
• A directed graph G is said to be strongly connected if for every
pair of distinct vertices <vi, vj > in V(G) there is a directed path
from vi to vj and also from vj to vi.
• The graph G3 is not strongly connected as there is no path
from v3 to v2.
• A strongly connected component is a maximal subgraph that
is strongly connected. G3 has two strongly connected
components.
Graph Representations
1. Adjacency Matrix
2. Adjacency Lists
3. Adjacency Multilists
Adjacency Matrix.
• Let G = (V, E) be a graph with n vertices, n 1. The adjacency
matrix of G is a 2-dimensional nxn array, say A, with the
property that A (i, j) = 1 iff the edge (vi, vj) (<vi,vj>for a directed
graph) is in E(G). A(i,j) = 0 if there is no such edge in G. The
adjacency matrices for the graphs G1, G3 and G4 are shown in
figure 6.7.
Adjacency Lists

• In this representation the n rows of the adjacency matrix are

represented as n linked lists. There is one list for each vertex in
G. The nodes in list i represent the vertices that are adjacent
from vertex i.
• Each node has at least two fields: VERTEX and LINK. The
VERTEX fields contain the indices of the vertices adjacent to
vertex i. The adjacency lists for G1, G3 and G4 are shown in
figure 6.8. Each list has a head node.
GRAPHS TRAVERSALS
• Graph traversal is a technique used for a searching vertex
in a graph.
• The graph traversal is also used to decide the order of
vertices is visited in the search process.
• A graph traversal finds the edges to be used in the search
process without creating loops.
• That means using graph traversal we visit all the vertices
of the graph without getting into looping path.
• There are two graph traversal techniques and they are as
follows.
1. DFS (Depth First Search)
2. BFS (Breadth First Search)
Depth First Search
• Depth first search of an undirected graph proceeds as
follows.
• The start vertex v is visited. Next an unvisited vertex w
adjacent to v is selected and a depth first search from w
initiated.
• When a vertex u is reached such that all its adjacent
vertices have been visited, we back up to the last vertex
visited which has an unvisited vertex w adjacent to it and
initiate a depth first search from w.
• The search terminates when no unvisited vertex can be
reached from any of the visited one.
void dfs (int v)
{
visited [v] = TRUE;
printf(“%5d", v);
for (w =graph [v]; w; w = w→link)
if (!visited [w→vertex])
dfs (w→vertex);
}
 DFS Traversal
• (numbers on the edge or branch specify the order in which
nodes are visited)
Breadth First Search
• Starting at vertex v and marking it as visited, breadth first
search differs from depth first search in that all unvisited
vertices adjacent to v are visited next.
• Then unvisited vertices adjacent to these vertices are
visited and so on.
• A breadth first search beginning at vertex v1 of the graph
in figure 6.13(a) would first visit 1 and then 2 and 3. Next
vertices 4, 5, 6 and 7 will be visited and finally 8.
Algorithm BFS gives the details.
void bfs (int v)
{
nodePointer w;
front= rear = NULL; /* initialize queue*/
printf (“%5d", v);
visited [v] =TRUE;
addq(v);
while (front)
{
v= deleteq ();
for (w=graph [v]; w; w =w->link)
if (!visited [w->vertex])
{
printf(“%5d", w→vertex);
addq (w->vertex);
visited [w->vertex] = TRUE;
}
}
}
 BFS Traversal
(numbers on the edge or branch specify the order in which nodes
are visited)
 Spanning Tree
• Spanning tree of a graph is its acyclic connected subgrapgh
that contains all the vertices of the graph.
 b c
a

Fig(b) : Depth First Spanning tree of fig (a)

Fig(c) : Breadth First Spanning tree of fig (a)
 Biconnected components

• A Biconnected graph is a graph that has no articulation

points.
• An articulation point is a vertex v of G such that the deletion
of v, together with all edges incident on v, produces a graph
G’, that has at least two connected components.
• Example Biconnected graph