GRAPHS
Definitions
A graph G can be defined as an ordered set G(V, E)
where V(G) represents the set of vertices and E(G)
represents the set of edges which are used to connect
these vertices.
More precisely, a graph is a data structure (V, E) that
consists of
A collection of vertices V
A collection of edges E, represented as ordered
pairs of vertices (u,v)
This graph has a set of vertices V=
{ 1,2,3,4,5}and a set of edges E= { (1,2),(1,3),
(2,3),(2,4),(2,5),(3,5),(4,5 }.
Types of Graphs
1.Undirected graph
In an undirected graph, edges are not associated with
the directions with them.
An undirected graph comprises a set of nodes and
links connecting them. The order of the two
connected vertices is irrelevant and has no direction.
You can form an undirected graph with a finite
number of vertices and edges
A graph with edges that don’t have direction is
called an undirected graph. The edges in an
undirected graph indicate a two-way relationship.
2.Directed Graph
A Directed graph(digraph) is a graph that has edges
with direction. These edges represent a one-way
relationship. That is edges can be only traversed in
one direction.
A directed graph also referred to as a digraph, is a set
of nodes connected by edges, each with a direction
In a directed graph, edges form an ordered pair.
Edges represent a specific path from some vertex A
to another vertex B. Node A is called initial node
while node B is called terminal node.
Incoming Edge (Indegree)
An edge that comes into a vertex.
Example: If A → B, then for vertex B, this edge is an
incoming edge.
Outgoing Edge (Outdegree)
An edge that goes out from a vertex.
Example: If A → B, then for vertex A, this edge is an
outgoing edge.
3.weighted graph
A graph G= (V, E) is called a labelled or
weighted graph because each edge has a value or
weight representing the cost of traversing that
edge.
A weighted graph is a graph that has a number
associated with each of its edges.
The number is called the weight of the edge.
A weighted graph can be undirected or directed.
The weight of a path P is the sum of the weights
of the edges along the path
4.Connected Graph
A graph is considered to be connected if and only if
any two of its nodes have a path between them.
5.Complete Graph
A complete graph is the one in which every node is
connected with all other nodes
6.Multi graph
A multigraph is a graph that contains a self-loop,
parallel edges, or both.
Graph Terminology
Path
A finite sequence of edges that connects a series of
vertices is called a path.
A path is said to be closed if it starts and ends at the
same node.
A path is considered to be simple if all of its nodes
are distinct, except the initial and last node.
Graph Representation
There are different ways to optimally represent a
graph, depending on the density of its edges, type of
operations to be performed and ease of
use.
1.Adjacency Matrix
2.Adjacency List
1. Adjacency Matrix
Adjacency matrix is a sequential representation.
It is used to represent which nodes are adjacent
to each other. i.e. is there any edge connecting
nodes to a graph.
In this representation, we have to construct a NN
matrix A.
If there is any weighted graph then instead of 1s
and Os, we can store the weight of the edge.
Since the adjacency matrix will be sparse, a lot
of space will be wasted. Adding or removing
new nodes may be difficult.
2.Adjacency List
Adjacency list is a linked representation.
In this representation, for each vertex in the
graph, we maintain the list of its neighbours. It
means, every vertex of the graph contains list of
its adjacent vertices.
We have an array of vertices which is indexed
by the vertex number and for each vertex v, the
corresponding array element points to a singly
linked list of neighbours of v.
The linked representation of a graph contains
two lists, a NODE list and an EDGE(Adjacency)
list.
Each element in the NODE list will correspond
to a node in the graph. It contains:
a. Name of the Node.
b.Pointer to adjacent nodes.
c. Pointer to next node.
Each element in the edge list will represent an
edge of the graph. It contains:
a)Destination node of the edge.
b) Link that link together the edges with the
same initial node.
Because we only need to keep the values for the ed
ges, an adjacency list is efficient in terms of storag
e
Applications of Graph
In circuit networks: connection points as vertices
and wires as edges.
In transport network: stations as vertices and
routes as edges.
For finding shortest paths.
In state diagrams: states as vertices and
transition between states as edges.
For scientific computations.
In recommendation algorithms.
Google maps as a graph
Resource allocation graph
