標籤: 暫無標籤

目錄

1邊集數組

邊集數組(edgeset array)是利用一維數組存儲圖中所有邊的一種圖的表示方法。該數組中所含元素的個數要大於等於圖中邊的條數,每個元素用來存儲一條邊的起點、終點(對於無向圖,可選定邊的任一端點為起點或終點)和權(若有的話),各邊在數組中的次序可任意安排,也可根據具體要求而定。
邊集數組只是存儲圖中的所有邊的信息,若需要存儲頂點信息,則還需要另外一個具有n個元素的一維數組。設圖G中的頂點數為n,邊數為e,且不需要存儲頂點信息,則圖的邊集數組表示的有關類型定義和生成一個無向帶權圖的邊集數組的演算法描述如下:
type degenode=record{} fromvex,endvex:1..n; {邊的起點和終點域,亦可定義為其它子域型或自定義型}
weight:{權值的類型,對無權圖可省去此域}end edgeset=array〔1..m 0 〕of edgenode; {定義邊集數組類型,其中m 0 要大於等於圖中的邊數e}
procedure crate3(GE); {GE為具有edgeset類型的變參,表示一個邊集數組}
begin
for k:=1 to e do (1)
read(i,j,w);{讀入一條邊的信息}  
2)
GE〔k〕.fromvex:=i;
GE〔k〕.endvex:=j;
GE〔k〕.weight:=w {把讀入的一條邊寫入邊集數組的第k個單元}
end;
邊集數組中查找一條邊或一個頂點的度都需要掃描整個數組,所以其時間複雜性為O(e)。
邊集數組適合那些對邊依次進行處理的運算,不適合對頂點的運算和對任一條邊的運算。
邊集數組表示通常包括一個邊集數組和一個頂點數組,所以其空間複雜性為O(n+e)。從空間複雜性上講,邊集數組也適合表示稀疏圖。圖的鄰接矩陣、鄰接表示和邊集數組表示各有利弊,具體應用時,要根據圖的稠密和稀疏程度以及運算的要求進行選擇。
上一篇[順序文件]    下一篇 [特殊矩陣]

相關評論

同義詞:暫無同義詞