Counting incoming edges in a directed acyclic graph

给定一个有向无环图（DAG），是否有一个算法在线性时间运行，计算每个顶点的入度（以及该边的来源），假设我们知道一个根节点（从它开始的一个节点可以到达每个其他顶点）？

---

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.

链接地址: http://www.djcxy.com/p/35284.html

上一篇: 在有向加权图中寻找最短的顶点序列

下一篇: 在有向无环图中计算传入边