如何找到有向无环图的根

Question

我需要一个方法来查找有向无环图的根.我使用布尔邻接matix来表示java中的图.所以请建议.图也是未加权的图

Answer 1

只需找到indegree为0的节点.对于下面的算法,我们假设图中没有任何节点被隔离.

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;
}