沙宗堯 邊馥苓

摘要:數(shù)據(jù)結(jié)構(gòu)和算法的教學是計算機科學與技術(shù)、軟件工程等相關(guān)專業(yè)最重要的教學內(nèi)容之一,特別是在復雜的算法分析時,由于具有抽象性和較強的邏輯性,不采用好的教學方法,往往是事倍功半。本文提出用圖示教學法教授數(shù)據(jù)結(jié)構(gòu)中的算法,并以圖狀結(jié)構(gòu)中的最小生成樹算法為例,詳細介紹了該圖示方法描述數(shù)據(jù)結(jié)構(gòu)算法過程,可以為數(shù)據(jù)結(jié)構(gòu)的教學提供參考。

關(guān)鍵詞:數(shù)據(jù)結(jié)構(gòu);算法;圖示教學法;最小生成樹

中圖分類號:G642 文獻標識碼:B

1背景

數(shù)據(jù)結(jié)構(gòu)和算法是計算機科學與技術(shù)、軟件工程等相關(guān)專業(yè)的專業(yè)基礎課,其重要性不言而喻,在教學過程中需要運用多種教學方法,讓學生領(lǐng)會算法實現(xiàn)的過程和本質(zhì),加深對所學知識的理解、記憶和應用。在數(shù)據(jù)結(jié)構(gòu)和算法課程教學中,圖狀結(jié)構(gòu)的教學是一個難點,特別是涉及到圖的具體應用時,更讓學生難以掌握,本文將圖示教學法應用到數(shù)據(jù)結(jié)構(gòu)中關(guān)于圖狀結(jié)構(gòu)的一個典型應用——最小生成樹問題,給出該教學方法的基本方法和過程,取得了良好的教學效果。

最小生成樹是圖狀(網(wǎng)絡)結(jié)構(gòu)中一個典型的實踐應用,可以解決實際中諸如公路網(wǎng)的規(guī)劃,即在n個城市中,如何規(guī)劃n-1條公路,使得n個城市都可以連接起來,而所有城市間的連接線長度的總和最短(所要修建的公路長度最短,因而費用最少)。

對于這個典型的應用,絕大多數(shù)教科書均介紹了普里姆(Prim)算法,用于求最小生成樹問題,然而教科書對這個算法實現(xiàn)的論述,一般是先介紹應用背景,然后就給出算法實現(xiàn)的過程,缺少形象的算法分析過程,課堂教學講解如果按照這種方式去傳授,學生在理解上十分吃力,而且不能有效地長期記憶。筆者結(jié)合自己在教學中的經(jīng)驗,將以上算法采用了圖示教學法來分析其基本原理和實現(xiàn)過程,并給出算法實現(xiàn)過程,取得了良好的效果。

2教學方法

圖示教學法就是用各種圖形表示的方法描述問題、引導學生的思考,增強對新知識的記憶,并在教學中被廣泛使用。最小生成樹屬于網(wǎng)絡的實踐應用,下面以圖1為例,用圖示教學法來對最小生成樹算法進行圖示過程分析。

假設某一區(qū)域內(nèi)有n個城市,現(xiàn)要為這些城市修建城間公路,使得任意兩城市間都能夠相互通達(連通),由于要求所有的城市都在該公路網(wǎng)上,某兩個城市間的道路稱為一個路段,則修建的道路路段總數(shù)應等于n-1個(容易理解:如果路段總數(shù)小于n-1,則會有存在城市不能處在該道路網(wǎng)的節(jié)點上;如果路段總數(shù)大于n-1則會存在某兩個城市間有至少兩個路段,則路段距離的總和將不是最小),先從這些城市中任選一個作為種子,把剩下的城市用路段連接到由該種子城市為起始點的城市網(wǎng)絡中,保證路段長度總和最小(最優(yōu)路段網(wǎng)),則最后連接好的路段即為最小生成樹。

如圖1,每個帶圈的數(shù)字表示一個城市,城市間的邊表示城市間的距離,如果兩城市間沒有邊存在,則表示這兩個城市間不適宜修道路(如有山脈或河流隔斷,造價太高),假設種子城市為數(shù)字1(選定的網(wǎng)絡的起始頂點),通過圖示教學法求最優(yōu)路段網(wǎng)的過程如圖2:

圖中,Li-j表示城市i與城市j間的距離,例如在(b)中,當把城市2加入到最優(yōu)路段網(wǎng)后,城市3、4、6與該最優(yōu)路段網(wǎng)的距離發(fā)生了變化,例如城市3,由于由L1-3(=∞)> L2-3(=5),故其與最優(yōu)路段網(wǎng)的距離由原先的∞也轉(zhuǎn)變?yōu)?

