Graph Algorithms

Here, We will discuss about Graph Algorithms, types of nodes and graphs and also explain Graph Representation like Adjacency Matrix, Adjacency List and Graph Traversals like DFS and BFS.

What is Graph?

A Graph is a flow structure that represents the relationship between various objects. In other words, A graph is a pair (V,E) where V is number of vertices and E is number of edges.

Graph can be visualized by using the following two basic components:

  • Nodes: Nodes are entities whose relationships are expressed using edges.
  • Edges: Edges are the components that are used to represent the relationship between various nodes in a graph.

Types of Nodes in Graph

  • Root Node: The root node is the ancestor of all other nodes in a graph. It does not have any ancestor. Root node has no parent.
  • Leaf Nodes: Leaf nodes represent the nodes that do not have any successors.

Types of Graphs

  1. Undirected Graph: An undirected graph is a graph in which all edges are bi-directional i.e, the edges do not point in any specific direction.
  2. Directed Graph: A directed graph is a graph in which all the edges are uni-directional i.e, the edges point in a single direction.
  3. Weighted Graph: A weighted graph is a graph in which each edge is assigned a weight or cost.
  4. Cyclic Graph: A cyclic graph is a graph in which path that starts from a vertex and ends at the same vertex.

A tree is an undirected graph in which any two vertices are connected by only one path.

A tree cannot contains any cycles or self loops.

undirected graph
directed graph
weighted graph

Graph Representation

Graph can represent in many ways. The two most common ways of representing a graph is as follow:

Adjacency Matrix

An adjacency matrix is 2D array of V*V vertices. Each row and column represent a vertex.

adjacency matrix graph representation

if the values of any elements a[i][j] is 1, it represents that there is an edge connecting vertex i and vertex j.

Adjacency List

An adjacency list represents a graph as an array of linked lists.

adjacency list graph representation

It is efficient in terms of storage because we only need to store the values for the edges.

Graph Traversals

Graph traversal means visiting every vertex and edge exactly once in a well-defined order.

During a traversal, it is important that you track which vertices have been visited. The most common way of tracking vertices is to mark them

There are two such algorithm for traversing the graphs are:

  1. Breadth First Search (BFS)
  2. Depth First Search (DFS)

Want to Contribute:-

If you like “To The Innovation” and want to contribute, you can mail your articles to 📧 contribute@totheinnovation.com. See your articles on the main page and help other coders.😎

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top