生成有向图中全部简单回路的一种有效算法-计算机应用与软件.PDFVIP

第２６卷第１２期　　　 计算机应用与软件 Ｖｏｌ２６Ｎｏ．１２ ０９ ２００９年１２月　　 ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅ Ｄｅｃ．２０ 生成有向图中全部简单回路的一种有效算法 １，２ ２ ２ 王玉英 　陈　平 　苏　 １（西安建筑科技大学理学院　陕西西安７１００５５） （ ２（西安电子科技大学软件工程研究所　陕西西安７１００７１） 摘　要　　在研究有向图中全部简单回路现有算法的基础上，综合各算法的优点提出一种新的算法。算法的主要思想是对图中顶 点进行深度优先有哪些信誉好的足球投注网站，在有哪些信誉好的足球投注网站过程中采取措施避免同一回路的重复出现，同时记录有用信息避免对顶点的重复访问，从而提高算法 的效率，还给出了算法的证明和实例应用。算法结构清晰简单，方便转化为计算机程序。 关键词　　有向图　简单有向回路　深度优先有哪些信誉好的足球投注网站　算法 ＡＮＥＦＦＩＣＩＥＮＴＡＬＧＯＲＩＴＨＭＯＦＧＥＮＥＲＡＴＩＮＧＡＬＬＥＬＥＭＥＮＴＡＲＹ ＣＩＲＣＵＩＴＳＩＮＤＩＲＥＣＴＥＤＧＲＡＰＨ １，２ ２ ２ ＷａｎｇＹｕｙｉｎｇ 　ＣｈｅｎＰｉｎｇ　ＳｕＹａｎｇ １（ＳｃｈｏｏｌｏｆＳｃｉｅｎｃｅ，Ｘｉ’ａｎＵｎｉｖｅｒｓｉｔｙｏｆＡｒｃｈｉｔｅｃｔｕｒｅａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｘｉ’ａｎ７１００５５，Ｓｈａａｎｘｉ，Ｃｈｉｎａ） ２（ＳｏｆｔｗａｒｅＥｎｇｉｎｅｅｒｉｎｇＩｎｓｔｉｔｕｔｅ，ＸｉｄｉａｎＵｎｉｖｅｒｓｉｔｙ，Ｘｉ’ａｎ７１００７１，Ｓｈａａｎｘｉ，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ　　Ｂａｓｅｄｏｎｓｔｕｄｙｉｎｇｅｘｉｓｔｉｎｇａｌｇｏｒｉｔｈｍｓｗｉｔｈｒｅｇａｒｄｔｏａｌｌｅｌｅｍｅｎｔａｒｙｃｉｒｃｕｉｔｓｉｎｄｉｒｅｃｔｅｄｇｒａｐｈ，ａｎｅｗａｌｇｏｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄｂｙｉｎ ｔｅｇｒａｔｉｎｇｔｈｅａｄｖａｎｔａｇｅｓｏｆｔｈｅｓｅａｌｇｏｒｉｔｈｍｓ．Ｔｈｅｍａｉｎｔｈｏｕｇｈｔｏｆｉｔｉｓｔｈｅｄｅｐｔｈｆｉｒｓｔｓｅａｒｃｈｏｆｖｅｒｔｅｘｉｎｇｒａｐｈｗｉｔｈｓｐｅｃｉａｌｍｅａｓｕｒｅｔａｋｅｎｔｏｉｎ ｓｕｒｅｎｏｃｉｒｃｕｉｔｉｓｒｅｐｅａｔｅｄｌｙｆｏｕｎｄｄｕｒｉｎｇｔｈｅｓｅａｒｃｈｉｎｇｐｒｏｃｅｓｓ，ｍｅａｎｗｈｉｌｅｓｏｍｅａｖａｉｌａｂｌｅｉｎｆｏｒｍａｔｉｏｎｉｓｒｅｃｏｒｄｅｄｆｏｒａｖｏｉｄｉｎｇｄｕｐｌｉｃａｔｅｄｖｉｓｉｔｓ ｔｏｓａｍｅｖｅｒｔｅｘ，ｉｎｔｈｉｓｗａｙｉｔｉｍｐｒｏｖｅｓｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅａｌｇｏｒｉｔｈｍ．Ｔｈｅｐｒｏｏｆｏｆｔｈｅａｌｇｏｒｉｔｈｍａｎｄｉｔｓａｐｐｌｉｃａｔｉｏｎａｒｅｇｉｖｅｎａｓｗｅｌｌ．Ｉｔｉｓｃｏｎ ｖｅｎｉｅｎｔｔｏｔｒａｎｓｆｏｒｍｔｈｉｓａｌｇｏｒｉｔｈｍｔｏａｃｏｍｐｕｔｅｒｐｒｏｇｒａｍ，ｆｏｒｉｔｓｓｔｒｕｃｔｕｒｅｉｓｃｌｅａｒａｎｄｓｉｍｐｌｅ． Ｋｅｙｗｏｒｄｓ　　Ｄｉｒｅｃｔｅｄｇｒａｐｈ　Ｅｌｅｍｅｎｔａｒｙｄｉｒｅｃｔｉｏｎａｌｃｉｒｃｕｉｔ　Ｄｅｐｔｈｆｉｒｓｔｓｅａｒｃｈ　Ａｌｇｏｒｉｔｈｍ 简单回路。 ０　引　言 １．１　算法的主要思想 算法是基于深度有限有哪些信誉好的足球投注网站的。 在计算机科学中，经常