新的二部图判定算法

• 作者: 王青松
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 二部图 二部图判定 广度优先遍历
• 年，卷（期）: 2009,（z1）
• 所属期刊栏目: 数据库与知识工程
• 页码范围: 181-183
• 页数: 3页
• 分类号: TP391.41
• 字数: 3265字
• 语种: 中文

摘要

二部图是现代图论中一类非常重要的图,然而关于其判定的充要条件却很少,而且用算法实现它们很复杂.需要指数级的时间代价.利用图的广度优先遍历,提出了一个易于实现的二部图判定的充要条件:无向图G是二部图当且仅当G的广度优先生成森林中的同一层上的任意两点在G中不邻接.给出了该判定条件的实现算法,算法的时间复杂度是O(n2),很好地解决了二部图的判定问题.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王青松	辽宁大学信息学院	20	83	5.0	9.0