1、最小生成樹(MST)作為圖論中最經(jīng)典算法之一，引發(fā)了人們經(jīng)久不衰的關注。由于MST的性質(zhì)，在規(guī)劃、網(wǎng)絡和醫(yī)學等各個領域得到了廣泛的應用。同時，基于MST結(jié)構(gòu)的聚類、分類和最短路徑查詢等復雜圖算法，在效率和結(jié)果質(zhì)量方面均有顯著提高。然而，隨著互聯(lián)網(wǎng)的迅猛發(fā)展，圖規(guī)模也變得越來越大，包含千萬甚至上億個頂點的大規(guī)模圖越發(fā)常見。因此，如何在大規(guī)模圖上實現(xiàn)查詢處理和數(shù)據(jù)挖掘算法已成為了亟待解決的問題之一。除此之外，由于大規(guī)模圖的動態(tài)性特征，即圖的

2、拓撲結(jié)構(gòu)可能會發(fā)生改變，如何動態(tài)地維護算法結(jié)果也勢必成為最受關注的問題之一。
　　本文提出并行MST算法和MST動態(tài)維護算法，為上述問題提供了堅實的基礎。
　　首先，本文利用以邊為中心的設計思想，提出了邊驅(qū)動的并行MST算法。同時，本文設計了分布式索引、分區(qū)加速和基于直方圖排序等優(yōu)化技術，提高了算法的執(zhí)行效率。隨后，基于不同的通信模型實現(xiàn)了并行MST算法并分析了算法的時間復雜度。實驗驗證了算法的有效性，以及分布式索引和基于直

3、方圖排序技術的高效性。
　　其次，本文從頂點為中心的角度出發(fā)，提出了頂點驅(qū)動的并行MST算法PB，并論證了PB算法的正確性。另外，本文給出了PB算法的終止條件和索引維護策略。隨后，分別列出了基于MapReduce和BSP框架的PB算法的整體執(zhí)行過程，其中包括啟動作業(yè)和循環(huán)作業(yè)的詳細處理流程。同時，本文分別針對上述框架剖析了PB算法的時間復雜度。實驗證明了PB算法的有效性、高效性和可擴展性。
　　最后，針對圖的動態(tài)性特征，本文

4、定義了動態(tài)圖的五種操作并提出了MST結(jié)果的分布式動態(tài)維護算法MTBM。同時，本文給出了二次劃分和分布式MST構(gòu)建等預處理算法。在預處理之后，分別針對插入、刪除和修改等操作，設計了相應的維護策略，并分析了MTBM算法執(zhí)行代價。實驗證明了MTBM算法的可靠性和高效性。
　　總之，本文從大規(guī)模圖角度出發(fā)，針對MST問題展開一系列研究，分別提出了邊驅(qū)動和頂點驅(qū)動的并行MST算法以及MST結(jié)果的分布式動態(tài)維護算法。本文的研究工作，即大規(guī)模圖