CODEWITHSUNDEEP
algorithmdirected-acyclic-graphs
TheNotMe
TheNotMe

Reputation: 1058

Counting incoming edges in a directed acyclic graph

Given a directed acyclic graph (DAG), is there an algorithm that runs in linear time that counts the in-degree of each vertex (and the source of that edge), given that we know a root node (a node that from it you can reach every other vertex)?

Upvotes: 0

Views: 2186

Answers (2)

Rishi Kumar
Rishi Kumar

Reputation: 1

This may be the answer to your problem:

public List<Integer> findIndegree(int n, List<List<Integer>> edges)
{
    List<Integer>as = new ArrayList<>();
    int[]in_deg = new int[n];
    for(int u=0;u<n;u++)
    {
        for(int x:edges.get(u))
            in_deg[x]++;
    }}

Here the array in_deg is storing the degree of the variables.

Upvotes: 0

Niklas B.
Niklas B.

Reputation: 95308

Let's assume your nodes are numbered from 1 to n. There's a simple solution: Create an array D of size n, with values initialized to 0. Then walk through all edges (v, w) and increment D[w] by one. In the end D[w] will be the in-degree of vertex w.

Upvotes: 1

Related Questions