浅议标号标号树编解码线性算法设计

更新时间:2024-03-16 点赞:5512 浏览:17414 作者:用户投稿原创标记本站原创

摘要:标号树的编码是一串能够映射一棵标号树结构的标号序列,由于在现代优化算法中便于运算而常常被采用。本文对四种常见的标号树的编解码方法进行了综述,并就标号树直观的边集表示和编码表示之间的转换算法进行讨论,实现了四种标号树编解码的线性算法。
关键词:标号树;Prufer编码;Nevile编码;DM编码
● 引言
标号树是计算机领域中常见的一种数据组织形式,它的传统存储方法通常有双亲表示法、孩子表示法、孩子兄弟表示法、边集表示法等,这些表示方法,在遗传、粒子群等现代优化算法中,由于很难进行运算,所以很少被使用。而标号树的编码是一串可以映射一棵标号树的标号序列,由于其存储简单、便于运算,常常被采用,因而对于标号树编码的深入讨论,无论在计算机的理论还是应用上,都有着十分重要的意义。
1918年Prufer在证明Cayley定理时,最先提出了Prufer编码,1953年Neville提出了三种编码方法,其中第一种和Prufer码一样,后两种称之为Neville2码、Neville3码,近年来Deo和Micikevicius又提出了一种新的编码方法。我们将上述四种编码简称为PR、N

2、N3、DM码。

根据编码定义,以上四种编码除DM编解码的算法时间为О(n),其他三种都为О(n2)。近年来一些文献用算法语言给出了它们的线性算法思想。本文在综述上述四种编解码规则之后,用C语言,就标号树直观的边集表示和编码表示之间的转换,给出了编码和解码的线性算法。
● 标号树的编码

1.编码方法

总的来说,四种编码方法都是以叶节点的删除为基础,直至只剩下一条边为止,按照n-2个叶节点的删除顺序,依次将其在删除前的邻接点编号组成一个数字序列,就是其标号树的编码。四种编码的不同在于叶节点的删除顺序不同。
(1)PR编码
删除标号树中最小编号的叶节点;重复第一步,直至该标号树剩一条边。
如图1所示的标号树,PR编码的叶子节点删除顺序应为3、4、5、6、8、

1、2、9,其相应的邻接点顺序为(6,10,6,7,1,2,7,7)。

(2)N2编码
按升序将标号树的叶节点整批删除;在修正过的标号树上重复第一步,直至该标号树剩一条边。
如图1,N2编码的叶子节点删除顺序应为第一层的3、4、5、8、9和第二层的

1、6、10,其相应的邻接点顺序为(6,10,6,1,7,2,7,7)。

(3)N3编码
从最小叶节点开始,逐个删除其所在链上的节点,直至该链被删除;重复第一步,直至该标号树剩一条边。
如图1,N3编码的叶节点删除顺序应为第一条链3,第二条链4、10,第三条链5、6,第四条链8、

1、2,其相应的邻接点顺序为(6,10,7,6,7,1,2,7)。

(4)DM编码
按升序将标号树的叶节点整批删除;对修正过的标号树按照其叶节点出现的先后顺序进行整批删除;重复第二步,直至该标号树剩一条边。
如图1,DM编码的叶子节点删除顺序应为第一层的3、4、5、8、9和第二层的10,6,1,其相应的邻接点顺序为(6,10,6,1,7,7,7,2)。

2.编码算法

(1)存储结构
typedef struct node
{ int data;
struct node *next;
} Node;
typedef Node LTree[N+1];
LTree t;
标号树的存储结构采用了图的邻接表存储形式,其说明语句如上,标号树的邻接表存储示意图见图2。将标号树中每个节点i的度数存放在t[i]的data域中,将与该节点i相邻的所有邻接点,以链表链接在t[i]的next域中,为了节点i和t数组下标的一致,这里数组的长度定义为N+1。
(2)PR编码算法
PR编码算法的思想:在邻接表t中顺序查找出第一个度数为1的节点j(t[j].data=1),当前最小的叶节点u=j,求出和u相邻的节点v,写入编码数组,删除最小叶节点u(t[u].data--,t[v].data--);比较v和j,如果vPR编码算法实现见函数PR( ),c数组存放标号树的PR编码;函数GetAdjvex( )实现标号树t中求解u节点的邻接点运算。
PR( LTree t,int c[] )
{ int i,j,u,v;
u=v=j=0;
for(i=1;i* { if(v//找编号最小的叶子节点u
else
{ while(t[++j].data!=1) ;
u=j;
}
v=GetAdjvex(t,u); // 找叶子u相邻节点v
源于:大专毕业论文www.618jyw.com
c[i]=v; //将节点v写入c数组
t[u].data--; t[v].data--; // 删除边(u,v)
}
}
int GetAdjvex(LTree t ,int u )
{ Node *p=t[u].next;
while( t[p->data].data==0) p=p->next; 源于:免费论文查重站www.618jyw.com
相关文章
推荐阅读

 发表评论

共有3000条评论 快来参与吧~