387
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − [[File:Directed acyclic graph 3.svg|right|frame|一個有向無環圖的例子]]+ − 在[[图论]]中，如果一个[[有向图]]从任意[[顶点 (图论)|顶点]]出发无法经过若干条[[邊 (圖論)|边]]回到该[[顶点 (图论)|点]]，则这个图是一个'''有向无环图'''（'''DAG''', '''D'''irected '''A'''cyclic '''G'''raph）。<ref>{{Cite book|title=Introduction to Algorithms|isbn=978-7-111-40701-0|pages=1172|trans-title=算法导论}}</ref> − 因为有向无环图中从一个点到另一个点有可能存在两种路线，因此有向无环图未必能转化成树，但任何有向树均为有向无环图。
无编辑摘要
在数学，特别是<font color="#ff8000">图论</font>和<font color="#ff8000">计算机科学</font>中，有向无环图<font color="#ff8000">DAG 或 dag</font>是一个没有定向循环的有向图。也就是说，它由<font color="#ff8000">顶点Vertex</font>和<font color="#ff8000">边Edge</font>(也称为弧)组成，每条边都从一个顶点指向另一个顶点，沿着这些顶点的方向 不会形成一个闭合的<font color="#ff8000">环Loop</font>。有向图是一个有向无环图当且仅当它可以通过将顶点按照与所有边方向一致的线性顺序排列构成<font color="#ff8000">拓扑排序Topologically ordered</font>。有向无环图有许多科学的和计算的应用，从生物学(进化论，家谱，流行病学)到社会学(引文网络)到计算(调度)。
==定义==
==定义==