Graph in Data Structure: Definition, Types and Application

Last Updated on February 2, 2023 by Prepbytes

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.

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.

What is Graph in Data Structure?

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.

Now vertices and edges might be jargon that can be confusing to beginners so the definition of the two can be said:

1. Vertex: Also referred to as Node, represents the entity or object that is a part of the network that builds a graph data structure.
2. Edge: 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.

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.

Terminologies – Graph Data Structure

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.

Multiple Edges: If two vertices are joined by two or more edges.

Self-Loop: Edge whose endpoints are a single vertex. A vertex being joined with itself result in a self-loop.

Adjacent Nodes: Vertices that are both endpoints of the same edge.

Adjacent Edges: Adjacent edges are two distinct edges that share an end vertex.

Edge Cost: The value that an edge holds to travel to another vertex. It is also known as Edge Weight.
Degree of a Node: The degree of a node states the number of vertexes connected to it.
In-degree of a Node: The number of edges directing inwards on a vertex is called the in-degree of the vertex

Out-degree of a Node: The number of edges directing outwards from a node is called the out-degree of a vertex.
Path: A sequence of nodes connected through edges in a graph data structure is known as a path.
Cycles: A cycle is a path in the graph data structure, that ends at the node right from where it starts.

Representation of Graph Data Structure

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.

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.

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.

Thus the two ways to store and represent the graph data structure can be deduced as

1. Adjacency List
2. Adjacency Matrix

Types of Graph in Data Structure

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:-

Simple Graph
A graph having no more than a single edge between all the adjacent nodes of the graph data structure.

Multigraph
A graph having multiple edges to join the same vertices or nodes.

Undirected Graph
A graph where the adjacent nodes are not directed towards each other.

Directed Graph
A graph where the adjacent nodes are directed towards each other. Also known as Digraph.

Weighted Graph
A graph where the edges or connections between its nodes have an edge cost or weight.

Unweighted Graph
A graph where the edges or connections between its nodes do not have an edge cost or weight.

Connected Graph
A graph in which all the nodes are connected to each other with edges with a single component.

Disconnected Graph
A graph in which all the nodes are not connected to each other with edges making multiple components present in the graph data structure.

Cyclic Graph
A graph that constitutes any cycle where we reach an already visited vertex.

Graph Traversal in Data Structure

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.

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.

Depth-First Search – Graph Data Structure:

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.

Algorithm:

1. Execute recursive function dfs(node):
2. Add node to visited set
3. If the node already visited:
   a. Print node
4. while node has neighbours
   a. Set temp as adjacent node
   b. If temp not in visited set
   • Repeat Step 1

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.

Here we have an undirected graph to travel.

Now A is visited after being popped from the stack and its unvisited neighbour is added to the stack i.e. B

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

Now we have covered a majority portion of the network, we add the nodes left to be traversed, E and D.

E being at the top of the stack will be popped and printed once it is added to the set.

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.

def dfs(graph, source,stack,visited):
    visited.add(source)
    print(source)
    while stack:
        cur = stack.pop()

        for i in graph[cur]:
            if i not in visited:
                stack.append(i)
                dfs(graph,i,stack,visited)
    return True
            

graph = {
    'a':['b','e'],
    'b':['a','c'],
    'c':['b','e','d'],
    'd':['c','e'],
    'e':['a','e','d'],

}
print(dfs(graph,'a',['a'],set()))

Output:

a
b
c
e
d
True

Breadth-First Search – Graph Data Structure:

Another form of search traversal we perform using a queue and move level by level to traverse through the nodes.

Algorithm:

1. Execute recursive function bfs(node):
2. Add node to queue
3. Add node to visited set
4. while the queue is not empty:
   1. Pop front of the queue and assign it to cur
   2. If neighbours of cur are left unvisited
      1. Append neighbour to the rear of queue
      2. Mark neighbour or neighbours as unvisited
   3. Print data kept in cur node

Now, we will be tracing step-by-step how to graph traversal is performed. We add A, the initial node to our queue and pass it to the function.

The source node will be added to the visited set,

With A being popped from the queue to seek its adjacent nodes.

As we pop and add the adjacent nodes, we will print the current node in our output result.

Now, On applying the step to other nodes of the graph data structure.

The remaining nodes C and D will be popped with all the elements being visited in the set. Thus, in this manner, we will end up traversing all the nodes using a breadth-first search.

With this, we get all the nodes in our output successfully.

from collections import deque
def bfs(graph, source,stack,visited):
    visited.add(source)
    q = deque([source])
    while q:
        cur = q.popleft()
        for i in graph[cur]:
            if i not in visited:
                visited.add(i)
                q.append(i)
        print(cur)

    return True
            

graph = {
    'a':['b','e'],
    'b':['a','c'],
    'c':['b','e','d'],
    'd':['c','e'],
    'e':['a','e','d'],

}
print(bfs(graph,'a',['a'],set()))

Output:

a
b
e
c
d
True

Application of Graph in Data Structure

As of now, we have, we have covered a vast portion of graph data structure. Some of the most important application of graph in data structure is as follow-

1. Internet Maps and GPS Services:- Maps are made possible with real-world application of graph data structure. Djikstra Algorithm is used to find the shortest path to reach the destination.

2. Web Search Engine:- The Internet and web search engine are linked with each other with the help of hyperlinks that can be framed as the application of a graph.

3. Biochemical Applications:- Graph data structure has expanded its use in chemical research and biological applications such as protein, signal transduction etc.

4. Social Media:- The use case of Facebook friends and Twitter users is dependent on the usage of graph data structure that defines a relationship between two vertices.

5. Discrete Mathematics:- Graph Data Structure has multiple use cases with Graph Theory being an important subject comprising graph concepts.

6. Solve Puzzle:- Graph data structure is used to solve complex problems that have a single solution such as maze problems.

Conclusion
In this article, we started by looking at how to define graph in data structure and proceeded further looking at the types of graph in data structure, application of graph in data structure, and graph traversal in data structure giving us clarity to the topic.

We hope you liked this article on what is graph in data structure and expect to see you again at PrepBytes with another informative article from our side.

FAQs Related to Graph Data Structure

1. Define graph in data structure / What is graph in data structure?
Graph data structure represents the relationship between nodes connected with the help of edges in a network.

2. What are the two ways to represent Graph Data Structure?
Graph Data Structure can be represented by an adjacency list and adjacency matrix.

3. What are the methods to perform graph traversal in data structure?
Depth First Search and Breadth First are the two methods of graph traversal in data structure.