在有向无环图中计算传入边
给定一个有向无环图（DAG），是否有一个算法在线性时间运行，计算每个顶点的入度（以及该边的来源），假设我们知道一个根节点（从它开始的一个节点可以到达每个其他顶点）？
假设您的节点从1到n编号。 有一个简单的解决方案：创建一个大小为n的数组D，其值初始化为0.然后遍历所有边（v，w）并将D [w]递增1。 最后，D [w]将是顶点w的入度。
链接地址: http://www.djcxy.com/p/35283.html
给定一个有向无环图（DAG），是否有一个算法在线性时间运行，计算每个顶点的入度（以及该边的来源），假设我们知道一个根节点（从它开始的一个节点可以到达每个其他顶点）？
假设您的节点从1到n编号。 有一个简单的解决方案：创建一个大小为n的数组D，其值初始化为0.然后遍历所有边（v，w）并将D [w]递增1。 最后，D [w]将是顶点w的入度。
链接地址: http://www.djcxy.com/p/35283.html