西安石油大学学报(自然科学版)
Journal of Xi'an Shiyou University(Natural Science Edition)
ISSN 167。针对现有计算方法计算时间
长且计算效率随着图的规模增大逐渐下降的问题，提出一种针对连通图的随机生成树组求解算法。首先定
义简化规则，将复杂图中不涉及生成树生成过程的辐射通路删除，合并互斥支路集中的支路得到简化图，然
后通过在简化图和树图间以轮盘赌的方式随机选择支路进行迁移得到简化图对应的生成树图，最后逆向用
简化图和原图的支路关系得到复杂图对应的生成树组。通过算例表明，该方法能快速有效地生成对应的生
成树组。
关键词：连通图；随机生成树组；辐射通路；轮盘赌
ＡＮｅｗＡｌｇｏｒｉｔｈｍ ｆｏｒＧｅｎｅｒａｔｉｎｇＲａｎｄｏｍ ＳｐａｎｎｉｎｇＴｒｅｅＧｒｏｕｐｏｆＧｒａｐｈｓ
ＤＯＮＧＺｈａｎｇｚｈｕｏ１，ＬＵＯＨｕｉ２，ＱＩＹａｎｇ１
（１．ＣｏｌｌｅｇｅｏｆＥｌｅｃｔｒｏｎｉｃＥｎｇｉｎｅｅｒｉｎｇ，Ｘｉ＇ａｎＳｈｉｙｏｕＵｎｉｖｅｒｓｉｔｙ，Ｘｉ＇ａｎ，Ｓｈａａｎｘｉ７１００６５，Ｃｈｉｎａ；
２．ＣｏｌｌｅｇｅｏｆＥｌｅｃｔｒｉｃａｌａｎｄＣｏｎｔｒｏｌＥｎｇｉｎｅｅｒｉｎｇ，Ｘｉ＇ａｎＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｘｉ＇ａｎ，Ｓｈａａｎｘｉ７１００５４，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｏｂｔａｉｎｉｎｇｔｈｅｓｐａｎｎｉｎｇｔｒｅｅｇｒｏｕｐｏｆａｌａｒｇｅｓｃａｌｅｃｏｎｎｅｃｔｅｄｇｒａｐｈｉｓｏｎｅｏｆｔｈｅｔｙｐｉｃａｌｍｅｔｈｏｄｓｔｏｓｏｌｖｅｅｎｇｉｎｅｅｒｉｎｇｐｒｏｂ
ｌｅｍｓ．Ａｉｍｉｎｇａｔｔｈｅｐｒｏｂｌｅｍｓｏｆｌｏｎｇｃａｌｃｕｌａｔｉｏｎｔｉｍｅａｎｄｔｈｅｇｒａｄｕａｌｄｅｃｒｅａｓｅｏｆｃａｌｃｕｌａｔｉｏｎｅｆｆｉｃｉｅｎｃｙｗｉｔｈｔｈｅｉｎｃｒｅａｓｅｏｆｇｒａｐｈｓｃａｌｅ，
ａｒａｎｄｏｍｓｐａｎｎｉｎｇｔｒｅｅｇｒｏｕｐｓｏｌｖｉｎｇａｌｇｏｒｉｔｈｍｆｏｒｃｏｎｎｅｃｔｅｄｇｒａｐｈｉｓｐｒｏｐｏｓｅｄ．Ｆｉｒｓｔｌｙ，ｔｈｅｓｉｍｐｌｉｆｉｃａｔｉｏｎｒｕｌｅｓａｒｅｄｅｆｉｎｅｄ，ｔｈｅｒａｄｉａ
ｔｉｏｎｐａｔｈｓｉｎｔｈｅｃｏｍｐｌｅｘｇｒａｐｈｔｈａｔｄｏｎｏｔｉｎｖｏｌｖｅｔｈｅｓｐａｎｎｉｎｇｔｒｅｅｇｅｎｅｒａｔｉｏｎｐｒｏｃｅｓｓａｒｅｄｅｌｅｔｅｄ，ａｎｄｔｈｅｂｒａｎｃｈｅｓｉｎｔｈｅｍｕｔｕａｌｌｙ
ｅｘｃｌｕｓｉｖｅｂｒａｎｃｈｓｅｔａｒｅｃｏｍｂｉｎｅｄｔｏｏｂｔａｉｎａｓｉｍｐｌｉｆｉｅｄｇｒａｐｈ．Ｔｈｅｎｔｈｅｓｐａｎｎｉｎｇｔｒｅｅｇｒａｐｈｃｏｒｒｅｓｐｏｎｄｉｎｇｔｏｔｈｅｓｉｍｐｌｉｆｉｅｄｇｒａｐｈｉｓ
ｏｂｔａｉｎｅｄｂｙｒａｎｄｏｍｌｙｓｅｌｅｃｔｉｎｇｂｒａｎｃｈｅｓｉｎａｒｏｕｌｅｔｔｅｗａｙｂｅｔｗｅｅｎｔｈｅｓｉｍｐ
一种新的生成树组随机求取算法 董张卓 来自淘豆网m.daumloan.com转载请标明出处.
