層級結(jié)構(gòu)型數(shù)據(jù)的聯(lián)通性研究

摘? 要：針對結(jié)構(gòu)復(fù)雜、聯(lián)通算法難以實現(xiàn)的層級結(jié)構(gòu)聯(lián)通性問題，提出了利用樹結(jié)構(gòu)的最長路徑算法解決層級結(jié)構(gòu)型數(shù)據(jù)的方法。本研究以傳統(tǒng)城堡防護(hù)問題為例，找出中間相隔的城墻數(shù)量最多的兩個點，即層級結(jié)構(gòu)的聯(lián)通厚度。通過數(shù)據(jù)結(jié)構(gòu)分析，將城堡各區(qū)域轉(zhuǎn)化為樹結(jié)構(gòu)，驗證了樹結(jié)構(gòu)的最長路徑即為層級結(jié)構(gòu)的聯(lián)通厚度，最終巧妙實現(xiàn)將層級結(jié)構(gòu)轉(zhuǎn)換為樹結(jié)構(gòu)，并利用樹結(jié)構(gòu)的遍歷分析尋找到樹的最長路徑遞歸算法，解決了樹節(jié)點到節(jié)點的最長路徑，最終實現(xiàn)層級結(jié)構(gòu)各層的聯(lián)通路徑建設(shè)規(guī)劃，為層級結(jié)構(gòu)問題的解決找到突破口與參考性。

關(guān)鍵詞：層級結(jié)構(gòu);生成樹結(jié)構(gòu);聯(lián)通算法;最長路徑

中圖分類號：TP399? ? ?文獻(xiàn)標(biāo)識碼：A

Research on the Connectivity of Hierarchical Structured Data

HE Junzhong

（Longnan Teachers College， Chengxian 742500， China）

lnszhjztg@163.com

Abstract： Aiming at the problem of hierarchical structure connectivity that is difficult to achieve with the complex structure， this paper， proposes a method of using the longest path algorithm of the tree structure to solve the problem of hierarchical structure data. This research takes traditional castle protection problem as an example. It is necessary to find the two points， between which there is the largest number of walls， namely the connectivity thickness of the hierarchical structure. Through data structure analysis， each area of the castle is transformed into a tree structure to verify that the longest path of the tree structure is the connectivity thickness of the hierarchical structure. Finally， hierarchical structure is ingeniously transformed into tree structure， and the traversal of the tree structure is used to analyze and find the longest path recursive algorithm of the tree. It solves the longest path from the tree node to the node. Finally， the proposed method realizes the connection path construction planning of each layer in the hierarchical structure， and makes breakthroughs and provides references for solving hierarchical structure problems.

Keywords： hierarchical structure; spanning tree structure; connectivity algorithm; longest path

1? ?引言（Introduction）

在無法利用線性結(jié)構(gòu)表示的數(shù)據(jù)中，層級結(jié)構(gòu)最常見。數(shù)據(jù)間存在上下級關(guān)系或包含關(guān)系時，就會產(chǎn)生層級結(jié)構(gòu)。世界杯決賽的對陣表、公司或?qū)W校的組織結(jié)構(gòu)圖、網(wǎng)店商品的分類標(biāo)準(zhǔn)等，都具有層級結(jié)構(gòu)。表示層級結(jié)構(gòu)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)就是樹（tree）。若某一概念包含另一概念，就將兩個概念連接為上下級形式。這種從一個上級概念分割出許多從屬概念的形狀與樹非常相似，都可以轉(zhuǎn)化為樹結(jié)構(gòu)解決。

2? ?問題概述（Problem overview）

在古代，為保護(hù)城堡，防止敵入侵，更好地守衛(wèi)和保護(hù)更多領(lǐng)地，城堡中心都建有多層城墻，如圖1所示。其中主建筑的Strawgoh要塞達(dá)到了這種建城模式的極致。巨大的圓形外墻包含若干圓形內(nèi)墻，所有城墻均未設(shè)置城門。因此，要想進(jìn)出必須使用梯子，在要塞內(nèi)部從某地移動到另一地也需要耗費大量時間。為此，城主決定挖幾條地道，以連接來往不便的幾個地方。為了設(shè)計出合適的建設(shè)計劃，需要找出中間相隔的城墻數(shù)量最多的兩個點。例如，圖1中的兩個星號表示的地點相隔了5 層城墻[1]。

