## 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.**

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:

Adjacency Matrix representation of above graph G:

## 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:

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

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.

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

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

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

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

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