Graphs: Introduction

A graph is a non-linear data structure with a finite number of vertices and edges, and these
edges are used to connect the vertices. Graphs are used in various applications like computer
networks, social networks, navigation systems, etc.

 Vertices (V): These are the fundamental units of the graph (denoted as V).
 Edges (E): These represent the connections between vertices. Edges can be directed
or undirected (denoted as E).

Graphs are generally denoted as G(V, E) where V is the set of vertices and E is the set of
edges.

Classification of Graphs

o Directed Graph (Digraph):

o A graph in which each edge has a direction, meaning the edge from vertex A
to vertex B is different from the edge from vertex B to vertex A.
o Example: A one-way street in a city, where traffic can flow only in one
direction.
o Undirected Graph:
o A graph where the edges do not have directions, i.e., an edge between vertex
A and vertex B means you can traverse in both directions.
o Example: A two-way street between two cities, where traffic can flow in either
direction.

o Weighted Graph / Unweighted Graph:

o In Weighted Graph, Each edge in the graph has a weight (cost, distance, or
time). These weights are often used to find the shortest path or minimum
spanning tree.
Example: A road network where edges (roads) have distances
(weights).
o In Unweighted Graph, all edges are equal, meaning there is no weight
associated with any edge.

o
o
 o
o Connected Graph/ Disconnected Graph:
o A connected graph is a graph where any vertex can be reached from any other
vertex by following a path of edges. A path is a sequence of edges and vertices
that joins two vertices, where each edge and vertex is distinct. A graph that is
not connected is called disconnected.

o Cyclic Graph / Acyclic Graph:

o A graph that contains at least one cycle, i.e., a path that starts and ends at the
same vertex is known as Cyclic Graph.
o A graph that contains no cycles is known as Acyclic Graph. A directed acyclic
graph (DAG) is often used in scheduling problems.

o Simple Graph / Multi Graph:

o A simple graph is a graph that does not have more than one edge between any
two vertices and no edge starts and ends at the same vertex. In other words a
simple graph is a graph without loops and parallel edges
o A multigraph is a graph which is permitted to have self loops(an edge that
connects a vertex to itself) and multiple edges (also called parallel edges), that
is, edges that have the same end nodes. Thus two vertices may be connected
by more than one edge.
 o Complete Graph:
o A complete graph is a graph in which each vertex is connected to every other
vertex. Every vertex in a complete graph has a degree (n-1), where n is the
number of vertices in the graph. So total edges are n*(n-1)/2.
o A complete graph is denoted by the symbol K_n, where n is the number of
vertices in the graph. Below graph is K - 4 complete graph.

o
o Regular Graph:
o A graph is called regular graph if degree of each vertex is equal. A graph is
called K regular if degree of each vertex in the graph is K

Representation of Graphs

Graphs can be represented in different ways depending on the problem at hand:

1. Adjacency Matrix:
o A 2D array of size V x V where V is the number of vertices. If there is an edge
between vertex i and vertex j, the matrix element at row i and column j is 1 (or
the edge weight in a weighted graph); otherwise, it is 0.
o Advantages: Easy to implement, especially for dense graphs.
o Disadvantages: Requires O(V^2) space, even for sparse graphs.

2. Adjacency List:
o An array (or list) where each element represents a vertex and stores a list of all
the vertices connected to it by edges.
o Advantages: Efficient for sparse graphs, requires less space (O(V + E)).
o Disadvantages: Slightly more complex to implement, but more efficient for
most real-world graphs.

Graph representation refers to the way in which a graph’s vertices and edges are stored in a
computer system. The choice of representation depends on the type of graph (sparse or dense)
and the nature of the operations to be performed (e.g., traversal, finding neighbors, etc.).
1. Adjacency Matrix

An Adjacency Matrix is a 2D array of size V x V, where V is the number of vertices in the

graph. Each cell in the matrix, denoted as matrix[i][j], indicates whether there is an edge
between vertex i and vertex j.

 Undirected Graph: If there is an edge between vertex i and vertex j, both matrix[i]
[j] and matrix[j][i] will be 1 (or the weight of the edge, if the graph is weighted). If
there is no edge, the value will be 0.
 Directed Graph: If there is a directed edge from vertex i to vertex j, then matrix[i][j]
will be 1 (or the weight), and matrix[j][i] will remain 0 (unless there's a reverse
edge).

Note: If there is any weighted graph then instead of 1s and 0s, we can store the weight
of the edge.

Example:

For a graph with vertices A, B, C, and D, an adjacency matrix might look like:

Undirected graph representation