給出城墻信息時，編寫程序計算出從某地移動到另一地需要翻過的城墻最多會有幾層。此問題表面上看起來與樹結(jié)構(gòu)并無直接關(guān)系，但由“所有城墻不會相交或相接”可知，城墻有很規(guī)則的層次結(jié)構(gòu)，層級關(guān)系較為明確，從而可以將城墻間的包含關(guān)系轉(zhuǎn)化為樹結(jié)構(gòu)求解。

圖2（a）是表示各數(shù)據(jù)結(jié)構(gòu)關(guān)系的樹結(jié)構(gòu)圖。結(jié)構(gòu)圖中的每個方框表示1 種數(shù)據(jù)結(jié)構(gòu)，上面的方框表示上級概念，下面的方框表示從屬概念。若某一概念包含另一概念，就將兩個概念連接為上下級形式。這種從一個上級概念分割出許多從屬概念的形狀與樹非常相似（雖然上下顛倒），故稱為“樹”，如圖2（b）所示。層級結(jié)構(gòu)與人類的生活關(guān)系非常密切，所以得到了廣泛應(yīng)用。

為此，給城墻分割的各個“區(qū)域”標(biāo)上序號。將圍繞當(dāng)前區(qū)域的城墻序號用作該區(qū)域序號，得到圖3（a）。通過這種連接就能把包含關(guān)系表示為樹結(jié)構(gòu)，如圖3（b）所示。如果兩個區(qū)域不被同一城墻分割，那么它們不會在樹結(jié)構(gòu)中相互連接。例如，1 號區(qū)域間接包含3 號區(qū)域，所以并沒有在樹結(jié)構(gòu)中直接相連。

轉(zhuǎn)化為樹結(jié)構(gòu)后，從一個區(qū)域移動到相鄰其他區(qū)域的過程將對應(yīng)于樹結(jié)構(gòu)中沿著樹的邊從一個節(jié)點移動到另一個節(jié)點的過程。因此，兩個區(qū)域間經(jīng)過的最多城墻數(shù)問題就能變換成在樹結(jié)構(gòu)中尋找相隔最遠(yuǎn)的兩個節(jié)點的問題。此時，連接兩個節(jié)點的各邊就是樹的路徑[1]。

3? ?樹的最長路徑（The longest path of the tree）

上述建模過程將問題變換為“找出給定樹結(jié)構(gòu)中最長路徑”的問題。而求樹的最長路徑并不難，求解關(guān)鍵在于需要明白最長路徑的兩端必須是根節(jié)點或葉節(jié)點。

假設(shè)，既不是根節(jié)點也不是葉節(jié)點的內(nèi)部節(jié)點（Internal Node）是路徑終點，而內(nèi)部節(jié)點總是連接兩條以上的邊。因為此節(jié)點不是根節(jié)點，所以會有連向父節(jié)點的邊;又不是葉節(jié)點，所以會有連向子節(jié)點的邊。因此，以內(nèi)部節(jié)點為終點的路徑必定至少存在1條未使用的邊。利用此邊就能生成更長的路徑，所以它不可能是最長路徑[2]。

由此可知，最長路徑會是如下兩種路徑中的較大值：最長的根—葉路徑長度和最長的葉—葉路徑長度。

此時，最長的根—葉路徑長度等于樹的高度，我們已經(jīng)知道求解方法?，F(xiàn)在只要求出最長的葉—葉路徑長度，就能得出答案。

葉—葉路徑的形式總是從葉節(jié)點到達(dá)某個節(jié)點后，又回到另一個葉節(jié)點。例如，圖2（b）中連接3和4的路徑，首先從3到達(dá)1之后，又返回4;而連接3和7的路徑，首先從3到達(dá)0之后，又返回7。這種先上升后下降的路徑中，處在上下轉(zhuǎn)換位置的節(jié)點就是此路徑的頂端節(jié)點。因此，在樹的遍歷過程中找出將各節(jié)點用作頂端節(jié)點的最長葉—葉路徑，選擇其中的最大值即可[3]。

