Find the Sum of Dependencies in a Graph

🍤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!