Data Structure - Introduction To Graphs

          A Beginners Introduction to Graphs Data Structure

Graphs are a non-linear data structure used widely in technical world applications to solve real-world problems. Graphs are basically the collection of nodes (vertices) and edges.

• Google search, Google Maps, even social media sites use Graphs data structures to solve problems.

• These data structures are so powerful that you won't even imagine how diverse their real-world applications can be.

          
    Real-world Applications:-

• GPS System and Google Maps use graphs to find the shortest path from one destination to other.
• Social Networks use graphs to represent connections between users.
• The Google Search Algorithm uses graphs to determine the relevance of the search result.
• Chemistry uses graphs to represent molecules.

         

                                 GRAPH SUB-OPERATIONS

Graphs are used to represent, find, analyze and optimize the connection between elements(houses, users, articles, etc.)

 There are two main elements in a graph's nodes and edges.

                                                                  Fig:-1   Graph

• Nodes:- they are the elements that create the network. Anything that you could represent as being connected to other similar elements in the network.
• Edges:- they are connections between the nodes. They could represent streets, a connection between two users in a social network.

       If there is no connection:-  If two nodes are not connected by an edge, that means there is no direct connection between them.

You might still be able to go from one node to another by following a sequence of edges, similar to driving through several streets to reach your final destination.

For example in the diagram below, even though there is no direct connection(edge) between the purple node (left) and yellow node (right), you can go from the purple node to orange node, to the Pink node, to the green node and finally reach the yellow node.

                         Fig:-2 No direct connection between the purple and yellow node

      💥 NOTATION AND TERMINOLOGY:

           It's very important to learn the formal language to work with graphs.

•             |V| = Total number of vertices (nodes) in the graph.
•           |E| = Total number of connections (edges) in the graph.

                                       🍁🍁 TYPES OF GRAPHS 🍁🍁

1. Directed Graphs

 In a directed graph, edges have a direction. They go from one node to another, and there is no way to return to the initial node through that edge.

In a directed graph, you may not be able to return at all to your initial location if there is no path with the appropriate directions.

                                                   Fig:-3 Directed Graph

  2. Undirected Graphs

     In this type of graph, edges are undirected( they do not have a specific direction). Think of undirected edges as two-way streets. You can go from one node to another and return through the same path.

                                                      Fig:- 4 Undirected Graph

Whenever you see a diagram of a graph where the edges don't have arrows pointing in a specific direction, you can assume that the graph is undirected.