該如何求將給定節(jié)點用作頂端節(jié)點的最長葉—葉路徑呢？這種路徑的形態(tài)是：當(dāng)前節(jié)點的后代節(jié)點中，從一側(cè)上升到該節(jié)點，然后從另一側(cè)下降。此時，上升部分和下降部分的長度等于將各自的后代節(jié)點用作根節(jié)點的子樹高度加1。因此，先計算出各子樹的高度后，找出最高的兩個子樹就能求出最長葉—葉路徑。

這些過程相當(dāng)于求樹的高度的運算過程。因此，變換一下求樹高的遞歸函數(shù)就能求出此題。代碼1表示解決此問題的遞歸調(diào)用函數(shù)。代碼中，已找出的最長路徑的長度會保存到全局變量longest，而height（）函數(shù)通過更新此變量完成操作。另外，利用最高的兩個子樹的高度求出將當(dāng)前節(jié)點用作頂端節(jié)點的葉—葉路徑中的最長路徑[4]。

代碼1：找出樹結(jié)構(gòu)中最長路徑的遞歸算法。

struct Treellode {

vector children;

};

// 保存已找出的最長葉—葉路徑的長度

int longest;

//返回將root用作根節(jié)點的子樹的高度

int height（TreeNode* root）{

//計算將各子節(jié)點用作根節(jié)點的子樹高度

vector heights;

for（int i=0;i < root->children.size（）;++i）

heights.push_back（height（root->children[i]））;

//沒有子節(jié)點就返回0

if（heights.empty（）） return 0;

sort（heights.begin（），heights.end（））;

//考慮將root用作頂端節(jié)點的路徑

if（heights.size（）>=2）

longest=max（longest，2+heights[heights.size（）-2]+

heights[heights.size（）-1];

//將子樹高度加1以算出樹的高度

return heights.back（）+1;

}

//計算兩個節(jié)點之間的最長距離

int solve（TreeNode* root）{

longest=0;

//選擇樹的高度和最長葉—葉路徑中更大的值

int h=height（root）;

return max（longest，h）;

}

其中height（）函數(shù)在處理整個樹結(jié)構(gòu)的過程中會耗費時間，若是忽略子樹高度的排序時間O（nlgn），就會與樹的遍歷時間相同，都是O（n）[5]。

4? ?算法的實現(xiàn)（Algorithm implementation）

此問題的實際實現(xiàn)方法可分為兩部分：從輸入值生成樹結(jié)構(gòu);在生成的樹結(jié)構(gòu)中求出最長路徑。求最長路徑的部分如前所述，接下來介紹樹結(jié)構(gòu)生成過程。

最直觀的生成樹結(jié)構(gòu)的方法是從樹的根節(jié)點開始生成。第0 號城墻是包含其他所有城墻的外墻，所以它會成為樹的根節(jié)點。找出第0 號城墻的下一層城墻，并通過遞歸調(diào)用生成將各城墻用作根節(jié)點的子樹。代碼2是將給定序號的城墻用作根節(jié)點并生成樹結(jié)構(gòu)的getTree（）函數(shù)[6]。

代碼2：生成表示給出城墻中各區(qū)域的樹結(jié)構(gòu)。

//生成將root城墻用作根節(jié)點的樹

TreeNode* getTree（int root）{

TreeNode* ret=new Treenode（）;

for（int ch=0;ch

//如果ch城墻直接包含于root城墻，那么生成樹后再添加到后代目錄

if（isChild（root，ch））

ret->children.push_back（getTree（ch））;

return ret;

}

getTree（）中的isChild（）函數(shù)可用多種方法實現(xiàn)。不過，實現(xiàn)此函數(shù)最簡單的方法是，根據(jù)其他城墻的信息判斷是否存在于兩個城墻之間。例如，圖2（a）中，第0 號城墻和第4 號城墻之間存在第1 號城墻，因此，第4 個區(qū)域并沒有直接包含于第0 號區(qū)域。代碼3表示實現(xiàn)這種簡單方法的isChild（）函數(shù)[7]。

代碼3：確認(rèn)某個城墻是否包含且直接包含于另一城墻的函數(shù)。

