Practical No.
6 Group C
Aim: To illustrate the various Graph Functions.
Problem Statement : C- 13 Represent a given graph using adjacency matrix/list to perform DFS and using
adjacency list to perform BFS. Use the map of the area around the college as the graph. Identify the
prominent land marks as nodes and perform DFS and BFS on that.
Learning Objectives:
To understand concept of Graph and Adjacency matrix.
To analyze the working of various Traversals-depth first and breadth first.
Learning Outcome: Students will be able to use various set of operations on depth first and breadth first.
Theory:
Graph:
Graph is a data structure that consists of following two components:
1. A finite set of vertices also called as nodes.
2. A finite set of ordered pair of the form (u, v) called as edge. The pair is ordered because (u, v)
is not same as (v, u) in case of directed graph(di-graph). The pair of form (u, v) indicates that there
is an edge from vertex u to vertex v. The edges may contain weight/value/cost.
Graphs are used to represent many real life applications: Graphs are used to represent networks.
The networks may include paths in a city or telephone network or circuit network. Graphs are
also used in social networks like linkedIn, facebook. For example, in facebook, each person is
represented with a vertex(or node). Each node is a structure and contains information like person
id, name, gender and locale. See this for more applications of graph.
Following is an example undirected graph with 5 vertices.
Following two are the most commonly used representations of graph.
1. Adjacency Matrix
2. Adjacency List
There are other representations also like, Incidence Matrix and Incidence List. The choice of the
graph representation is situation specific. It totally depends on the type of operations to be
performed and ease of use.
Adjacency Matrix:
Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let
the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j.
Adjacency matrix for undirected graph is always symmetric. Adjacency Matrix is also used to
represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with
weight w.
The adjacency matrix for the above example graph is:
Adjacency Matrix Representation
Pros: Representation is easier to implement and follow. Removing an edge takes O(1) time.
Queries like whether there is an edge from vertex ‘u’ to vertex ‘v’ are efficient and can be done
O(1).
Cons: Consumes more space O(V^2). Even if the graph is sparse(contains less number of edges),
it consumes the same space. Adding a vertex is O(V^2) time.
Adjacency List:
An array of linked lists is used. Size of the array is equal to number of vertices. Let the array be
array[]. An entry array[i] represents the linked list of vertices adjacent to the ith vertex. This
representation can also be used to represent a weighted graph. The weights of edges can be stored
in nodes of linked lists. Following is adjacency list representation of the above graph.
Pros: Saves space O(|V|+|E|) . In the worst case, there can be C(V, 2) number of edges in a graph
thus consuming O(V^2) space. Adding a vertex is easier.
Cons: Queries like whether there is an edge from vertex u to vertex v are not efficient and can be
done O(V).
Depth First Search or DFS for a Graph
Depth First Traversal (or DFS) for a graph is similar to Depth First Traversal of a tree. The only
catch here is, that, unlike trees, graphs may contain cycles (a node may be visited twice). To avoid
processing a node more than once, use a boolean visited array. A graph can have more than one DFS
traversal.
Example:
Input: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Output: DFS from vertex 1 : 1 2 0 3
How does DFS work?
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.
Let us understand the working of Depth First Search with the help of the following illustration:
Step1: Initially stack and visited arrays are empty.
Step 2: Visit 0 and put its adjacent nodes which are not visited yet into the stack.
Step 3: Now, Node 1 at the top of the stack, so visit node 1 and pop it from the stack and put all of its adjacent
nodes which are not visited in the stack.
Step 4: Now, Node 2 at the top of the stack, so visit node 2 and pop it from the stack and put all of its adjacent
nodes which are not visited (i.e, 3, 4) in the stack.
Step 5: Now, Node 4 at the top of the stack, so visit node 4 and pop it from the stack and put all of its adjacent
nodes which are not visited in the stack.
Step 6: Now, Node 3 at the top of the stack, so visit node 3 and pop it from the stack and put all of its adjacent
nodes which are not visited in the stack.
Now, Stack becomes empty, which means we have visited all the nodes and our DFS traversal ends.
Breadth First Search (BFS) for a Graph:
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 pathfinding, connected components, and shortest path problems in graphs.
How Does the BFS Algorithm Work?
Starting from the root, all the nodes at a particular level are visited first and then the nodes of the next level
are traversed till all the nodes are visited.
To do this a queue is used. All the adjacent unvisited nodes of the current level are pushed into the queue
and the nodes of the current level are marked visited and popped from the queue.
Illustration:
Let us understand the working of the algorithm with the help of the following example.
Step1: Initially queue and visited arrays are empty.
Step2: Push node 0 into queue and mark it visited.
Step 3: Remove node 0 from the front of queue and visit the unvisited neighbours and push them into queue.
Step 4: Remove node 1 from the front of queue and visit the unvisited neighbours and push them into queue.
Step 5: Remove node 2 from the front of queue and visit the unvisited neighbours and push them into queue.
Step 6: Remove node 3 from the front of queue and visit the unvisited neighbours and push them into queue.
As we can see that every neighbours of node 3 is visited, so move to the next node that are in the front of the
queue.
Steps 7: Remove node 4 from the front of queue and visit the unvisited neighbours and push them into queue.
As we can see that every neighbours of node 4 are visited, so move to the next node that is in the front of the
queue.
Algorithm:
DFS Algorithm (using either Adjacency Matrix or Adjacency List)
Initialization:
Create a visited array of size V to keep track of visited vertices (initialize all to False).
Define a recursive DFS function that takes the current vertex and the visited array as arguments.
Mark current vertex as visited.
Iterate through all adjacent vertices of the current vertex:
If the neighbor is not visited, call the DFS function recursively for that neighbor.
BFS Algorithm (using Adjacency List)
Initialization:
Create a queue (FIFO data structure) to store vertices to be explored.
Create a visited array of size V to keep track of visited vertices (initialize all to False).
Define a BFS function that takes the starting vertex and the visited array as arguments.
Enqueue the starting vertex and mark it as visited.
While the queue is not empty:
Dequeue a vertex from the queue.
Iterate through all adjacent vertices of the dequeued vertex:
If the neighbor is not visited, enqueue it and mark it as visited.
Software required: g++ / gcc compiler- / 64 bit fedora.
Outcome
Learn object oriented programming features.
Understand & implement different operations on Graph and traversal of DFS and BFS.
Conclusion : Thus we have studied the implementation of various Graph operations
Questions:
1. An undirected graph having n edges, then find out no. Of vertices that graph have?
2. Define data structure to represent graph.
3. What are the methods to display graph.
4. Where you apply directed and undirected grap?
5. What is complexity of your graph to represent it in adjacency matrix and list?
Program Code:
#include <iostream>
#include <list>
#include <queue>
#include <vector>
using namespace std;
class Graph {
int V; // Number of vertices
list<int> *adjList; // Pointer for adjacency list
vector<vector<int>> adjMatrix; // Adjacency matrix
public:
Graph(int V) {
this->V = V;
adjList = new list<int>[V];
adjMatrix.resize(V, vector<int>(V, 0));
}
// Add edge for adjacency list
void addEdgeList(int v, int w) {
adjList[v].push_back(w); // Add w to v’s list.
adjList[w].push_back(v); // Since the graph is undirected
}
// Add edge for adjacency matrix
void addEdgeMatrix(int v, int w) {
adjMatrix[v][w] = 1;
adjMatrix[w][v] = 1; // Since the graph is undirected
}
// DFS utility function
void DFSUtil(int v, vector<bool>& visited) {
visited[v] = true;
cout << v << " ";
// Using adjacency matrix
for (int i = 0; i < V; ++i) {
if (adjMatrix[v][i] && !visited[i]) {
DFSUtil(i, visited);
}
}
}
// DFS traversal
void DFS(int v) {
vector<bool> visited(V, false);
DFSUtil(v, visited);
}
// BFS traversal
void BFS(int s) {
vector<bool> visited(V, false);
queue<int> queue;
visited[s] = true;
queue.push(s);
while (!queue.empty()) {
s = queue.front();
cout << s << " ";
queue.pop();
// Using adjacency list
for (auto adjacent : adjList[s]) {
if (!visited[adjacent]) {
visited[adjacent] = true;
queue.push(adjacent);
}
}
}
}
};
int main() {
Graph g(5); // Create a graph with 5 nodes (0 to 4)
g.addEdgeList(0, 1);
g.addEdgeList(0, 2);
g.addEdgeList(1, 2);
g.addEdgeList(1, 3);
g.addEdgeList(2, 4);
g.addEdgeList(3, 4);
g.addEdgeMatrix(0, 1);
g.addEdgeMatrix(0, 2);
g.addEdgeMatrix(1, 2);
g.addEdgeMatrix(1, 3);
g.addEdgeMatrix(2, 4);
g.addEdgeMatrix(3, 4);
cout << "DFS starting from node 0: ";
g.DFS(0);
cout << "\nBFS starting from node 0: ";
g.BFS(0);
cout << endl;
return 0;
}
