[發(fā)明專利]一種稠密圖鄰接表壓縮方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201710909521.2
• 申請(qǐng)日: 2017-09-29
• 公開(kāi)（公告）號(hào): CN107564075A
• 公開(kāi)（公告）日: 2018-01-09
• 發(fā)明（設(shè)計(jì)）人: 李鳳英;張琪;常亮;古天龍
• 申請(qǐng)（專利權(quán)）人: 桂林電子科技大學(xué)
• 主分類號(hào): G06T9/00
• 分類號(hào): G06T9/00
• 代理公司: 桂林市持衡專利商標(biāo)事務(wù)所有限公司45107
• 代理人: 陳躍琳

1.一種稠密圖鄰接表壓縮方法，其特征是，包括步驟如下：

步驟1、使用廣度優(yōu)先搜索遍歷整個(gè)圖G的所有結(jié)點(diǎn)，從中找出出度最大的結(jié)點(diǎn)V，將該結(jié)點(diǎn)V的編碼設(shè)置為0并存儲(chǔ)在結(jié)點(diǎn)數(shù)組A的A[0]處；

步驟2、以結(jié)點(diǎn)V為起始結(jié)點(diǎn)，使用深度優(yōu)先搜索遍歷整個(gè)圖G，按照?qǐng)DG的深度優(yōu)先搜索序依次為結(jié)點(diǎn)編碼，并將結(jié)點(diǎn)編碼依次存入結(jié)點(diǎn)數(shù)組A中；

步驟3、建立結(jié)點(diǎn)V的初始出邊表L₀，并將出邊表L₀作為參考出邊表L；

步驟4、對(duì)于結(jié)點(diǎn)V_i，判斷該結(jié)點(diǎn)V_i的編碼i是否包含于參考出邊表L中；若參考出邊表L中包含結(jié)點(diǎn)V_i的編碼i，則轉(zhuǎn)至步驟5，若參考出邊表L中不包含結(jié)點(diǎn)V_i的編碼i，則轉(zhuǎn)至步驟6；

步驟5、將編碼i與結(jié)點(diǎn)V_i的第一個(gè)鄰接結(jié)點(diǎn)V_j的編碼j進(jìn)行比較；當(dāng)i≤j時(shí)，轉(zhuǎn)至步驟5.1；當(dāng)i＞j時(shí)，轉(zhuǎn)至步驟5.2；

步驟5.1、將結(jié)點(diǎn)V_i中從第一個(gè)鄰接結(jié)點(diǎn)開(kāi)始的結(jié)點(diǎn)編碼與參考出邊表L中從結(jié)點(diǎn)V_i開(kāi)始的結(jié)點(diǎn)編碼依次做比較；若有編碼相同的結(jié)點(diǎn)，則繼續(xù)比較，直到找到編碼不同的結(jié)點(diǎn)或所有結(jié)點(diǎn)全部比較結(jié)束且編碼相同為止；當(dāng)找到編碼不同的結(jié)點(diǎn)后，在參考出邊表L中最后一個(gè)編碼相同的結(jié)點(diǎn)V_last處標(biāo)記“i”；若始終沒(méi)有編碼相同的結(jié)點(diǎn)，則轉(zhuǎn)至步驟6；

步驟5.2、以結(jié)點(diǎn)V_j的出邊表L_j中從第一個(gè)鄰接結(jié)點(diǎn)開(kāi)始的結(jié)點(diǎn)編碼與結(jié)點(diǎn)V_i的出邊表L_i中從第二個(gè)鄰接結(jié)點(diǎn)開(kāi)始的結(jié)點(diǎn)編碼依次做比較，直到找到不同的編碼為止；若找到不同的編碼且不同編碼恰為i，則跳過(guò)該編碼，分別取出邊表L_i和L_j的下一個(gè)編碼繼續(xù)比較，直到找到不同的編碼且該不同編碼不為i；當(dāng)找到不同的編碼且該不同編碼不為i或所有編碼均相同時(shí)，則直接在出邊表L_j中最后一個(gè)相同結(jié)點(diǎn)V_last處標(biāo)記“i”；

步驟6、依次以L₁，L₂…L_i-1替換為參考出邊表L后，并轉(zhuǎn)至步驟4，直到在某一出邊表內(nèi)標(biāo)記“i”或在前i-1個(gè)結(jié)點(diǎn)的出邊表中都未能成功標(biāo)記“i”時(shí)停止替換；

當(dāng)在某一出邊表內(nèi)成功標(biāo)記“i”時(shí)，若結(jié)點(diǎn)V_i仍有不包含于該出邊表的鄰接結(jié)點(diǎn)，則將這些剩余鄰接結(jié)點(diǎn)按照結(jié)點(diǎn)編碼順序，依次添加到結(jié)點(diǎn)V_i的后續(xù)鏈表中，構(gòu)建成結(jié)點(diǎn)V_i的壓縮出邊表L_i；

當(dāng)在前i-1個(gè)結(jié)點(diǎn)的出邊表中都未能成功標(biāo)記“i”時(shí)，則直接將結(jié)點(diǎn)V_i的所有鄰接結(jié)點(diǎn)按照結(jié)點(diǎn)編碼順序，依次添加到結(jié)點(diǎn)V_i的后續(xù)鏈表中，構(gòu)建成結(jié)點(diǎn)V_i的壓縮出邊表L_i；

步驟7、將所有結(jié)點(diǎn)的壓縮出邊表建立完成后，將結(jié)點(diǎn)的出邊表與結(jié)點(diǎn)數(shù)組A結(jié)合，以結(jié)點(diǎn)數(shù)組A中存儲(chǔ)的元素即結(jié)點(diǎn)編碼為表頭，以擁有相同編碼的結(jié)點(diǎn)的出邊表作為后續(xù)鏈表，從而得到圖G完整的壓縮鄰接表；

上述i＝0,1,2,3…；j＝0,1,2,3…。

2.根據(jù)權(quán)利要求1所述的一種稠密圖鄰接表壓縮方法，其特征是，在步驟5.1中，當(dāng)找到不同的結(jié)點(diǎn)時(shí)，除了需要在參考出邊表L中最后一個(gè)相同結(jié)點(diǎn)V_last處標(biāo)記“i”之外，還需要在參考出邊表L的結(jié)點(diǎn)V_i處做一個(gè)特殊標(biāo)記，來(lái)表示結(jié)點(diǎn)V_i的鄰接結(jié)點(diǎn)是從參考出邊表L中的結(jié)點(diǎn)V_i處開(kāi)始計(jì)數(shù)。