//輸入數(shù)據(jù)

int n，y[100]，x[100]，radius[100];

//返回x^2

int sqr（int x）{

return x*x;

}

//返回兩個城墻a和b的圓心點距離的平方值

int sqrdist（int a，int b）{

return sqr（y[a]-y[b]）+sqr（x[a]-x[b]）;

}

//確認(rèn)城墻a是否包含城墻b

bool encloses（int a，int b）{

return radius[a]>radius[b] &&

sqrdist（a，b）

}

//在"城墻"樹結(jié)構(gòu)中確認(rèn)parent是否為child的父節(jié)點

// parent必須直接包含 child

bool iscChild（int parent，int child）{

if（！encloses（parent，child）） return false;

for（int i=0;i

if（i ！=parent && i ！=child &&

encloses（parent，i）&& encloses（i，child））

return false;

return true;

}

通過這種實現(xiàn)方法，isChild（）函數(shù)能夠在O（n）的時間內(nèi)完成運算。樹結(jié)構(gòu)生成過程中，每訪問1 個節(jié)點，就會調(diào)用n 次isChild（）。因此，整個算法的時間復(fù)雜度為O（n2）[8]。

5? ?結(jié)論（Conclusion）

本研究根據(jù)城堡防衛(wèi)結(jié)構(gòu)圖及聯(lián)通性需求，利用層級結(jié)構(gòu)和樹結(jié)構(gòu)關(guān)系，將不容易直接解決的層級結(jié)構(gòu)數(shù)據(jù)轉(zhuǎn)化為樹結(jié)構(gòu)，從而將城堡的聯(lián)通性結(jié)構(gòu)設(shè)計轉(zhuǎn)化成了樹結(jié)構(gòu)的最長路徑問題來解決。通過尋找樹結(jié)構(gòu)的最長路徑優(yōu)化算法，最終實現(xiàn)城堡的最大聯(lián)通值。同時，通過解決城堡防衛(wèi)聯(lián)通性問題，得出利用樹結(jié)構(gòu)解決層級結(jié)構(gòu)的方法，為解決層級結(jié)構(gòu)問題的相關(guān)研究提供了依據(jù)。

參考文獻(xiàn)（References）

[1] 計算思維百科.“要塞”的版本間的差異[EB/OL].（2016-06-02）? [2021-06-05]. https：//wiki.jsswsq.com/index.php？diff=prev&oldid=3711&title=%E8%A6%81%E5%A1%9E.

[2] RAI A K， KUMAR N. Intra-block correlation based reversible data hiding in encrypted images using parametric binary tree labeling[J]. Symmetry， 2021， 13（6）：187-189.

[3] 楊迪，馬金全，岳春生，等.面向異構(gòu)處理平臺的最長路徑列表調(diào)度算法[J].信息工程大學(xué)學(xué)報，2021，22（02）：136-141，214.

[4] 王前東.一種帶匹配路徑約束的最長公共子序列長度算法[J].電子與信息學(xué)報，2017，39（11）：2615-2619.

[5] 潘靜靜.林區(qū)輪伐期優(yōu)化的隱式圖建模和最長路徑算法[J].河南科技大學(xué)學(xué)報（自然科學(xué)版），2016，37（01）：73-77，8-9.

[6] 劉劍，宋瑩，鄧立軍.基于GA與最長路徑并聯(lián)通路法優(yōu)化通風(fēng)網(wǎng)絡(luò)圖繪制[J].中國安全生產(chǎn)科學(xué)技術(shù)，2014，10（11）：77-83.

[7] 王防修，周康.基于最長公共子序列的隨機路徑選擇算法設(shè)計[J].計算機工程與設(shè)計，2014，35（06）：2170-2173.

[8] 張琦，金胤丞，李苗，等.Trie樹路由查找算法在網(wǎng)絡(luò)處理器中的實現(xiàn)[J].計算機工程，2014，40（1）：98-102.

作者簡介：

賀軍忠（1982-），男，碩士，副教授/網(wǎng)絡(luò)工程師.研究領(lǐng)域：網(wǎng)絡(luò)組建與信息安全，網(wǎng)絡(luò)營銷.