?? chapter1_3.htm
字號:
<html>
<!-- #BeginTemplate "/Templates/article_template.dwt" -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="keywords" content="algorithm, data structure, contest, programming, 算法, 數據結構, 程序設計, 競賽">
<meta name="description" content="discussing the algorithm and data structure of computer programming, as well as all kinds of programming contest.">
<meta name="description" content="討論程序設計的算法與數據結構，各類程序設計競賽試題解析和參賽經驗介紹。">
<!-- #BeginEditable "doctitle" -->
<title>算法與數據結構 -- 歐拉回路技術</title>
<!-- #EndEditable -->
<script id="header" language="JavaScript" src="../../lib/header.js"></script>
<!-- #BeginEditable "javascript" -->
<script language="JavaScript">
previous = "chapter1_2.htm";
next = "chapter2.htm";
contents="";
topic="并行算法——指針轉移";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content"> <!-- #BeginEditable "MainContent" -->
<h3>1.3 歐拉回路技術</h3>
<p>在本節中，我們將介紹歐拉回路技術，并說明如何運用這一技術在n個結點的二叉樹中計算出每個結點的深度。在這個O(lgn)時間的EREW算法中，關鍵的一步就是并行前綴計算。</p>
<p>為了在PRAM中存儲二叉樹，我們采用了簡單的二叉樹表示法。每個結點i有三個域parent[i],left[i],right[i]，分別指向結點i的父母、左子女和右子女。假定每個結點用一個非負整數來表示。我們為每個結點聯接三個而不是一個處理器，其原因我們在下面將會明白。稱這三個處理器為結點的A，B和C處理器，我們可以很容易地在結點與其三個處理器之司找出對應關系。例如，結點i可以與處理器3i，3i+1和3i+2相聯接。</p>
<p>在串行RAM上，計算包含n個結點的樹中每個結點的深度所需運行時間為O(n)。采用一種簡單的并行算法來計算結點深度時，算法可以從樹的根結點開始把一種“波”向下傳輸。這種波同時到達深度相同的所有結點，因此通過對波載計數器增值，我們就能計算出每個結點的深度。這種并行算法對完全二叉樹很適用，這是因為其運行時間與樹的高度成正此。而樹的高度最大為n-1，這時算法的運行時間為O(n)，這并不優于串行算法。但是，如果我們運用歐拉回路技術，不論樹的高度是多少，都能夠在EREW
PRAM上用O(lgn)的運行時間計算出結點的深度。</p>
<p>一個圖的歐拉回路是通過圖的每條邊一次一個回路，當然，在此過程中它可以多次訪問一個結點。根據圖論算法可知，一個有向連通圖具有歐拉回路當且僅當對所有結點v，v的出度等于v的入度。因為無向圖每條無向邊(u，v)對應于相應的有向圖中的兩條邊(u，v)和(v，u)，因此任何無向連通圖改成的有向圖均包含歐拉回路，這對無向樹也自然成立。</p>
<p align="center"><img border="0" src="images/fig4a.gif" width="504" height="386"></p>
<p align="center">(a)</p>
<p align="center"><img border="0" src="images/fig4b.gif" width="504" height="386"></p>
<p align="center">(b)<br>
</p>
<p align="center">圖4 運用歐拉回路技術來計算每個結點在二叉樹中的深度</p>
<p>為了計算二叉樹T中結點的深度，首先在改寫的有向樹T中形成一個歐拉回路。該回路對應于樹的遍歷過程，如圖4(a)所示，它可以用一個連接樹中所有結點的鏈表來表示。其結構如下：</p>
<ul>
<li>如果結點的左子女存在，則結點的A處理器指向其左子女的A處理器，否則就指向自身的B處理器。</li>
<li>如果結點存在右子女，則結點的B處理器指向其右子女的A處理器，否則就指向其自身的C處理器。</li>
<li>如果一個結點是其父母結點的左子女，則結點的C處理器指向其父母的B處理器，如果該結點是其父母結點的右子女，則結點的C處理器指向其父母的C處理器。根結點的C處理器指向NIL。</li>
</ul>
<p>因此，根據歐拉回路形成的鏈表的表頭是根結點的A處理器，表尾是根節點的C處理器。如果已知構成原始樹的指針，則我們可以在O(1)的時間內構造出歐拉回路。</p>
<p>在我們獲得表示T的歐拉回路的鏈表后，我們在每個A處理器中放入值1，在每個B處理器中放入值0，在每個C處理器中放入值-1，如圖4(a)所示。然后如第1.2節中那樣，我們運用滿足結合律的普通加法來執行并行前綴計算。圖4(b)說明了并行前綴計算的結果。</p>
<p>我們說，在執行完并行前綴計算過程后，每個結點的深度值在結點的C處理器中。為什么呢？我們按以下要求把數放入A，B和C三個處理器中：訪問子樹的最后結果是把運行和加上0。每個結點i的A處理器對其左子女樹的運行和加1，這表明i的左子女的深度比i的深度大1。B處理器對運行和沒有影響，這是因為i的左子女的深度與其右子女的深度相等。C處理器使運行和減1，以便對i的父母結點來說，對以i為根結點的子樹進行訪問后運行和不會改變。</p>
<p>我們可以在O(1)的時間內計算出表示歐拉回路的列表。列表中包含3n個對象，所以執行并行前綴計算過程僅需O(lgn)的運行時間。因此，計算所有結點深度所花費的全部運行時間為O(lgn)。又因為算法執行中不需要對有存儲器執行并發存取操作，所以該算法是一個EREW算法。</p>
<!-- #EndEditable --> </div>
<script src='../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate -->
</html>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -