图论法.docx资源-CSDN文库

版权申诉

66 浏览量 2023-03-13 21:00:47 上传评论收藏 252KB DOCX 举报

资源推荐

资源详情

资源评论

图论算法

图论算法在计算机科学种扮演者很重要的角色，它提供了对很多问题都有效的一

种简单而系统的建模方式。很多问题都可以转化为图论问题，然后用图论的基本算法

加以解决。遗传算法是解优化问题的有效算法，而并行遗传算法是遗传算法研究中的

一个重要方向，受到了研究人员的高度重视。

特点：一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或

方案，数学上把这种问题称为最优化或优化（optimization）问题；二是它们都易于用图形

的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network）。与图和网络

相关的最优化问题就是网络最优化或称网络优化（netwok optimization）问题。

哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛

及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回

到起点。当

然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个

问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相

应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一

点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一

个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问

题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。

深度优先搜索、广度优先搜索、无向图、有向图、最小生成树、最短路径。

求最短路迪克斯特拉（Dijkstra）算法，其基本思想是按距u 从近到远为顺序，依次求

0

得 u 到G 的各顶点的最短路和距离，直至v （或直至G 的所有顶点），算法结束。为避免

0

0

重复并保留每一步的计算信息，采用了标号算法。下面是该算法。

(u )  0

v  u

( )   S  {u }

，令l v

 0

，i 。

(i) 令 l

，对

，

0

0

0

0

 S S  V \ S

），用

(ii) 对每个v

（

i

i

i

min {l(v),l(u)  w(uv)}

uS

i

代替l

(v)

。计算

m in{l(v)}

，把达到这个最小值的一个顶点记为

S  S {u }

，令。

u

i1

i1

i

i1

vS

i

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余6页未读，立即下载

内容反馈

版权申诉

คิดถึง643

粉丝: 3917
资源: 1万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip