前趨圖

前趨圖是為了描述一個程式的各部分間的依賴關係，或者是一個大的計算的各個子任務間的因果關係的圖示。

基本介紹

• 中文名：前趨圖
• 外文名：precedence graph
• 類別：物理圖片
• 特點：前趨圖中必須不存在循環

簡介

我們常常採用前趨圖方式。

前趨圖中的每個結點可以表示一條語句、一個程式段或一個進程，結點間的有向邊表示兩個結點之間存

在的偏序（Partial Order）或前趨關係（Precedence Relation）“→”，

→={(Pi,Pj)|在Pj開始前Pi必須完成}

如果（Pi，Pj）∈→，可寫成Pi→Pj，Pi是Pj的直接前趨，Pj是Pi的直接後繼

例如，具有九個結點的前趨圖：

P1為初始結點，P9為終止結點

每個結點還具有一個重量

該前趨圖，存在下面的前趨關係：

P1→P2，P1→P3，P1→P4，P2→P5，P3→P5，

P4→P6，P4→P7，P5→P8，P6→P8，P7→P9，P8→P9；

或表示為：

P={P1,P2,P3,P4,P5,P6,P7,P8,P9}

={(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,P6),(P4,P7),(P5,P8),(P6,P8),(P7,P9),(P8,P9)}

注意

前趨圖中必須不存在循環

　如上圖不是前趨圖。

前趨圖