有向无环图

维基百科,自由的百科全书
跳到导航 跳到搜索
一個有向無環圖的例子

图论中,如果一个有向图从任意顶点出发无法经过若干条回到该,则这个图是一个有向无环图DAG,directed acyclic graph)。[1]

因为有向图中一个点经过两种路线到达另一个点未必形成环,因此有向无环图未必能转化成树,但任何有向树均为有向无环图。

应用[编辑]

参考文献[编辑]

  1. ^ Introduction to Algorithms [算法导论]. : 1172. ISBN 978-7-111-40701-0.