Graph Data Structure

  • A Graph is a non-linear data structure that represents a collection of nodes with connections among them in no particular manner. That means a node can be connected to any number of nodes.

    Difference of a Graph from Tree is that, in a Graph a node can have any number of parent nodes, while a Tree permits only one at max. This means, Graphs can generate closed paths, while a Tree cannot. A Tree is in a way, a subset of a Graph.

    Graph Data Structure

    Graphs are better suited to represent diagrams and maps on a two dimensional or three dimensional surface. Graphs can handle much more complicated structures compared to a tree.

    This also means that data structure operations can become a bit more challenging as well. Algorithms like BFS can still be used for graphs, but with more space and time complexities.

    A Graph is also an Abstract Data Type and mostly uses Linked List data structure to store data. Graphs may require mostly Doubly or Multiple Linked List structure depending on the functionalities.

  • Basic Graph Terminologies

    See below some of the basic terminologies used for a Graph Data Structure.

    1. Vertices/Nodes

      Each vertex of a graph is an individual data storage location, with space reserved to store pointers to other connected vertices.

    2. Arrow/Edge

      This is the link between individual nodes. For directed graphs, we use arrows to represent direction. For undirected graphs, lines are used.

    3. Path

      Path between 2 vertices in a graph is a collection of edges between the two.

    4. Degree

      Degree of a vertex is the total number of child vertices. Degree of a graph is the maximum number of child vertices available for a vertex.

    5. Adjacency

      Two vertices are said to be adjacent, if there is an edge connecting them.

  • Applications of a Graph

    While Trees are useful to represent hierarchical data, Graphs represent any other kind of non-linear data. Usage of graphs are necessary among almost all fields of advanced computing and is among the most important of data structures.

    All kinds of maps and navigation systems that we see online including Google maps uses Graphs.

    Systems that depend on interconnected data, like in the field of AI, Machine Learning or Data Science has lots of uses of Graphs. For example, in Face Recognition software, a face representation is stored as a graph of interconnected nodes on a three dimensional surface.

    Block Chains are essentially a collection of interconnected vertices.

    Artificial Neural Network designs essentially consists of Graphs with millions of connections (edges) among each of the vertices.

    Graphs can be used to represent any kind of diagrams, like in the field of electronics to design chips with large scale connections, implementing 3D printers, develop building plans, etc.

    Social networking sites uses graphs to represent connections between users.

    Image Processing algorithms uses graph data structures.

  • Types of Graphs

    Graphs are classified into different types according to the number of vertices, type of connections, position of vertices, etc. Let us go through some of the most commonly used Graphs structures.

    1. Connected Graph

      A graph is said to be connected if there exists at least one path to reach any of the vertices, starting from any of the vertex in the graph.

    2. Disconnected Graph

      A disconnected graph has more that one group of vertices without having a connections. In such cases, we cannot say that all the nodes can be reached from any point in the graph.

    3. Directed Graph

      A directed graph has edges representing the direction of connection as well. That means the navigation has restrictions in terms of direction and we cannot say that all nodes can be reached from any other node. Helps in faster traversal.

    4. Non-directed Graph

      A graph without specific direction of connection.

    5. Regular Graph

      A regular graph is the one with same degree for all vertices. That is, each node has exactly same number of connections.

    6. Complete Graph

      In a Complete graph, all the nodes are connected to every other node present in the graph. A simple triangle with 3 vertices is a complete graph.

    7. Finite and Infinite Graph

      If we know the number of connections possible in a graph, it is a finite graph. For some structures, like neural network designs there may not be a limit in the number of connections possible for a vertex. Such graphs are known as infinite graphs.

    8. Cyclic Graph

      Each node has exactly 2 connections and a cyclic path is possible among all vertices.

    9. Planar and Non-planar Graph

      Planar graphs can be represented on a two-dimensional plane like representing a group of friends in a social networking site. Non-planar graphs extend beyond a plane, like a map of a town with elevation as well.

    10. Simple, Multi and Pseudo Graph

      If a vertex has a connection to itself, it is known as self connection. If more than one edge is present among two nodes, we call it parallel connected.

      A graph without no self connection or parallel connection is known as Simple Graph. A graph with any parallel connection and no self connection is known as Multi Graph. A graph consisting of self connections is known as Pseudo Graph.

  • Graph Traversal

    Graph Traversal refers to the process of navigating through each of the vertices in a graph. Traversals are required to search for some values within the graphs or to find paths between 2 nodes.

    In Tree Traversal, it is enough to visit one node only once. But in Graphs a node may be required to be visited more than once resulting in more complex algorithms. In general, to traverse, graphs we have two types of Algorithms; Breadth First Search (BFS) and Depth First Search (DFS) Algorithms.

    1. Breadth First Search (BFS)

      Breadth First Search algorithm visits the same level vertices before visiting the child vertices. That means, it traverses left or right side first till the end and backtrack and then move in downward direction and check for nodes in the left or right and continue. A queue is used for BFS.

    2. Depth First Search (DFS)

      Depth First Search algorithm visits the child vertices before visiting the vertices on the same level. That means, it traverses in downward direction first to find all nodes and then backtrack and moves to the left or right side and continue. A stack is generally used to implement DFS.

  • Graphs Based Algorithms

    The basic tasks that are performed on a graph are traversals, search and insert/update/delete. We will see more on these in detail in the upcoming modules.

Absolute Code Works - Python Topics