首先構(gòu)造一個初始最優(yōu)路段網(wǎng),但該網(wǎng)絡只有一個節(jié)點,即“種子城市”,其位于圖2(a)中的中心圓圈內(nèi),圈外的節(jié)點稱為外圍節(jié)點或外圍城市。然后根據(jù)圖1城市間的距離(網(wǎng)絡節(jié)點間的邊的權(quán)值),求其它所有城市(網(wǎng)絡節(jié)點)與種子城市間的距離(通過訪問網(wǎng)絡的物理存儲結(jié)構(gòu)如鄰接表獲取),該圖表示僅通過了種子城市來連接所有的外圍其它城市,圖中中心圓圈外的城市當前還沒有加入到最優(yōu)路段網(wǎng)規(guī)劃中,圈外連接每個外圍城市與中心圓圈的實線表示該城市如果按當前規(guī)劃方案加入到該路段網(wǎng)時所需要建造的路段長度(即網(wǎng)絡邊的權(quán)),圈內(nèi)的虛線表示當前外圍城市通過某一個最優(yōu)路段網(wǎng)中的某城市為“橋梁”,而進入到該網(wǎng)絡中。例如,城市2如果通過城市1進入規(guī)劃網(wǎng),則需要修建長度為16(僅表示相對數(shù)值)的道路,城市5要修建長度19的道路,城市6要修建長度21的道路,而城市3和城市4無法通過城市1來連接到最優(yōu)路段網(wǎng)中(距離為無窮大,∞),而必須通過其它城市作為“橋梁”,來進入該規(guī)劃網(wǎng)絡中。很明顯,如果按照該方案來把所有的外圍城市都加入到初始最優(yōu)路段網(wǎng),得到的路段網(wǎng)如圖2(g),需要修建的路段網(wǎng)總長度為∞,顯然不是最優(yōu)路段網(wǎng)。

注意到為了使規(guī)劃的路段網(wǎng)是最優(yōu)的(路段長度總和最小),只要保證每次加入到最優(yōu)路段網(wǎng)中的城市都具有最短路段長度,則最后的路段總長度也必然最小。在圖2(a)中,城市2與種子城市具有最小的距離(16),因而不可能找到其它任何一個路段,實現(xiàn)“種子城市與其它外圍城市實現(xiàn)互連時,種子城市到其它任意一個城市的路段距離小于該值”,因而路段②-①必然是滿足種子城市連通其它城市的最優(yōu)路段,將城市2加入到最優(yōu)路段網(wǎng)后,得到圖2(b)。注意到當城市2加入到最優(yōu)路段網(wǎng)后,城市3、4、6如果是通過城市2為“橋梁”(圖中的虛線所示),加入到該最優(yōu)路段網(wǎng)中,可以使各自的路段長度由原先的∞、∞和21分別縮短到5、6、11(其它城市通過城市2無法實現(xiàn)路段長度縮短,因為保持不變),此時路段總長度也由原先的∞縮小到57(即16+5+6+19+11),較圖2(a),該方案有了很大的進步。然而該網(wǎng)絡仍不是最優(yōu)路段網(wǎng),因為其僅保證了路段②-①的最優(yōu)性(注意圓圈內(nèi)的網(wǎng)絡是最優(yōu)的),而其它城市到該網(wǎng)絡中的路段并非最優(yōu),這樣不能保證路段總長度最小。

進一步注意到,在所有的當前外圍城市中,城市3距離最優(yōu)路段網(wǎng)的距離最短(5),也就是為了使當前最優(yōu)路段網(wǎng)(圓圈內(nèi)的城市及連線)與其它外圍城市能夠?qū)崿F(xiàn)連通,且連通后的路段總長度最小,所以當前應加入城市3(圖2(c))。城市3的加入或許可以使得其它的外圍城市通過該城市為“橋梁”,而縮短外圍城市到最優(yōu)路段網(wǎng)的距離(當然這里城市3的加入實際并沒有使其它城市到最優(yōu)路段網(wǎng)的距離縮小)。同樣的道理,在第4步(圖2(d)),將城市4加入到最優(yōu)路段網(wǎng)中(因為在余下的外圍城市中,城市4到最優(yōu)路段網(wǎng)的距離最小),該城市的加入,也使得城市1以該城市為“橋梁”而到最優(yōu)路段網(wǎng)的距離由原來的19縮短到18(其它路段不變)。第5步將城市6加入到最優(yōu)路段網(wǎng)中(圖2(e)),該城市的加入沒有影響余下的城市(當前僅剩一個城市,即城市5),最后將城市5加入到最優(yōu)路段網(wǎng)中(圖2(f))。得到的最終的最優(yōu)路段網(wǎng)如圖2(h),其路段長度的總和為56(16+5+11+6+18)。

3算法求解

