广度优先搜索在图论中的应用 计算机专业VIP免费

广度优先搜索在图论中的应用摘要：本文详细地分析了广度优先搜索算法，重点研究了该算法在图论中的应用，尤其是在最短路径问题中的应用。通过与其它最短路搜索算法的比较分析，本文得到了这些最短路算法之间的关系。关键词：广度优先搜索，最短路径，图论。Abstract：thispapergivesadetailedanalysisofthebreadth-firstsearchalgorithm,andemphasisonthealgorithmintheapplicationofgraphtheory,especiallyintheshortestpathproblemintheapplication.Throughthecomparativeanalysiswiththeothershortestpathsearchalgorithm,thispaperobtainstheserelationshipsbetweentheseshortestpathalgorithms.Keywords:breadthfirstsearch,shortestpath,graphtheory.目录摘要---------------------------------------------------------------------------------0Abstract-----------------------------------------------------------------------------0一、引言------------------------------------------------------------------------2二、广度优先搜索算法------------------------------------------------------2(一)基本思想----------------------------------------------------------------2(二)算法结构----------------------------------------------------------------4(三)算法特性----------------------------------------------------------------5(四)广度优先搜索算法在图论中的应用-------------------------------6三、广度优先搜索算法在图论中应用的具体分析---------------------7(一)寻找连接元件----------------------------------------------------------7(二)测试是否二分图-------------------------------------------------------7(三)寻找非加权图中任两点的最短路径-------------------------------7四、最短路中常用算法的比较---------------------------------------------9五、总结-----------------------------------------------------------------------10参考文献--------------------------------------------------------------------------10附件--------------------------------------------------------------------------------11一、引言使用计算机求解的问题中，有许多问题是无法用数学公式进行计算推导和采用模拟方法来找出答案的。这样的问题往往需要我们根据问题所给定的一些条件，在问题的所有可能解中用某种方式找出问题的解来，这就是所谓的搜索法或搜索技术。常见的搜索算法有广度优先搜索法（简称为BFS）、深度优先搜索法、双向广度优先搜索法，A*算法、回溯法、枚举法、分支定界法等。图论是数学的一个分支,以图为研究对象。这种图由若干给定的点和连接两点的线构成,借以描述某些事物之间的关系。用点代表事物,用连接两点的线表示两个事物之间具有特定关系。图论起源于18世纪,追朔到1736年瑞士数学家L.Euler出版第一本图论著作,提出和解决著名Konigsberg七桥问题。从那时以来,图论不仅在许多领域,如计算机科学,运筹学,心理学等方面得到了广泛的应用,而且学科本身也获得长足发展,形成了拟阵理论,超图理论,代数图论,拓扑图论等新分支。本文讨论广度优先搜索在图论中的应用。1二、广度优先搜索算法(一)基本思想采用广度优先搜索算法解答问题时，需要构造一个表明状态特征和不同状态之间关系的数据结构，这种数据结构称为结点。根据问题所给定的条件，从一个结点出发，可以生成一个或多个新的结点，这个过程通常称为扩展。结点之间的关系一般可以表示成一棵树，它被称为解答树。搜索算法的搜索过程实际上就是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的结点的过程。广度优先搜索算法中，解答树上结点的扩展是沿结点深度的“断层”进行，也就是说，结点的扩展是按它们接近起始结点的程度依次进行的。首先生成第一层结点，同时检查目标结点是否在所生成的结点中，如果不在，则将所有的第一层结点逐一扩展，得到第二层结点，并检查第二层结点是否包含目标结点，...对长度为n+1的任一结点进行扩展之前，必须先考...