Last updated on September 4th, 2023 at 09:40 pm
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
- 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.
- 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.
- Weighted Graph: A weighted graph is a graph in which each edge is assigned a weight or cost.
- 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.
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.
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.
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:
Related:
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.😎
