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.
![undirected graph](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2021/01/undirected-graph.jpg?resize=207%2C225&ssl=1)
![directed graph](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2021/01/directed-graph.jpg?resize=225%2C209&ssl=1)
![weighted graph](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2021/01/weighted-graph.jpg?resize=212%2C225&ssl=1)
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](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2021/01/adjacency-matrix.jpg?resize=602%2C269&ssl=1)
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](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2021/01/adjacency-list.jpg?resize=613%2C174&ssl=1)
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.😎