Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
🍤Introduction
2.
🍤Problem Statement
2.1.
🍤Example
3.
🍤Algorithm
4.
🍤Implementation
5.
🍤Explanation
6.
Frequently Asked Questions
6.1.
What is a dependency graph?
6.2.
How to determine whether there is a dependency in a graph?
6.3.
What is the use of a dependency graph?
6.4.
How to find the sum of dependencies in a graph?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Find the Sum of Dependencies in a Graph

Author Rashi
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

🍤Introduction

directed graph representing how the nodes are connected/dependent on each other is called a dependency graph, i.e., representing dependencies of several objects towards each other. 

Find the sum of Dependency in a graph

A dependency graph can be used to establish dependencies between tasks, allowing us to specify the sequence in which they should be finished and which tasks must be finished before others can be released.

🍤Problem Statement

We are given a directed and connected graph with 'n' nodes.  If an edge exists from u to v in the graph, then u depends on v. The function should return the sum of dependencies in the given graph.

Input: An integer ‘n’, where n describes the number of nodes and ‘e’ which describe the number of edges. 

Output: An integer s that represents the sum of dependencies in the graph.

🍤Example

Sum of Dependency in a Graph

 

For the graph mentioned above,

  • P depends on Q and R, i.e.dependency is equal to 2
     
  • Q depends on R, i.e. 1
     
  • S depends on R, i.e. 1
     
  • And R depends on none.
     

Thus the sum of dependency of the above graph is, 2 + 1 + 1 + 0 = 4.

Solve this problem and learn how to find the sum of dependencies in a graph.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

🍤Algorithm

  1. Firstly check the adjacency list.
     
  2. Then, find how many edges are there from each vertex.
     
  3. Return the total number of edges.

🍤Implementation

🥢C++

/* Program to find the sum of dependencies */
#include <bits/stdc++.h>
using namespace std;

/* function to add an edge in graph */
void addEdge(vector <int> adj[], int u, int v)
{
    adj[u].push_back(v);
}

/* function to find the sum of all dependencies */
int findSum(vector<int> adj[], int V)
{
    int sum = 0;

    /* find the size at each vector's
          index and sum it */
   for (int u = 0; u < V; u++)
   sum += adj[u].size();

    return sum;
}

/* Driver code of main function */
int main()
{
    int V = 4;

   /* create adjacency list */
    vector<int >adj[V];
    addEdge(adj, 0, 2);
    addEdge(adj, 0, 3);
    addEdge(adj, 1, 3);
    addEdge(adj, 2, 3);

     /* print the sum */
    cout << "Sum of dependencies is " << findSum(adj, V);
    return 0;
}

 

Output: 

Sum of dependencies is 4.

 

🥢Python

# Program to find the
# sum of dependencies

# function to add an edge
def addEdge(adj, u, v):
    adj[u].append(v)

# function to find 
#the sum of all dependencies
def findSum(adj, V):
    sum = 0
    # Just find the size at each vector's index
     # And sum it
    for u in range(V):
        sum += len(adj[u])
    return sum

# Driver code
if __name__=='__main__':
    V = 4
     # Create adjacency list
    adj = [[] for i in range(V)]
    addEdge(adj, 0, 2)
    addEdge(adj, 0, 3)
    addEdge(adj, 1, 3)
    addEdge(adj, 2, 3)
    print("Sum of dependencies is", findSum(adj, V))

 

Output: 

Sum of dependencies is 4

🍤Explanation

  1. Let us have the adjacency list representation of this graph.
     
  2. We pass the adjacency list and number of vertices 4 to the findSum function.
     
  3. Next, we take a sum variable and initialize it to 0.
     
  4. Now, we run a for loop from 0 to the number of vertices that is 4. And find the size of each vertex’s list and add it to the sum.
     
  5. So, first, u will be 0 since the size of the adjacency list of 0 is 2, and we add 2 to the sum. Hence, now, the sum will be equal to 2.
     
  6. Next, u becomes 1. Since the size of the adjacency list of 1 is 1, we add 1 to the sum. Then, u become 2. Again, as the size of the adjacency list of 2 is 1, we add 1 to the sum. Then, u become three since the adjacency list of 3’s size is 0.
     
  7. The sum remains 4; we come out of the for loop and return 4. So, the Sum of dependencies for this graph is 4.

 

Time Complexity: O(V), where V is the number of vertices in the graph.

Space Complexity: O(1)
Check out this problem - Subarray Sum Divisible By K

Frequently Asked Questions

What is a dependency graph?

A directed graph that represents the dependencies of several objects toward each other is a dependency graph.

How to determine whether there is a dependency in a graph?

In a graph, if there is an edge from u to v, then u depends on v.

What is the use of a dependency graph?

A dependency graph can be used to establish dependencies between tasks, allowing us to specify the sequence in which they should be finished and which tasks must be finished before others can be released.

How to find the sum of dependencies in a graph?

Check the adjacency list, find how many edges are there from each vertex, and return the total number of edges. 

Conclusion

In this article, we have thoroughly discussed what dependency graphs are, their applications, and an example to understand them. We have also implemented the code to find the Sum of Dependencies in a Graph in C++ and Python.

You can refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Happy Learning!

Previous article
Find the Shortest Path in a Weighted Graph where the Weight of an Edge is 1 or 2
Next article
Minimum Cost Path in a Directed Graph via a Given Set of Necessary Nodes
Live masterclass