Directed graph represenation

See the directed graph representation:

In the above examples, 1 represents an edge from row vertex to column vertex, and 0
represents no edge from row vertex to column vertex.

Undirected weighted graph represenation

Pros:
 Simple and easy to implement.
 Efficient for dense graphs (where the number of edges E is close to V²).
 Checking the existence of an edge between two vertices is O(1).

Cons:
 Requires O(V²) space, making it inefficient for sparse graphs (where E is much
smaller than V²).
 Inefficient for finding all neighbors of a vertex, as this requires O(V) time.

2. Adjacency List

An adjacency list is used in the linked representation to store the Graph in the computer's
memory. It is efficient in terms of storage as we only have to store the values for edges.

Let's see the adjacency list representation of an undirected graph.

In the above figure, we can see that there is a linked list or adjacency list for every node of
the graph. From vertex A, there are paths to vertex B and vertex D. These nodes are linked to
nodes A in the given adjacency list.

An adjacency list is maintained for each node present in the graph, which stores the node
value and a pointer to the next adjacent node to the respective node. If all the adjacent nodes
are traversed, then store the NULL in the pointer field of the last node of the list.

The sum of the lengths of adjacency lists is equal to twice the number of edges present in an
undirected graph.

Now, consider the directed graph, and let's see the adjacency list representation of that graph.
For a directed graph, the sum of the lengths of adjacency lists is equal to the number of edges
present in the graph.

Now, consider the weighted directed graph, and let's see the adjacency list representation of
that graph.

In the case of a weighted directed graph, each node contains an extra field that is called the
weight of the node.

In an adjacency list, it is easy to add a vertex. Because of using the linked list, it also saves
space.

Each vertex has a list of its neighbors (connected vertices).

Pros:

 Requires O(V + 2E) space, making it efficient for sparse graphs.

 Finding all the neighbors of a vertex takes O(Eₙ) time, where Eₙ is the number of
edges connected to that vertex.
 Adding edges is efficient (O(1) per edge).

Cons:

 Checking the existence of an edge between two vertices can take O(V) in the worst
