dag[圖論名詞]

DAG意思是有向無環圖，所謂有向無環圖是指任意一條邊有方向，且不存在環路的圖。如果有一個非有向無環圖，且A點出發向B經C可回到A，形成一個環。將從C到A的邊方向改為從A到C，則變成有向無環圖。有向無環圖的生成樹個數等於入度非零的節點的入度積。

基本信息

• 中文名：有向無環圖
• 英文名：Directed Acyclic Graph
• 其他外文名：dag

• 特點：任意一條邊有方向，且不存在環路

有向無環圖DAG

算法中有時稱有向無環圖為DAG ( Directed Acyclic Graph)。所謂有向無環圖是指：任意一條邊有方向，且不存在環路的圖。