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

By Mukesh Kumar|Updated : December 4th, 2021

Graphs are a fundamental data structure used in computer science and have a wide range of applications. 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.

A graph is a collection of nodes (vertices) connected by edges. Graphs are used to model relationships between objects, and they can be used to represent a wide variety of data, including social networks, computer networks, road maps, and more. Read on to get Graph and its applications study notes for the GATE exam.

Table of Content

Graphs and its Applications

There are several types of graphs commonly used in Computer Science, including Undirected Graphs, Directed Graphs, Weighted Graphs, Bipartite Graphs, Trees, Spanning Trees, Planar Graphs, and Hypergraphs. The choice of graph type depends on the specific problem being solved and the properties of the data being represented. Graphs have numerous applications, including network analysis, algorithm design, data mining and machine learning, image processing, computational geometry, computer graphics, and database systems.

Before we move on to Graph and its applications, Here are some of the important terms related to Graphs you should know:

  • 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, and 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 the 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 has some weight (value).
  • Weight of a Graph: The sum of weights(values) of all edges in a graph is known as the 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 is known as a connected graph, i.e. each vertex is reachable from another.
  • Subgraph: A subgraph is defined as the subset of vertices and edges that forms a graph.
  • Tree: A tree is a connected graph without any cycle or loop.
  • Forest: A forest may be defined as an undirected and disconnected, acyclic graph. A disjoint collection of trees is also known as a forest. Each component of a forest is a tree.
  • Weakly Connected component: Connected graph which is not strongly connected, i.e. some vertex is not connected to every vertex is known as a weakly connected graph.

Graph Representations

There are several ways to represent graphs, each with its own advantages and disadvantages. Here are some of the most common graph representations:

  • Incidence list
  • Incidence matrix
  • Adjacency List
  • Adjacency Matrix

Example: Consider the following graph G.

byjusexamprep

 

Incidence list representation of above graph G:

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

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

Incidence matrix representation of above graph G:

byjusexamprep

Adjacency Matrix representation of above graph G:

byjusexamprep

Graph Traversals

Graph traversals are defined as a process of traversing (or searching, reaching) all vertices in a graph. If the graph is connected then only we can reach all vertices of a graph. While traversing we will never visit a vertex more than once.

To search a node (or traverse a node) we use breadth-first search(bfs) and depth-first search (dfs) algorithms.

Depth-First Search (DFS) Algorithm

In DFS, the search algorithm starts at a node and explores as far as possible along each branch before backtracking. This means that the algorithm explores the deepest parts of the graph first. DFS can be implemented using recursion or a stack data structure.

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

Step 2: Find another undiscovered adjacent node 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 be known as the 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 in three parts:

  • Back edges point 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 a graph
  • To find bridges in the graph
  • Minimum spanning tree
  • To check if the 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 (BFS) Algorithm

In BFS, the search algorithm starts at a node and explores all the neighbours of that node before moving on to the neighbours' neighbours. This means that the algorithm explores the graph layer by layer. BFS can be implemented using a queue data structure.

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 the queue one by one (choose any order to visit all the connected vertices).Step 4: When 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 the graph has a cycle
  • Diameter of Tree
  • To find the shortest path between two nodes u and v
  • To test the bipartite-ness of a graph

Analysis of BFS: The running time complexity of the BFS algorithm is O(|V|+|E|).

Graph Applications

Graph and its applications are an important topic for all CSE exams. Some of the applications of graphs in computer science include:

  1. Network analysis: Graphs are used to represent and analyze networks of all kinds, including computer networks, social networks, and transportation networks.

  2. Algorithm design: Graphs are often used in the design of algorithms, such as pathfinding algorithms, which find the shortest path between two nodes in a graph.

  3. Data mining and machine learning: Graphs are used in data mining and machine learning to represent data and extract patterns from it.

  4. Image processing: Graphs are used in image processing to represent and analyze images.

  5. Computational geometry: Graphs are used in computational geometry to represent geometric objects and solve geometric problems.

  6. Computer graphics: Graphs are used in computer graphics to represent and manipulate objects and scenes.

  7. Database systems: Graphs are used in database systems to represent data and relationships between data.

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

Comments

write a comment

FAQs

  • A graph is a mathematical concept that represents a set of objects (called vertices or nodes) and the connections between them (called edges). Graphs can be used to model various real-world systems, such as social networks, transportation systems, and computer networks. They are a powerful tool for analyzing complex systems and solving optimization problems.

  • The 3 applications of Graph Theory include Network analysis, Machine Learning and Optimization.

  • The real-life applications of Graphs are:

    1. Social networks: Graphs can be used to model social networks such as Facebook, Twitter, and LinkedIn.
    2. Transportation systems: Graphs are used to model transportation systems such as highways, railways, and airline routes.
    3. Computer networks: Graphs are used to model computer networks such as the Internet and peer-to-peer networks.
  • There are several types of Graphs, including:

    1. Undirected graph: A graph where the edges do not have a direction.
    2. Directed graph: A graph where the edges have a direction.
    3. Weighted graph: A graph where the edges have a weight or value assigned to them.
    4. Bipartite graph: A graph where the vertices can be divided into two sets, and all edges connect vertices from different sets.
    5. Complete graph: A graph where every pair of vertices is connected by an edge.
    6. Tree: A graph where there is only one path between any two vertices.
  • BFS and DFS are two algorithms used to traverse a graph and visit all its nodes or vertices.

Follow us for latest updates