查看“︁支配 (圖論)”︁的源代码

{{Other uses|支配}}

{{Multiple issues|
{{copyedit|time=2014-02-15T04:50:33+00:00}}
{{Expert|time=2014-02-15}}
{{Copypaste|time=2022-06-24T06:24:58+00:00}}
{{How-to|time=2022-06-24T06:24:58+00:00}}
{{Tone|time=2022-06-24T06:24:58+00:00}}
}}
{| style="float:right" class=wikitable
|-
! 1 
| dom &nbsp; &nbsp; || {{color|#c0c0c0|1}} || {{color|#800000|2}} || 3 || 4 || 5 || 6
|-
! 2 
| dom ||   || {{color|#c0c0c0|2}} || {{color|#800000|3}} || {{color|#800000|4}} || 5 || {{color|#800000|6}}
|-
! 3 
| dom ||   ||   || {{color|#c0c0c0|3}} ||   ||   ||  
|-
! 4 
| dom ||   ||   ||   || {{color|#c0c0c0|4}} ||   ||  
|-
! 5 
| dom ||   ||   ||   ||   || {{color|#c0c0c0|5}} ||  
|-
! 6 
| dom ||   ||   ||   ||   ||   || {{color|#c0c0c0|6}}
|-
| colspan=8 | 支配关系图
|-
| colspan=8 | {{color|#c0c0c0|灰色节点}} 表示非严格支配
|-
| colspan=8 | {{color|#800000|红色节点}} 表示直接支配
|}
{| style="float:right"
| [[File:Domrel.png|thumb|200px|以1作为开始节点的控制流图实例]]
|}

在[[计算机科学]]中，[[控制流图]]的一个节点（[[基本块]]） '''d''' '''支配'''节点 '''n'''，当且仅当从开始节点（可以理解为源）到节点 '''n'''的每一条路径均要经过节点'''d'''，写作'''d''' dom '''n''' (一写作'''d''' <math>\gg</math> '''n''')。根据上述定义，容易得到每个节点均支配其自身。

一些相關概念：

* 说一个节点 '''d''' 严格支配节点'''n'''，当且仅当 '''d'''支配 '''n''' 而不等于 '''n'''。
* 节点 '''n''' 的直接支配节点（immediate dominator），简称 '''idom''' 是一个独特的节点，它严格支配节点 '''n'''，却不严格支配任何严格支配节点'''n'''的其他节点。不是所有的节点均有直接支配节点，如开始节点就没有。
* 一个节点 '''d''' 的可支配边界是一个点集，其中任意节点n均满足， '''d''' 能支配 '''n''' 的前驱结点，却不能严格支配 '''n'''。就是 '''d''' 支配能力的极限。
* 一个[[支配树]]是一棵[[树 (图论)|树]]，它的所有节点儿子是被其直接支配的所有节点。由于直接支配节点是唯一的，故其为一棵树，开始节点即为树根。
*求解支配树一般使用 Tarjan 算法


== 求解支配树的一般方法 ==
一般而言，会使用 Tarjan 算法在 <math>O(|V|+|E|)</math>的时间内将其求出

=== 大概步骤 ===
首先来介绍一些这个算法的大概步骤

# 对图进行DFS（深度优先遍历）并求出搜索树和DFS序。这里用 <math>dfn[x]</math>表示点 <math>x</math>在dfs序中的位置。
# 根据半必经点定理计算出所有的半必经点作为计算必经点的根据
# 根据必经点定理修正半必经点，求出支配点。

=== 半必經點 ===
用 idom[x] 表示點 <math>x</math>的直接支配节点，用 semi[x] 表示點 <math>x</math>的半必經點。

那什麼是半必經點呢？
 對於一個節點 <math>Y</math>，存在某個點 <math>X</math>能夠通過一系列點 <math>p_i</math>（不包含 <math>X</math>和 <math>Y</math>）到達點 <math>Y</math>且 <math>\forall i \ dfn[i]>dfn[Y]</math>，就稱 <math>X</math>是 <math>Y</math>的半必經點，記做 semi[Y]=X
當然一個點的“半必經點” <math>X</math>會有多個，而且這些半必經點一定是搜索樹中點 <math>X</math>的祖先。

對於每個點，只需要保存其半必經點中最小的一個，下文中用表示點的半必經點中值最小的點的編號。

可以更書面一點的描述這個定理：

* 對於一個節點 <math>Y</math>考慮所有能夠到達它的節點，設其中一個為 <math>X</math>
* 若 <math>dfn[X]<dfn[Y]</math>，則 <math>X</math>是 <math>Y</math>的一個半必經點

* 若 <math>dfn[X]>dfn[Y]</math>，那麼對於 <math>X</math>在搜索樹中的祖先 <math>Z</math>(包括 <math>X</math>)，如果滿足 <math>dfn[Z]>dfn[Y]</math>那麼 semi[Z] 也是 <math>Y</math>的半必經點

== 历史 ==
[[计算机科学]]中支配的概念第一次被提出是在Reese T. Prosser在1959年一篇关于流网络的论文中提出的<ref>{{cite paper 
|last=Prosser 
|first=Reese T. 
|title=Applications of Boolean matrices to the analysis of flow diagrams 
|url=http://portal.acm.org/ft_gateway.cfm?id=1460314&type=pdf&coll=GUIDE&dl=GUIDE&CFID=79528182&CFTOKEN=33765747 
|journal=AFIPS Joint Computer Conferences: Papers presented at the December 1–3, 1959, eastern joint IRE-AIEE-ACM computer conference 
|publisher=ACM 
|location=Boston, MA
|pages=133–138 
|year=1959 }}</ref> 而在此论文中，Prosser并未提出一种有效算法以计算支配关系,解决这一问题的有效算法直到十年后才被 Edward S. Lowry and C. W. Medlock<ref>{{cite paper 
|title=Object code optimization 
|url=http://portal.acm.org/ft_gateway.cfm?id=362838&type=pdf&coll=GUIDE&dl=GUIDE&CFID=79528182&CFTOKEN=33765747 
|journal=Communications of the ACM 
|volume=12 
|issue=1 
|pages=13–22 
|first=Edward S. 
|last=Lowry 
|coauthors=and Medlock, Cleburne W. |date=January 1969}}</ref> 提出。Ron Cytron等人在1989年将其应用于高效计算应用于[[静态单赋值形式]]的φ 函数时对其重新燃起了兴趣。<ref>{{cite paper 
|first=Ron 
|last=Cytron 
|coauthors=Hind, Michael; and Hsieh, Wilson 
|id = {{citeseerx|10.1.1.50.9287}} 
|title=Automatic Generation of DAG Parallelism 
|journal=Proceedings of the ACM SIGPLAN 89 Conference on Programming Language Design and Implementation 
|year=1989 
|pages=54–68 }}</ref>
==参考==
<references />4.https://blog.csdn.net/a710128/article/details/49913553
[[Category:图论]]