UNIT 5 - GRAPHS

The Graph ADT Introduction

Definition
Graph representation
Elementary graph operations BFS, DFS
Introduction to Graphs

Graph is a non linear data structure; A map is a well-known example of a graph. In a map various connections are
made between the cities. The cities are connected via roads, railway lines and aerial network. We can assume that
the graph is the interconnection of cities by roads. Euler used graph theory to solve Seven Bridges of Königsberg
problem. Is there a possible way to traverse every bridge exactly once – Euler Tour

Figure: Section of the river Pregal in Koenigsberg and Euler's graph.

Defining the degree of a vertex to be the number of edges incident to it, Euler showed that there is a walk starting
at any vertex, going through each edge exactly once and terminating at the start vertex iff the degree of each,
vertex is even. A walk which does this is called Eulerian. There is no Eulerian walk for the Koenigsberg bridge
problem as all four vertices are of odd degree.

A graph contains a set of points known as nodes (or vertices) and set of links known as edges (or Arcs) which
connects the vertices.

A graph is defined as Graph is a collection of vertices and arcs which connects vertices in the graph. A graph G is
represented as G = ( V , E ), where V is set of vertices and E is set of edges.

Example: graph G can be defined as G = ( V , E ) Where V = {A,B,C,D,E} and

E = {(A,B),(A,C)(A,D),(B,D),(C,D),(B,E),(E,D)}. This is a graph with 5 vertices and 6 edges.

Graph Terminology

1.Vertex : An individual data element of a graph is called as Vertex. Vertex is also known as node. In above
example graph, A, B, C, D & E are known as vertices.

2.Edge : An edge is a connecting link between two vertices. Edge is also known as Arc. An edge is represented as
(starting Vertex, ending Vertex).

In above graph, the link between vertices A and B is represented as (A,B).

Edges are three types:

1.Undirected Edge - An undirected edge is a bidirectional edge. If there is an undirected edge between vertices A
and B then edge (A , B) is equal to edge (B , A).

2.Directed Edge - A directed edge is a unidirectional edge. If there is a directed edge between vertices A and B
then edge (A , B) is not equal to edge (B , A).

1
3.Weighted Edge - A weighted edge is an edge with cost on it.

Types of Graphs

1.Undirected Graph

A graph with only undirected edges is said to be undirected graph.

2.Directed Graph

A graph with only directed edges is said to be directed graph.

3.Complete Graph

A graph in which any V node is adjacent to all other nodes present in the graph is known as a complete graph. An
undirected graph contains the edges that are equal to edges = n(n-1)/2 where n is the number of vertices present in
the graph. The following figure shows a complete graph.

4.Regular Graph

Regular graph is the graph in which nodes are adjacent to each other, i.e., each node is accessible from any other
node.

5.Cycle Graph

A graph having cycle is called cycle graph. In this case the first and last nodes are the same. A closed simple path
is a cycle.

2
6.Acyclic Graph

A graph without cycle is called acyclic graphs.

7. Weighted Graph

A graph is said to be weighted if there are some non negative value assigned to each edges of the graph. The
value is equal to the length between two vertices. Weighted graph is also called a network.

Outgoing Edge

A directed edge is said to be outgoing edge on its orign vertex.

Incoming Edge

A directed edge is said to be incoming edge on its destination vertex.

Degree

Total number of edges connected to a vertex is said to be degree of that vertex.

Indegree

Total number of incoming edges connected to a vertex is said to be indegree of that vertex.

Outdegree

Total number of outgoing edges connected to a vertex is said to be outdegree of that vertex.

Parallel edges or Multiple edges

If there are two undirected edges to have the same end vertices, and for two directed edges to have the same
origin and the same destination. Such edges are called parallel edges or multiple edges.

Self-loop

An edge (undirected or directed) is a self-loop if its two endpoints coincide.

Simple Graph

A graph is said to be simple if there are no parallel and self-loop edges.

3
Adjacent nodes

When there is an edge from one node to another then these nodes are called adjacent nodes.
Incidence

In an undirected graph the edge between v1 and v2 is incident on node v1 and v2.
Walk

A walk is defined as a finite alternating sequence of vertices and edges, beginning and ending with vertices, such
that each edge is incident with the vertices preceding and following it.
Closed walk

A walk which is to begin and end at the same vertex is called close walk. Otherwise it is an open walk.

If e1,e2,e3,and e4 be the edges of pair of vertices (v1,v2),(v2,v4),(v4,v3) and (v3,v1) respectively ,then v1 e1 v2
e2 v4 e3 v3 e4 v1 be its closed walk or circuit.

Path

A open walk in which no vertex appears more than once is called a path.

If e1 and e2 be the two edges between the pair of vertices (v1,v3) and (v1,v2) respectively, then v3 e1 v1 e2 v2 be
its path.
Length of a path

The number of edges in a path is called the length of that path. In the following, the length of the path is 3.

An open walk Graph

Circuit

A closed walk in which no vertex (except the initial and the final vertex) appears more than once is called a
circuit.
A circuit having three vertices and three edges.

4
Sub Graph

