{"id":11978,"date":"2023-01-30T07:34:50","date_gmt":"2023-01-30T07:34:50","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=11978"},"modified":"2023-02-02T05:37:30","modified_gmt":"2023-02-02T05:37:30","slug":"graph-in-data-structure","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/graph-in-data-structure\/","title":{"rendered":"Graph in Data Structure: Definition, Types and Application"},"content":{"rendered":"

\"\"<\/p>\n

In this article, we are going to study what is graph in data structure, the types of graph in data structure, the application of graph in data structure and also the techniques to perform graph traversal in data structure in the types of graph in data structure.<\/p>\n

We will start by looking out to define graph in data structure and progress step by step with all the sections discussed in a graph, which proves to be one of the most important data structures in terms of the application of graph in data structure.<\/p>\n

What is Graph in Data Structure?<\/h2>\n

We can define a graph in data structure that represents relationships between the objects that are a part of the graph data structure. It can be assumed as a flow structure that has networks in between them with the help of vertices and edges.<\/p>\n

\"\"<\/p>\n

Now vertices and edges might be jargon that can be confusing to beginners so the definition of the two can be said:<\/p>\n

1. Vertex:<\/strong> Also referred to as Node, represents the entity or object that is a part of the network that builds a graph data structure.
\n2. Edge:<\/strong> The connection between the vertex, or nodes, can be defined as an edge. A graph has multiple edges joining or connecting the vertices to each other.<\/p>\n

A general example can be Facebook where two individuals can befriend each other making it a two-way mutual connection that can be relative to an Undirected Graph unlike in Twitter or Instagram where an individual can follow the other individual irrespective of the other individual following which resembles a directed graph.<\/p>\n

Terminologies – Graph Data Structure<\/h3>\n

Now that we have some idea of seeing what is graph in data structure and how we can define a graph in data structure. Let us look at some of the important terminologies in a graph.<\/p>\n

Multiple Edges:<\/strong> If two vertices are joined by two or more edges. <\/p>\n

Self-Loop:<\/strong> Edge whose endpoints are a single vertex. A vertex being joined with itself result in a self-loop.<\/p>\n

Adjacent Nodes:<\/strong> Vertices that are both endpoints of the same edge.<\/p>\n

Adjacent Edges:<\/strong> Adjacent edges are two distinct edges that share an end vertex.<\/p>\n

Edge Cost:<\/strong> The value that an edge holds to travel to another vertex. It is also known as Edge Weight.
\nDegree of a Node:<\/strong> The degree of a node states the number of vertexes connected to it.
\nIn-degree of a Node:<\/strong> The number of edges directing inwards on a vertex is called the in-degree of the vertex<\/p>\n

Out-degree of a Node:<\/strong> The number of edges directing outwards from a node is called the out-degree of a vertex.
\nPath:<\/strong> A sequence of nodes connected through edges in a graph data structure is known as a path.
\nCycles:<\/strong> A cycle is a path in the graph data structure, that ends at the node right from where it starts.<\/p>\n

Representation of Graph Data Structure<\/h2>\n

Graphs can be represented in multiple ways. In case the nodes are sparse, an adjacency list or adjacency set seems to be a good option else an adjacency matrix can be used to store the connections in an n*n matrix denoting all the nodes that are connected.<\/p>\n

To store the weight of edges, the adjacency matrix can store the weight in A[i][j] between adjacent nodes where A is the matrix and i,j being the nodes that are connected to each other.<\/p>\n

In the case of an adjacency list, a tuple consisting of weight as well as the connected node can be an alternative to simply connected nodes being stored in the adjacency list.<\/p>\n

Thus the two ways to store and represent the graph data structure can be deduced as<\/p>\n

    \n
  1. Adjacency List<\/li>\n
  2. Adjacency Matrix<\/li>\n<\/ol>\n

    Types of Graph in Data Structure<\/h2>\n

    Getting the necessary terminologies and understanding what is graph in data structure, for this section, we proceed to look at the different types of graph in data structure. As we explore our way of looking at them below:-<\/p>\n

    Simple Graph<\/strong>
    \nA graph having no more than a single edge between all the adjacent nodes of the graph data structure.<\/p>\n

    \"\"<\/p>\n

    Multigraph<\/strong>
    \nA graph having multiple edges to join the same vertices or nodes.<\/p>\n

    \"\"<\/p>\n

    Undirected Graph<\/strong>
    \nA graph where the adjacent nodes are not directed towards each other. <\/p>\n

    \"\"<\/p>\n

    Directed Graph<\/strong>
    \nA graph where the adjacent nodes are directed towards each other. Also known as Digraph.<\/p>\n

    \"\"<\/p>\n

    Weighted Graph<\/strong>
    \nA graph where the edges or connections between its nodes have an edge cost or weight.<\/p>\n

    \"\"<\/p>\n

    Unweighted Graph<\/strong>
    \nA graph where the edges or connections between its nodes do not have an edge cost or weight.<\/p>\n

    \"\"<\/p>\n

    Connected Graph<\/strong>
    \nA graph in which all the nodes are connected to each other with edges with a single component.<\/p>\n

    \"\"<\/p>\n

    Disconnected Graph<\/strong>
    \nA graph in which all the nodes are not connected to each other with edges making multiple components present in the graph data structure.<\/p>\n

    \"\"<\/p>\n

    Cyclic Graph<\/strong>
    \nA graph that constitutes any cycle where we reach an already visited vertex.<\/p>\n

    \"\"<\/p>\n

    Graph Traversal in Data Structure<\/h2>\n

    Graph Traversal in Data Structure can be performed in certain ways available at our disposal. We can use a breadth-first traversal that is based on a queue data structure or a depth-first traversal based on the stack-based data structure.<\/p>\n

    The major tweak between the tree and graph is that we maintain a visited set in the graph to avoid revisiting a node. A node in a tree is free from being revisited as there are no cycles in it.<\/p>\n

    Depth-First Search – Graph Data Structure:<\/h3>\n

    Let us perform a depth-first search step by step on a tree using a stack, we print the values one by one along with the algorithm used to perform the technique.<\/p>\n

    Algorithm:<\/strong><\/p>\n

      \n
    1. Execute recursive function dfs(node):<\/li>\n
    2. Add node to visited set<\/li>\n
    3. If the node already visited:
      \na. Print node<\/li>\n
    4. while node has neighbours
      \na. Set temp as adjacent node
      \nb. If temp not in visited set<\/p>\n
        \n
      • Repeat Step 1<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n

        We will be looking in a step-by-step manner to trace the working of depth first traversal in this article on what is graph data structure in data structure.<\/p>\n

        \"\"<\/p>\n

        Here we have an undirected graph to travel.<\/p>\n

        \"\"<\/p>\n

        Now A is visited after being popped from the stack and its unvisited neighbour is added to the stack i.e. B<\/p>\n

        \"\"<\/p>\n

        With A already visited by B, we only add the C node to our stack maintained to tackle the graph traversal in data structure.<\/p>\n

        \"\"<\/p>\n

        Now we have covered a majority portion of the network, we add the nodes left to be traversed, E and D.<\/p>\n

        \"\"<\/p>\n

        E being at the top of the stack will be popped and printed once it is added to the set.<\/p>\n

        \"\"<\/p>\n

        As the last node in the stack, D is popped and the stack becomes empty, we have printed the required result leading to the termination and successful traversal.<\/p>\n\t\t\t\t\t\t