case (if you're searching for a specific neighbor).
 Slightly more complex to implement than an adjacency matrix.
3. Incidence Matrix

An Incidence Matrix is a matrix where rows represent vertices and columns represent edges.
The value in a cell (i, j) indicates whether the vertex i is incident to the edge j.

 For an undirected graph, matrix[i][j] = 1 if vertex i is connected to the edge j.

 For a directed graph, the cell will contain -1 for the tail vertex and 1 for the head
vertex of a directed edge.

Example:

For a graph with edges:

 (A, B)
 (A, D)
 (B, C)
 (C, D)

The incidence matrix would look like:

e1 e2 e3 e4

A1 1 0 0

B1 0 1 0

C0 0 1 1

D0 1 0 1

Here, e1 is the edge between A and B, e2 between A and D, e3 between B and C, and e4
between C and D.

Pros:

 Can be useful in problems where relationships between vertices and edges are
important.
 Simple to represent directed and undirected graphs uniformly.

Cons:

 Requires O(V * E) space, which is inefficient for large graphs.

 More complex to work with in comparison to adjacency lists and matrices.
Comparison of Graph Representations

Representation Space Complexity Edge Lookup Neighbor Lookup Suitable for

Adjacency Matrix O(V²) O(1) O(V) Dense Graphs

Adjacency List O(V + E) O(V) O(Eₙ) Sparse Graphs

Incidence Matrix O(V * E) O(E) O(E) Vertex-Edge Ops

Choosing the Right Representation

 Adjacency Matrix is suitable for dense graphs where edge lookups need to be fast,
but it consumes a lot of space for sparse graphs.
 Adjacency List is ideal for sparse graphs since it saves space and allows for efficient
traversal and neighbor lookups.
 Incidence Matrix is less commonly used but useful in special applications like
network flow problems or in bipartite graphs.

Graph Traversal Algorithms

Traversal algorithms are used to explore all the vertices and edges in a graph.

1. Depth First Search (DFS):

o DFS is a recursive algorithm that explores as far as possible along a branch
before backtracking. It starts at a source vertex, marks it as visited, and then
recursively visits its unvisited neighbors.
o Time Complexity: O(V + E) where V is the number of vertices and E is the
number of edges.
o Applications:
 Pathfinding and cycle detection.
 Topological sorting in a directed acyclic graph (DAG).
 Solving puzzles like mazes.

Algotrithm:
DFS(G, s) //s is a starting vertex //Time Complexity O(E+V)
[Link]( s ) //Inserting s in stack S
mark s as visited
while (S is not empty)
{ //Pop a vertex from stack to visit next
u = [Link]();
for (each adj vertex av of u) //in any order
{
if(av is not visited)
{
 mark av as visited
[Link](av)
print(av)
break;
}
}
if(av is fully explored)
{
[Link]();
}
}

2. Breadth First Search (BFS):

o BFS is a level-order traversal algorithm that explores all neighbors at the
current depth level before moving on to nodes at the next depth level. It uses a
queue data structure.
o Time Complexity: O(V + E).
o Applications:
 Shortest path in an unweighted graph.
 Finding connected components in an undirected graph.
 Solving shortest path problems in navigation systems.

Algorithm:
BFS(G,s) //s is a starting vertex //Time Complexity O(E+V)
add start vertex s to Q //Q is a linear queue
mark s as visited
while (Q is not empty)
{
u = [Link]();
print(u);
for (each adj vertex av of u) //(in any order)
{
If( av is not visited)
{
mark av as visited
[Link](av)
}
}
}
Graph Algorithms

1. Minimum Spanning Tree (MST): A Minimum Spanning Tree of a graph is a subset

of edges that connects all vertices together without any cycles and with the minimum
possible total edge weight.
o Kruskal’s Algorithm:
 A greedy algorithm that sorts all edges by their weight and adds the
smallest edge to the spanning tree, as long as it doesn’t form a cycle.
 Uses the Disjoint Set (Union-Find) data structure.
 Time Complexity: O(E log V).
 Applications: Network design (e.g., minimizing the cost of laying
cables in a city).

Kruskal’s algorithm is used to find the minimum spanning tree for a connected
weighted graph.
Step 1: Create a forest in such a way that each graph is a separate tree.
Step 2: Create a priority queue Q that contains all the edges of the graph.
Step 3: Repeat Steps 4 and 5 while Q is NOT EMPTY
Step 4: Remove an edge from Q
Step 5: IF the edge obtained in Step 4 connects two different trees, then Add it to the forest
(for combining two trees into one tree).
ELSE
Discard the edge
Step 6: END

o Prim’s Algorithm:
 Also a greedy algorithm but works differently from Kruskal’s. It starts
from an arbitrary vertex and grows the spanning tree by adding the
smallest edge that connects a vertex inside the tree to a vertex outside
the tree.
 Uses a priority queue (min-heap).
 Time Complexity: O(E log V) with a binary heap, O(E + V log V)
with a Fibonacci heap, O(v^2) using simple adjacency matrix.
 Applications: Similar to Kruskal’s in network optimization problems.

Prim’s algorithm is a greedy algorithm that is used to form a minimum spanning tree
for a connected weighted undirected graph.
Prims Algorithm:
Step 1: Select a starting vertex
Step 2: Repeat Steps 3 and 4 until there are fringe vertices
Step 3: Select an edge e connecting the tree vertex and fringe vertex that has minimum
weight
Step 4: Add the selected edge and the vertex to the minimum spanning tree T
[END OF LOOP]
Step 5: EXIT

2. Dijkstra’s Shortest Path Algorithm:

o A greedy algorithm to find the shortest path from a source vertex to all other
vertices in a graph with non-negative edge weights.
o Uses a priority queue (min-heap) to pick the vertex with the smallest distance
and updates the shortest distance to all its neighbors.
o Time Complexity: O(E + V log V) using a Fibonacci heap.
o Applications:
 Shortest path in road networks.
 Network routing protocols.
 GPS navigation systems.

Dijkastra Algorithm

Dijkastra(Graph, Source)
Create vertex set Q
For each vertex v in graph
dist[v] = ∞
add v to Q // Build Heap
dist[Source] = 0
while Q is not empty
u = extract-min[Q]
for each neighbor v of u
Relax (u,v)
Relax (u,v) : if d[u] + c(u,v) < d[v] then d[v] = d[u] + c(u,v)

Time Complexity: O(E log v) using heap, otherwise O(v^2)

Applications of Graphs

 Computer Networks: Modeling communication between computers and routers.

 Social Networks: Representing relationships between users (vertices) and
connections (edges).
 Navigation Systems: Finding the shortest path between locations (e.g., GPS).
 Biology: Modeling ecosystems, where vertices are species and edges are their
relationships.
 Recommendation Systems: Representing users and products with edges showing
relationships based on preferences or purchases.
 Scheduling Problems: Directed acyclic graphs (DAGs) are used to model tasks that
have dependencies, ensuring proper execution order.