【免费】20151910042-刘鹏-AG实验01-图搜索算法1资源-CSDN文库

需积分: 0 100 浏览量 2022-08-08 17:45:38 上传评论收藏 1.05MB DOCX 举报

资源详情

资源评论

资源推荐

·

1

·

云南大学数学与统计学院

《算法图论实验》上机实践报告

课程名称：算法图论实验

年级：2015 级

上机实践成绩：

指导教师：李建平

姓名：刘鹏

专业：信息与计算科学

上机实践名称：图搜索算法

学号：20151910042

上机实践日期：2018-12-31

上机实践编号：1

组号：

一、实验目的

1. 理解广度优先搜索算法的具体步骤；

2. 学会读开源的代码库，并逐步学会使用这些代码库完成扩展性的实验。

二、实验内容

1. 用形式化伪代码表示图的广度优先搜索算法；

2. 借助开源代码库，完成高质量的广度优先搜索算法编程。

三、实验平台

Windows 10 Pro 1809；

MacOS Mojave 10.14.2；

Python 2；

四、算法设计

本次理论课上所讲的 Searching 算法在图论中一般被称为广度优先的图遍历算法（Breath First Searching,

BFS）。在一定规则下循环地使用这个算法可以对一个图进行遍历，并得到所有的连通子图（连通分支）。

这个算法十分重要，它是 Dijkstra 算法以及更一般的 Prim 算法的基础与原型。下面对 Searching 算法（广度优

先图遍历算法）进行形式化描述。

Algorithm

Input

Output

Begin

Step 1

图的反圈遍历算法，记此算法为

SEARCH

图

G

=

(V, E)

，并假定图

G

是无向图；

图

G

中的某个起点

v

自

v

1

出发所有有路可到达的点以及路过的边所构成的诱导子图，记之为

ε

-

CLOSURE

=

SEARCH

(

G

,

v

1

)

// 初始化染色

for each vertex

u

∈

(

V

―

{v})

:

剩余12页未读，继续阅读

评论0

内容反馈

SeaNico

粉丝: 17
资源: 321

最新资源

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

feedback-tip