在日常生活中,常用圖來表示一些問題或概念,如IC設(shè)計(jì)、城市間交通道路規(guī)劃、作業(yè)調(diào)度等。圖和樹一樣,也是一種非線性數(shù)據(jù)結(jié)構(gòu)。圖和樹的最大差異在于: 樹描述的是數(shù)據(jù)元素(結(jié)點(diǎn))之間的層次關(guān)系,每一層上的數(shù)據(jù)元素可能和下一層中多個元素(即孩子結(jié)點(diǎn))相關(guān),但只能和上一層中一個元素相關(guān),而圖結(jié)構(gòu)研究兩頂點(diǎn)之間是否相連的關(guān)系,在圖中,結(jié)點(diǎn)之間的關(guān)系是任意的,圖中任意兩個數(shù)據(jù)元素之間都有可能相關(guān)。圖結(jié)構(gòu)提供了簡單的方式來描述一個問題、系統(tǒng)或狀況等。這種圖的先后順序關(guān)系便是我們所提到的拓?fù)鋱D,我們所要做的事情就是從這些拓?fù)鋱D里面提取出符合實(shí)際生產(chǎn)需要的拓?fù)湫蛄?以達(dá)到解決實(shí)際問題的需要。
然而,基于有向圖的拓?fù)渑判蛟谀男┓矫嬗袘?yīng)用呢?我們都知道一個復(fù)雜的工程通?？梢苑纸獬梢唤M小任務(wù)的集合,完成這些小任務(wù)意味著整個工程的完成。例如,汽車裝配工程可分解為以下任務(wù):將底盤放上裝配線,裝軸,將座位裝在底盤上,上漆,裝剎車,裝門等等。任務(wù)之間具有先后關(guān)系,例如在裝軸之前必須先將底板放上裝配線。任務(wù)的先后順序可用有向圖表示——稱為頂點(diǎn)活動( Activity On Vertex, AOV)網(wǎng)絡(luò)。再例如,一個建筑工程的過程,通過對我們上面的分析,可以用拓?fù)鋱D表示為如下所示,我們可能要問:該項(xiàng)工程或系統(tǒng)能否順利完成?如果一個工程隊(duì)在一個時(shí)段只能做一件活動,應(yīng)該按什么順序完成這些活動?還有,比如我們現(xiàn)在的排課問題,也其實(shí)是一個拓?fù)溆行蛄械那蠼膺^程,在此類問題中,課程我們可以用向圖中的結(jié)點(diǎn)來表示,然后課程之間的先后關(guān)系,我們可以用圖的弧來表示,弧頭是弧尾所指的結(jié)點(diǎn)的后導(dǎo)課程,弧尾是弧頭的前驅(qū)課程。按照此種定義,我們從中提取出一個課程相互關(guān)系的結(jié)點(diǎn)元素的序列,便是我們所要求解的拓?fù)湫蛄小?br />
1 排課問題的描述
每個學(xué)期,我們都要對不同的課程進(jìn)行排課,然而,課程之間有著特殊的制約性質(zhì),我們還得考慮,比如計(jì)算機(jī)核心課程里面的數(shù)據(jù)結(jié)構(gòu)的前導(dǎo)課程是計(jì)算機(jī)文化基礎(chǔ),因此各個課程之間都有著嚴(yán)格的前后約束關(guān)系。其次,我們假設(shè)每個學(xué)生選課的情況是一個時(shí)間段只能選取一門課程,而且前后的幾個時(shí)間段必須是嚴(yán)格的連續(xù)的關(guān)系。再次,各個時(shí)間段選取的課程不能是以前已經(jīng)選取過的課程,在這里我們?yōu)榱撕唵纹鹨?假設(shè)選取的時(shí)間段為一個學(xué)期。最后,我們從建模后的拓?fù)鋱D中提取出一個拓?fù)湫蛄凶鳛橐粋€學(xué)生的各個學(xué)期的選課順序。綜上所述,該條件下排課問題的建模如下:
1) 各個課程之間有著嚴(yán)格的先后順序關(guān)系。
2) 兩個相鄰課程之間的跨度為一個時(shí)間段,具體就是一個學(xué)期。
3) 每個學(xué)生每個學(xué)期只能選一門課程。
4) 選擇一個拓?fù)湫蛄斜闶且粋€學(xué)生的各個學(xué)期的選課情況序列。
2有向圖的存儲結(jié)構(gòu)設(shè)計(jì)以及堆棧的定義
2.1 有向圖的定義與解釋
有向圖是一個二元組,其中:
1) V是非空集合,稱為頂點(diǎn)集。
2) E是V×V的子集,稱為邊集。
直觀來說,若圖中的每條邊都是有方向的,則稱為有向圖。有向圖中的邊是由兩個頂點(diǎn)組成的有序?qū)?有序?qū)νǔＳ眉饫ㄌ柋硎?如表示一條有向邊,其中vi是邊的始點(diǎn),vj是邊的終點(diǎn)。和代表兩條不同的有向邊。
2.2 鄰接矩陣
鄰接矩陣(Adjacency Matrix):是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是一個圖,其中V={v1,v2,…,vn}。G的鄰接矩陣是一個具有下列性質(zhì)的n階方陣:
1) 無向圖的鄰接矩陣一定是對稱的,而有向圖的鄰接矩陣不一定對稱。因此,用鄰接矩陣來表示一個具有n個頂點(diǎn)的有向圖時(shí)需要n2個單元來存儲鄰接矩陣;對有n個頂點(diǎn)的無向圖則只存入上(下)三角陣中剔除了左上右下對角線上的0元素后剩余的元素,故只需1 2 ... (n-1)=n(n-1)/2個單元。
2) 無向圖鄰接矩陣的第i行(或第i列)非零元素的個數(shù)正好是第i個頂點(diǎn)的度。
3) 有向圖鄰接矩陣中第i行非零元素的個數(shù)為第i個頂點(diǎn)的出度,第i列非零元素的個數(shù)為第i個頂點(diǎn)的入度,第i個頂點(diǎn)的度為第i行與第i列非零元素個數(shù)之和。
4) 用鄰接矩陣表示圖,很容易確定圖中任意兩個頂點(diǎn)是否有邊相連。
2.3 鄰接表
鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。對圖的每個頂點(diǎn)建立一個單鏈表(n個頂點(diǎn)建立n個單鏈表),第i個單鏈表中的結(jié)點(diǎn)包含頂點(diǎn)Vi的所有鄰接頂點(diǎn)。又稱鏈接表。其中:
1) 在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧
2) 在有向圖的鄰接表中,對每個頂點(diǎn),鏈接的是指向該頂點(diǎn)的弧。
對于有向圖,vi的鄰接表中每個表結(jié)點(diǎn)都對應(yīng)于以vi為始點(diǎn)射出的一條邊。因此,將有向圖的鄰接表稱為出邊表。鄰接表的形式說明如下:
typedef struct node{//邊表結(jié)點(diǎn)
int adjvex; //鄰接點(diǎn)域
struct node *next; //鏈域
//若要表示邊上的權(quán),則應(yīng)增加一個數(shù)據(jù)域
}EdgeNode;
typedef struct vnode{ //頂點(diǎn)表結(jié)點(diǎn)
VertexType vertex; //頂點(diǎn)域
EdgeNode *firstedge;//邊表頭指針
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];//AdjList是鄰接表類型
typedef struct{
AdjList adjlist;//鄰接表
int n,e; 圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù)
}ALGraph; //對于簡單的應(yīng)用,無須定義此類型,可直接使用AdjList類型。
在本文中將采用的儲存結(jié)構(gòu)便是鄰接表,至于為什么要采用鄰接表而不采用鄰接矩陣,我們將在后面予以分析。
2.4 堆棧的定義以及堆棧在本文中的作用
堆棧是一個不容忽視的概念,但是很多人甚至是計(jì)算機(jī)專業(yè)的人也沒有明確堆棧其實(shí)是兩種數(shù)據(jù)結(jié)構(gòu)。堆棧都是一種數(shù)據(jù)項(xiàng)按序排列的數(shù)據(jù)結(jié)構(gòu),只能在一端(稱為棧頂(top))對數(shù)據(jù)項(xiàng)進(jìn)行插入和刪除。要點(diǎn):堆:順序隨意棧:后進(jìn)先出(Last-In/First-Out)。
在本文中為了快速有效地輸出拓?fù)湫蛄?應(yīng)該要對待輸出的結(jié)點(diǎn)進(jìn)行暫存,并且由于后面待輸出的結(jié)點(diǎn)需要與前面已經(jīng)輸出的結(jié)點(diǎn)發(fā)生聯(lián)系,因此,如果采用數(shù)組或者其它的數(shù)據(jù)結(jié)構(gòu)存儲便會比較麻煩,在這里我們綜合考慮到堆棧的特質(zhì),我們采用堆棧作為待輸出結(jié)點(diǎn)的緩沖區(qū)域。
3 拓?fù)渑判蛩惴ǖ拿枋?br />
3.1 拓?fù)渑判蛩惴ㄋ悸?br />
1) 在圖中找一個沒有前驅(qū)的頂點(diǎn),并把它輸出;
2) 從圖中刪除該頂點(diǎn)及由它發(fā)出的弧;
3) 重復(fù)第1、2步,直到所有頂點(diǎn)都輸出(頂點(diǎn)輸出序列為拓?fù)湫蛄?或剩余頂點(diǎn)中找不到?jīng)]有前驅(qū)的頂點(diǎn)(圖中存在回路)。
3.2 拓?fù)渑判騻未a
1) 計(jì)算每個頂點(diǎn)的入度indegree[];
2) 棧S初始化;計(jì)數(shù)器count初始化;
3) 掃描頂點(diǎn)表,將入度為零的頂點(diǎn)入棧;
4) 當(dāng)棧S非空時(shí)反復(fù)循環(huán):
step 3.1 彈出棧頂元素i;打印i;count加1;
step3.2 將頂點(diǎn)i的各個鄰接點(diǎn)的入度減1;
step3.3 將新的入度為0的頂點(diǎn)入棧;
5) if (count
3.3 拓?fù)渑判蛩惴ǔ绦虼a
Status ToplogicalSort(ALGraph G){
FindIndegree(G,indegree);
InitStack(S);
for( i=1;i<=G.vexnum;i )
if (!indegree[i]) Push(S,i);
count=0;
while (!StackEmpty(S)){
Pop(S,i);printf(i,G.vertices[i].data); count;
for(p=G.vertices[i].firstarc;p;p=p->nextarc){
k=p->adjvex;
if (- -indegree[k]) Push(S,k);
}//for
}//while
if (count
else return OK;
}//ToplogicalSort
4 實(shí)例分析
4.1 排課問題的數(shù)學(xué)建模
如表1所示,各個課程號代表的含義,以及各個課程相對應(yīng)的先修課。
如圖1表示了各個課程之間的拓?fù)鋱D,其中結(jié)點(diǎn)表示課程,弧代表前后兩門課程之間的約束關(guān)系。
4.2 實(shí)驗(yàn)?zāi)M初始狀態(tài)下各個結(jié)點(diǎn)的入度統(tǒng)計(jì)與鄰接表的狀態(tài)
圖2為各個頂點(diǎn)的入度統(tǒng)計(jì)圖;圖3為初始狀態(tài)下鄰接表的狀態(tài)。
5 實(shí)驗(yàn)結(jié)果及分析
5.1 實(shí)驗(yàn)結(jié)果
運(yùn)行的結(jié)果表明,本課程安排不存在回路,因此是一個恰當(dāng)有效的課程安排方案。并且可以產(chǎn)生多種拓?fù)渑判虻男蛄泄W(xué)生選課方案進(jìn)行選擇,例如可以是:
1) A,B,C,D,E,F,G
2) A,C,B,D,F,E,G
3) A,C,B,D,E,F,G
5.2 算法復(fù)雜度分析
由于本算法采用了一個一階的循環(huán),因此循環(huán)體內(nèi)的語句將執(zhí)行N個單位次數(shù),另外由于使用了堆棧作為數(shù)據(jù)暫存結(jié)構(gòu),則復(fù)雜系數(shù)為E,因此整個算法的時(shí)間復(fù)雜度是:O(N E)。
5.3 思考
在本文的算法里面,對于待輸出的結(jié)點(diǎn)是采用堆棧作為暫存,而堆棧最大的特點(diǎn)是“先進(jìn)先出”,但是本算法里面根本沒有運(yùn)用到堆棧的這個性質(zhì),而僅僅是用來作為數(shù)據(jù)的暫時(shí)存儲,這里我們其實(shí)也可以采用隊(duì)列的方法。
另外,我們也完全可心采用鄰接矩陣的方式對有向圖進(jìn)行存儲,而不一定是采用鄰接表進(jìn)行存儲。但是由于在求解每個結(jié)點(diǎn)的入度的時(shí)候,我們需要掃描整個鄰接矩陣的一行或者一列,而對于N個結(jié)點(diǎn),則需要掃描N*N次,因此時(shí)間復(fù)雜度則為O(N*N),因此,采用鄰接表的效率要高一些。
參考文獻(xiàn):
[1] 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)C語言版[M].北京:清華大學(xué)出版社,2007.
[2] 維斯.數(shù)據(jù)結(jié)構(gòu)與算法分析C語言描述[M .北京:機(jī)械工業(yè)出版社,2004.
[3] 周建麗,黃志真.用拓?fù)渑判虬才耪n程順序[J].重慶交通學(xué)院學(xué)報(bào),1997(4).
[4] 劉聲田,路明.面向?qū)ο蠹夹g(shù)獲取AOV網(wǎng)絡(luò)拓?fù)湫蛄械乃惴╗J].山東電大學(xué)報(bào),2005(2).
