Graph
Graph is a non-linear data structure consisting of vertices and edges. The vertices are
sometimes also referred to as nodes and the edges are lines or arcs that connect any
two nodes in the graph. More formally a Graph is composed of a set of vertices( V )
and a set of edges( E ). The graph is denoted by G(V, E).
Basic Operations on Graphs:
Below are the basic operations on the graph:
Insertion of Nodes/Edges in the graph – Insert a node into the graph.
Deletion of Nodes/Edges in the graph – Delete a node from the graph.
Searching on Graphs – Search an entity in the graph.
Traversal of Graphs – Traversing all the nodes in the graph.
Breadth First Search (BFS)
Breadth First Search (BFS) is a graph traversal algorithm that explores all the
vertices in a graph at the current depth before moving on to the vertices at the next
depth level. It starts at a specified vertex and visits all its neighbors before moving
on to the next level of neighbors. BFS is commonly used in algorithms for path
finding, connected components, and shortest path problems in graphs.
Breadth First Search (BFS) for a Graph Algorithm:
Let’s discuss the algorithm for the BFS:
1. Initialization: Enqueue the starting node into a queue and mark it as visited.
2. Exploration: While the queue is not empty:
Dequeue a node from the queue and explore it (e.g., print its value).
For each unvisited neighbor of the dequeued node:
Enqueue the neighbor into the queue.
Mark the neighbor as visited.
3. Termination: Repeat step 2 until the queue is empty.
Example to illustrate the working of the BFS Algorithm
We use an undirected graph with 5 vertices.
We start from vertex 1, the BFS algorithm starts by putting it in the Visited list and putting all
its adjacent vertices in the stack.
Next, we visit the element at the front of the queue i.e. 2, and go to its adjacent nodes.
Since 1 has already been visited, we visit 3 instead.
Vertex 3 has an unvisited adjacent vertex in 5, so we add that to the back of the queue and
visit 4, which is at the front of the queue.
Only 5 remain in the queue since the only adjacent node of 4 i.e. 1 is already visited. We
visited it.
Since the queue is empty, we have completed the Breadth First Traversal of the graph.
Algorithm
void Graph::BFS(int s)
{
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
queue<int> queue;
visited[s] = true;
queue.push(s);
list<int>::iterator i;
while (!queue.empty())
{
s = queue.front();
cout<< s << " ";
queue.pop();
for (i = adj[s].begin(); i != adj[s].end(); ++i)
{
if (!visited[*i]) {
visited[*i] = true;
queue.push(*i);
}
}
}
}
Depth-first search(DFS)
Depth-first search is an algorithm for traversing or searching tree or graph data
structures. The algorithm starts at the root node (selecting some arbitrary node as the
root node in the case of a graph) and explores as far as possible along each branch
before backtracking.
Here's a step-by-step explanation of how the DFS algorithm works:
1. Start by selecting a starting vertex or node.
2. Add the starting vertex on top of a stack.
3. Take the top item of the stack and add it to the visited list/array.
4. Create a list of that vertex's adjacent nodes. Add the ones that aren't in the visited
list to the top of the stack.
Keep repeating steps 3 and 4 until the stack is empty.
Example to illustrate the working of the DFS Algorithm
We use an undirected graph with 5 vertices.
We start from vertex 1, the DFS algorithm starts by putting it in the Visited list and
putting all its adjacent vertices in the stack.
Next, we visit the element at the top of stack i.e. 2 and go to its adjacent nodes. Since
1 has already been visited, we visit 3 instead.
Vertex 3 has an unvisited adjacent vertex in 5, so we add that to the top of the stack and
visit it.
After we visit the last element 4, it doesn't have any unvisited adjacent nodes, so we have
completed the Depth First Traversal of the graph.
Algorithm
void Graph::DFSUtil(int v, bool visited[]) {
visited[v] = true;
cout << v << " ";
for (list<int>::iterator i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
void Graph::DFS(int s) {
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
DFSUtil(s, visited);
}
Representations of Graph
Here are the two most common ways to represent a graph :
1. Adjacency Matrix
2. Adjacency List
Adjacency Matrix
An adjacency matrix is a way of representing a graph as a matrix of boolean (0’s and
1’s).
Let’s assume there are n vertices in the graph So, create a 2D
matrix adjMat[n][n] having dimension n x n.
Representation of Undirected Graph to Adjacency Matrix:
Thee below figure shows an undirected graph. Initially, the entire Matrix is initialized
to 0.. If there is an edge from source to destination, we insert 1 to both cases
(adjMat[destination] and adjMat
adjMat[destination]) because we can go either way.
Representation of Directed Graph to Adjacency Matrix:
The below figure shows a directed graph. Initially, the entire Matrix is initialized
to 0.. If there is an edge from source to destination, we insert 1 for that
particular adjMat[destination]
adjMat[destination].
An adjacency list is a data structure used to represent a graph where each node in
the graph stores a list of its neighboring vertices.
Representation of Undirected Graph to Adjacency li
list:
The below undirected graph has 3 vertices. So, an array of list will be created of size
3, where each indices represent the vertices. Now, vertex 0 has two neighbours (i.e,
1 and 2). So, insert vertex 1 and 2 at indices 0 of array. Similarly, For vertex
verte 1, it has
two neighbour (i.e, 2 and 0) So, insert vertices 2 and 0 at indices 1 of array.
Similarly, for vertex 2, insert its neighbours in array of list.
Representation of Directed Graph to Adjacency list:
The below directed graph has 3 vertices. So, an array of list will be created of size 3,
where each indices represent the vertices. Now, vertex 0 has no neighbours. For
vertex 1, it has two neighbour (i.e, 0 and 2) So, insert vertices 0 and 2 at indices 1 of
array. Similarly, for vertex 2, insert its neighbours in array of list.
Types of Graphs:
1. Undirected Graphs:: A graph in which edges have no direction, i.e., the
edges do not have arrows indicating the direction of traversal. Example: A social
network graph where friendships are not directional.
2. Directed Graphs: A graph in which edges have a direction, i.e., the edges
have arrows indicating the direction of traversal. Example: A web page graph
where links between pages are directional.
3. Weighted Graphs: A graph in which edges have weights or costs associated
with them. Example: A road network graph where the weights can represent the
distance between two cities.
4. Unweighted Graphs: A graph in which edges have no weights or costs
associated with them. Example: A social network graph where the edges
represent friendships.
5. Complete Graphs: A graph in which eeach
ach vertex is connected to every other
vertex. Example: A tournament graph where every player plays against every
other player.
6. Bipartite Graphs: A graph in which the vertices can be divided into two
disjoint sets such that every edge connects a vertex in one set to a vertex in the
other set. Example: A job applicant graph where the vertices can be divided into
job applicants and job openings.
7. Trees:: A connected graph with no cycles. Example: A family tree where each
person is connected to their pare
parents.
8. Cycles: A graph with at least one cycle. Example: A bike-sharing graph
where the cycles represent the routes that the bikes take.
9. Sparse Graphs: A graph with relatively few edges compared to the number
of vertices. Example: A chemical reaction graph where each vertex represents a
chemical compound and each edge represents a reaction between two
compounds.
10. Dense Graphs: A graph with many edges compared to the number of
vertices. Example: A social network graph where each vertex represents a person
and each edge represents a friendship.
Finite Graphs
A graph is said to be finite if it has a finite number of vertices and a finite number of
edges. In other words, both the number of vertices and the number of edges in a finite
graph are limited and can be counted.
Infinite Graph:
A graph is said to be infinite if it has an infinite number of vertices as well as an
infinite number of edges.
Trivial Graph:
A graph is said to be trivial if a finite graph contains only one vertex and no edge. It is
also known as a singleton graph or a single vertex graph. A trivial graph is the
simplest type of graph and is often used as a starting point for building more complex
graphs.
Simple Graph
A graph is said to be a simple graph if the graph doesn't consist of no self-loops and no
parallel edges in the graph.
Multi Graph
A graph is said to be a multigraph if the graph doesn't consist of any self-loops, but
parallel edges are present in the graph. If there is more than one edge present between
two vertices, then that pair of vertices is said to be having parallel edges.
Pseudo Graph
If a graph consists of no parallel edges, but self-loops are present in a graph, it is called
a pseudo graph. The meaning of a self-loop is that there is an edge present in the graph
that starts from one of the graph's vertices, and if that edge ends on the same vertex,
then it is called a pseudo graph.
6. Null Graph:
A graph of order n and size zero is a graph where there are only isolated vertices with
no edges connecting any pair of vertices. A null graph is a graph with no edges. In
other words, it is a graph with only vertices and no connections between them. A null
graph can also be referred to as an edgeless graph, an isolated graph, or a discrete
graph
Advantages of graphs:
1. Graphs can be used to model and analyze complex systems and relationships.
2. They are useful for visualizing and understanding data.
3. Graph algorithms are widely used in computer science and other fields, such as
social network analysis, logistics, and transportation.
4. Graphs can be used to represent a wide range of data types, including social
networks, road networks, and the internet.
Disadvantages of graphs:
1. Large graphs can be difficult to visualize and analyze.
2. Graph algorithms can be computationally expensive, especially for large
graphs.
3. The interpretation of graph results can be subjective and may require domain-
specific knowledge.
4. Graphs can be susceptible to noise and outliers, which can impact the accuracy
of analysis results.
