# Graphs and its applications Study Notes for GATE & Computer Science Engineering Exams

By Mukesh Kumar|Updated : December 4th, 2021

In this article, we are discussing complete study notes on Graph and its applications for the preparation of the GATE Exam, and other competitive Computer Science Engineering Exam.

Graph: A graph is defined as a collection of nodes (known as vertices (in a graph)) and connections between them (known as edges).

Directed Graph: In graph theory, a directed graph is defined as a graph whose edges have direction, then this kind of graph is known as a directed graph or digraph and the edges with direction are known as directed edges or arcs.

Adjacency: If two nodes a,b are connected by an edge in the graph then we say a is adjacent to b.

Path: A path in a graph is defined as a finite or infinite sequence of edges that join a sequence of nodes (vertices).

Loop: A loop may be defined as a path that has same start and end vertex. Or we can say that a path that starts and ends on the same vertex

Connected Graph: In a connected graph there exists a path between every pair of vertices, no node is disconnected.

Acyclic Graph: Acyclic graph is a graph with no cycles.

Weighted Graphs: A weighted graph is defined as a graph whose each edge have some weight (value).

Weight of a Graph: Sum of weights(values) of all edges in a graph is known as weight of the graph.

Connected Components: In an undirected graph, a connected component is defined as a subset of vertices which are mostly reachable from one another. A graph having one connected component known as connected graph, i.e. each vertex is reachable from another.

Subgraph: Subgraph is defined as the subset of vertices and edges that forms a graph.

Tree: Tree is a connected graph without any cycle and loop.

Forest:forest may be defined as an undirected and disconnected, acyclic graph. A disjoint collection of trees is also known as forest. Each component of a forest is tree.

Weakly Connected component: Connected graph which is not strongly connected, i.e some vertex are not connected to every vertex known as  weakly connected graph.

Graph Representations: There are numerous ways of representing a graph:

• Incidence list
• Incidence matrix

Example: Consider the following graph G. Adjacency List representation of above graph G:

• v1: v2, v3, v4, v5
• v2: v1, v3
• v3: v1, v2, v4, v5
• v4: v1, v3, v5
• v5: v1, v3, v4

Adjacency Matrix representation of above graph G: Incidence list representation of above graph G:

`{(1, 2, (1, 5), (1, 3), (1, 4), (4, 5), (3, 5), (3, 4), (2, 3)}`

Incidence matrix representation of above graph G: Graph Traversals: Graph traversals defined as a process of traversing (or searching, reaching) all vertices in graph. If the graph is connected then only we can reach to all vertices of graph. While traversing we will never visits a vertex more than once.

To search a node (or traverse a node) we use bread first search(bfs) and depth first search (dfs) algorithm.

Depth first search (DFS) Algorithm

Step 1: Visit one vertex, you can choose any vertex as the starting node (if start vertex not mentioned in question). And push that vertex to the Stack.

Step 2: find another undiscovered adjacent nodes of the top element of the stack and visit any one of them (in any particular order).

Step 3: Repeat Step 2 until there is no undiscovered vertex(node) left.

Step 4: Pop out the element from the top of the Stack and Repeat Step 2, 3 and 4 till the stack becomes empty.

DepthFirst(Vertex v){

mark v as Visited

for each neighbor w of v {

if (w is not visited){

add edge (v,w) to tree T

DepthFirst(w)

}

}

}

By using DFS traversal, only some edges will be traversed and these edges will form a tree, which will known as depth-first-search tree of graph G, and the edges of this tree are known as tree edges. The edges of G can be described into three parts:

• Back edges points a child node to one of its ancestors in the DFS tree.
• Forward edges point from a node to one of its child or descendants.
• Cross edges point from a node to a previously visited node that is neither its ancestor nor descendant.
Applications of DFS
• To find strongly connected components of graph
• To find bridges in graph
• Minimum spanning tree
• To check if graph has a cycle
• Topological sorting
Analysis of the DFS: The running time complexity of the DFS algorithm is O(|V|+|E|).

### Breadth First Search Algorithm

Step 1: Visit the start vertex (node), you can choose any node as the start node(if it is not given in the question). And add that node into a queue.
Step 2: Repeat the below steps until the queue becomes empty.
Step 3: Remove the head element of the queue and while staying at the vertex, visit all connected vertices and then add them into queue one by one (choose any order to visit all the connected vertices).
Step 4: When you visit all the connected vertices. Repeat Step 3.
`Breadth-First-Search (G) {	initialize a queue Q	unmark all vertices in G	for all vertices a in G {		if (a is unmarked) {			enqueue (Q, a)			while (!empty (Q) {				b = dequeue (Q)				if (b is unmarked) {					mark b					visit b // print or whatever					for all vertices c 						adjacent from b {						enqueue (Q, c)					}				}			}		}	}}`
Applications of BFS
• To find all nodes within one connected component
• To check if graph has a cycle
• Diameter of Tree
• To find shortest path between two nodes u and v
• To test bipartite-ness of a graph
Analysis of BFS: The running time complexity of the BFS algorithm is O(|V|+|E|).

### Graph Applications:

• Electronic circuits
• Route mapping
• Packet routing in Networks

Candidates can also practice 110+ Mock tests for exams like GATE, NIELIT with BYJU'S Exam Prep Test Series check the following link:

## Click Here to Avail GATE CSE Test Series!

Thanks

#DreamStriveSucceed GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303 help@byjusexamprep.com