how to find root of a directed acyclic graph

algorithm, data-structures, directed-graph, graph-algorithm

Solution

Just find the node where indegree is 0. For below algorithm to work we assume that none of nodes in graph are isolated.

int indegree[N]={0};

for(i=0;i<n;++i){
  for(j=0;j<n;++j){
      if(graph[i][j]==1){ //assuming edge from i to j
           indegree[j]++;
      }
  }
}
for(int i=0;i<n;++i){
   if(indegree[i]==0) add i to roots;
}

Problem

I need a method to find root of a directed acyclic graph.I am using boolean adjancency matix to represent graph in java.so please suggest.Also graph is unweighted graph

Original source