Define Graph
A graph is a non-linear data structure that basically consists of two components i.e a node and an edge. The nodes are the fundamental unit of graphs that contain some data. The edge is used to make the connection between the nodes. The edges can connect any two nodes in any possible way.
Types of graph
The types of graphs I have learned so far are:-
Undirected graph:- It is a type of graph in which the edges which connects the nodes are undirectional. The edges do not point to any specific position. So they are non-unidirectional.
Directed graph:- It is a type of graph in which the edges which connects the nodes are directional. The edges point either in the outward or inward direction of that specific node. They are unidirectional. They point towards a single direction only.
Weighted graph:- A graph that has a value associated with every edge. The values corresponding to the edges are called weights. The weight can be any value:- integer, string etc.
Unweighted graph:- A graph in which there is no value or weight associated with the edge. All the graphs are unweighted by default and they will remain unweighted until and unless the user provides some value to the edge.
Complete graph:- A graph is said to be a complete graph if every node is connected to every other node. A complete graph has [n(n-1)/2] edges.
Labeled graph:- A graph is said to be labeled if every edge of the graph is assigned some values.
Connected graph:- A graph is said to be connected if there is a path between any of the two nodes.
Strongly connected graph:- If v and u are two nodes then a graph is said to be strongly connected if there is a path between u node to v node and V node to u node as well.
Application of graph
The application of graphs are:-
Techniques of graphs are used in building a connection or suggesting connections in social media.
Graphs are used in the navigation of airlines or ships.
Graphs are used in communications.
Graphs are used in electronic devices like integrated Circuits.
Degree of graph
In an undirected graph, the degree is calculated by counting the edge emitting or entering the particular node. Or in other words, the number of edges a particular node contains become the degree of that particular node.
In a direct graph, there are two categories of degree:-
Indegree :- The degree is calculated by the number of edges entering/ending into a particular node.
Outdegree:- The degree is calculated by the number of edges emitting/beginning through a particular node.
Sequential Representation of graph
The representation of the graph can be done in two ways:-
Adjacency Matrix:- The adjacency list is a sequential representation . In an adjacency matrix, the connection between the nodes by the edges is represented or determined in a row and column format. It shows the connection of a node with its neighboring node with the help of matrices.
Adjacency List:- Adjacency list is a linked representation . In the adjacency list, for each vertex in the graph, we maintain the list of its neighbors. It means, every vertex of the graph contains a list of its adjacent vertices.
Traversal in graph
Traversal means the processing of nodes in the graph. There are two techniques of traversal:-
Breadth First Search(BFS):- In BreadthFirst Search we use a queue to hold the node. It works on the concept of FIFO (First In First Out). BFS is a traversal approach in which we first traverse through all nodes on the same level before moving on to the next level.
Depth First Search(DFS): - In Depth First Search we use a stack to hold the node. It works on the concept of LIFO(Last In First out). DFS is a traversal approach in which the traverse begins at the root node and proceeds through the nodes.