A graph S is said to be a sub graph of a graph G if all the vertices and all the edges of S are in G, and each edge of
S has the same end vertices in S as in G. A subgraph of G is a graph G’ such that V(G’)  V(G) and E(G’) 
E(G)

Connected Graph

A graph G is said to be connected if there is at least one path between every pair of vertices in G. Otherwise,G is
disconnected.

A connected graph G A disconnected graph G

This graph is disconnected because the vertex v1 is not connected with the other vertices of the graph.

Degree

In an undirected graph, the number of edges connected to a node is called the degree of that node or the degree of
a node is the number of edges incident on it.

In the above graph, degree of vertex v1 is 1, degree of vertex v2 is 3, degree of v3 and v4 is 2 in a connected
graph.

Indegree

The indegree of a node is the number of edges connecting to that node or in other words edges incident to it.

In the above graph,the indegree of vertices v1, v3 is 2, indegree of vertices v2, v5 is 1 and indegree of v4 is zero.
5
Outdegree

The outdegree of a node (or vertex) is the number of edges going outside from that node or in other words the

ADT of Graph:

Structure Graph is

objects: a nonempty set of vertices and a set of undirected edges, where each edge is a pair of vertices

functions: for all graph  Graph, v, v1 and v2  Vertices

Graph Create()::=return an empty graph

Graph InsertVertex(graph, v)::= return a graph with v inserted. v has no edge.

Graph InsertEdge(graph, v1,v2)::= return a graph with new edge between v1 and v2

Graph DeleteVertex(graph, v)::= return a graph in which v and all edges incident to it are removed

Graph DeleteEdge(graph, v1, v2)::=return a graph in which the edge (v1, v2) is removed

Boolean IsEmpty(graph)::= if (graph==empty graph) return TRUE else return FALSE

List Adjacent(graph,v)::= return a list of all vertices that are adjacent to v

Graph Representations

Graph data structure is represented using following representations

1. Adjacency Matrix

2. Adjacency List

3. Adjacency Multilists

1.Adjacency Matrix

In this representation, graph can be represented using a matrix of size total number of vertices by total number of
vertices; means if a graph with 4 vertices can be represented using a matrix of 4X4 size.

In this matrix, rows and columns both represent vertices.

This matrix is filled with either 1 or 0. Here, 1 represents there is an edge from row vertex to column vertex and 0
represents there is no edge from row vertex to column vertex.

Adjacency Matrix : let G = (V, E) with n vertices, n  1. The adjacency matrix of G is a 2-dimensional n  n
matrix, A, A(i, j) = 1 iff (vi, vj) E(G) (vi, vj for a diagraph), A(i, j) = 0 otherwise.

example : for undirected graph

For a Directed graph

6
 Walk – A walk is a sequence of vertices and
edges of a graph i.e. if we traverse a graph then
we get a walk. Edge and Vertices both can be
repeated

Here, 1-2-3-4-2-1-3 is a walk.

Open walk- A walk is said to be an open walk if the starting and
ending vertices are different
 1-2-3-4-5-3 is an open walk.
1-2-3-4-5-3-1 is a closed walk
 Trail –
Trail is an open walk in which no edge is repeated.
Vertex can be repeated.
 Here 1-3-8-6-3-2 is trail
Also 1-3-8-6-3-2-1 will be a closed trail
 Path –
It is a trail in which neither vertices nor
edges are repeated
Here 6-8-3-1-2-4 is a Path
 Cycle –
Traversing a graph such that we do not
repeat a vertex nor we repeat a edge but the
starting and ending vertex must be same
 Here 1->2->4->3->1 is a cycle.
 Eulerian path: A path in a graph G is called
euler path if it includes every edge exactly
once.
 Example:
 A graph is said to be connected if there
exists at least one path between every pair of
vertices in the graph.
 Tree
 Tree: A tree is a connected undirected graph that contains no
cycles
 Forest: A collection of trees is called forest. 1 3

3 1 3 2
1
2 4
4 5
5 4
Tree 5 Forest
Tree

 The Spanning Tree of a Graph G is a subgraph of G that is a

tree and contains all the vertices of G.
1 3
1 3 2
4
2 5
4 Spanning
5 Tree
Graph
7
1. An undirected graph is a tree iff there is a
unique simple path between any two
vertices.

2. A simple graph G = (V, E) is a tree iff |E| =

|V| - 1 or A tree with n vertices has n-1
edges
A rooted tree is a tree in which one vertex
designated as root and every edge directed
away.

root
root

Rooted tree: one vertex designated as
root and every edge directed away

Parent: u is the parent of v

iff (if and only if) there is an
edge directed from u to v

Child: v is called the child of u

Every non-root node has a unique parent (?)

 root Level 0

Level 1
parent
Height=3
Level 2
vertex

Level 3
children
 Root: a vertex with no parent
 Leaf: a vertex with no children
 Internal node: vertex with children
 Ancestors: parent and parents of parents
 Siblings: vertices with the same parent
 Height = number of levels
 When every vertex in a rooted tree has at most
two children, the tree is called a binary tree
3-ary tree Full 3-ary tree
 In an ordered rooted tree the children are
ordered.
 For example, in an ordered binary tree, a
vertex may have left child and right child

root

Left child Right child

Left child Right child