有了如上的圖示教學法描述的計算最小生成樹實現(xiàn)基本過程,在講解算法時就比較容易了。算法在實現(xiàn)時需要構(gòu)造三個輔助數(shù)組:第1個數(shù)組A[n](n為節(jié)點數(shù))記錄當前節(jié)點是外圍節(jié)點還是已加入最短路段(路徑)網(wǎng)的節(jié)點,數(shù)組元素A[i]=0或1,0表示節(jié)點i是一個外圍節(jié)點,當加入到最短路段(路徑)網(wǎng)后,A[i]=1;第2個數(shù)組B[n]記錄各節(jié)點到最短路段(路徑)網(wǎng)的距離,用B[n]表示;第3個數(shù)組C[n]記錄外圍節(jié)點通過最短路段(路徑)網(wǎng)內(nèi)的哪一個節(jié)點為“橋梁”而進入該路段(路徑)網(wǎng)的。注意這里的路徑R和路段L是兩個不同的概念,路段是節(jié)點的邊,而路徑是具有共同節(jié)點的有序邊起節(jié)點與尾節(jié)點首尾相連在一起的序列,如在圖1中,其中的一個路徑R1-3=L1-2+L2-3。下面結(jié)合圖2和圖3,給出這些數(shù)組的值在計算過程中的變化情況。

輔助數(shù)組的變化情況如下圖3所示,其中圖3(a)即對應于圖2(a),圖3(b)對應于圖2(b),依此類推。在圖3(a)中,首先只有第一個節(jié)點進入最短路段網(wǎng),因此A[1]=1,其它的A元素均為0,外圍節(jié)點與最短路段網(wǎng)的距離B[i]與圖2(a)中的距離對應,這里節(jié)點1由于已在最短路段網(wǎng),所以B[1]=0,由于所有的節(jié)點目前都是通過節(jié)點1與最短路段網(wǎng)連接,因而所有的C[i]的值都是1。在圖3(b)中,由于節(jié)點2距最短路段網(wǎng)的距離最小(16),節(jié)點2進入最短路段網(wǎng),因而A[2]=1,此時由于節(jié)點2已進入最短路段網(wǎng),因而B[2]=0,而節(jié)點3和節(jié)點4通過節(jié)點2,使它們距最短路段網(wǎng)的距離由原先的∞縮短到5和6,節(jié)點6也通過節(jié)點2使B[6]由21縮小到11。圖3(c)、3(d)、3(e)、3(f)的過程不再贅述。最后的結(jié)果(圖3(f))表明,節(jié)點1通過其本身進入最短路段網(wǎng),節(jié)點2通過節(jié)點1進入最短路段網(wǎng),節(jié)點3、4、6均通過節(jié)點2為“橋梁”進入最短路段網(wǎng),而節(jié)點5通過節(jié)點4進入最短路段網(wǎng)。

基于上述分析,不難給出以上算法的實現(xiàn)描述:

(1) 初始化數(shù)組A、B、C,結(jié)果如圖2(a)、圖3(a),這里假設以節(jié)點1為起始(源)節(jié)點,共有n個節(jié)點。

(2) 反復執(zhí)行如下操作:將B[i]中值最小的元素對應的編號i(即節(jié)點i)放入A中(即修改A[i]為1),然后修改A[j]!=0(j!=i)對應的B[j]和C[j]的值,修改的依據(jù)是:如果B[j]>Li-j,則用B[j]的值更改為Li-j。直至所有的A[i](1<=i<=n)都是1為止。

(3) 輸出結(jié)果,將B、C的最后值輸出即可以得到最后結(jié)果,B所有的元素最后都為0,表示所有的元素都進入了最短路段網(wǎng)(最小生成數(shù)網(wǎng)),而C中的元素值表示的是當前節(jié)點元素(即節(jié)點1、2、3、4、5或6)是通過C中表示的節(jié)點編號而進入最短路段網(wǎng)的,即:節(jié)點1是通過其自身進入路段網(wǎng),節(jié)點2通過節(jié)點1進入路段網(wǎng),節(jié)點3、4和6均通過節(jié)點2進入路段網(wǎng),節(jié)點5通過節(jié)點4進入路段網(wǎng)。

4結(jié)論

本文提出將圖示教學法可應用于數(shù)據(jù)結(jié)構(gòu)和算法課程教學的多個環(huán)節(jié)中,有些算法在大多數(shù)教科書中有了一定的圖示過程表示,而有些算法卻沒有給出形象的圖示表示,因而需要在教學中應補充。本文以圖狀結(jié)構(gòu)中的最小生成樹算法為例,通過圖示分析,詳細地講解這個算法的核心思想和實現(xiàn)過程,通過視覺刺激,使學生能夠加深對這個算法過程的把握,取得了良好的教學效果。

參考文獻:

[1] 戴敏,于長云,董玉濤. 高效學習數(shù)據(jù)結(jié)構(gòu)[J]. 計算機教育,2006(2):59-60.

[2] 余臘生,石獻. 基于創(chuàng)新理念的數(shù)據(jù)結(jié)構(gòu)教學方法探討[J]. 計算機與信息技術(shù),2006(11):110-114.

[3] 黃毅蓉. 關(guān)于多元復合函數(shù)偏導數(shù)鏈導法則的圖示教學探討[J]. 成都航空職業(yè)技術(shù)學院學報,2001(1):31-33.

[4] 薛超英. 數(shù)據(jù)結(jié)構(gòu)[M]. 2版. 武漢:華中科技大學出版社,2002.