iisc written

Question

Consider a directed graph with V nodes and E edges. The graph is represented by two arrays, source
src[] and destination dest[] each of size E, such that src[i] and dest[i] represent the nodes
connected by edge, i.
How to calculate the maximum indegree(or out degree)?

Answer 1

for(i = 0; i < V; i++){
        neighbors[i] = 0;
    }
    max_count = 0;

    for(i = 0; i < E; i++){
        neighbors[src[i]]++;
        if(max_count < neighbors[src[i]]){
            max_count = neighbors[src[i]];
            max_node = src[i];
        }
    }    
    printf("Node with max out degree = %d", max node);

Answer 2

Can we go for star Graph all the n-1 vertex pointing towards (in degree) or single vertex pointing all the (n-1) vertex (out degree).

so the array max(dest[]) will tell us about the in degree and max(src[])  will tell us about the out degree.

(i am taking the example as vertex =0 which is 0 location in both the array have some value which correspond to the number of vertex it point for destination and for source it contain the total vertex which point towards the known place vertex).