图的应用数据结构实验报告(图的知识点数据结构)

图是数据结构学科中最难的关键章节，也被认为是近两年考试的重点。这部分图包含很多概念、算法和难点。这就需要大家深入理解每个知识点，多做练习，掌握规律，才能答好这部分试题。这部分图要求大家掌握图的定义、特点、存储结构、遍历以及基本应用。图这部分的重点和难点是图的基本应用，这在2009年和2010年的考试中都有体现。图的基本应用包括：最小生成树、最短路径、拓扑排序、关键路径等。 2009年考试的重点是最短路径的判断和证明。文都教育考研组建议大家重点复习图表的基本应用。

下面介绍图的基本应用：

1.最小生成树

1.最小生成树的基本概念

最小生成树：边权值之和最小的生成树。最小生成树有许多重要的应用。《计算机学科专业基础综合辅导讲义》介绍了最小生成树在城市建设中的应用。

2. 最小生成树的性质最小生成树的性质：假设G=(V,E)是一个连通网络，U是顶点集V的真子集。如果(u,v)是G中的一条边，一个端点在U中（例如：uU），另一个端点不在U中（例如：vV-U），并且（u，v）具有最小权重，则必须存在G的最小生成树，包括这条边（u，v）。

3构建最小生成树的算法

有许多用于构造最小生成树的算法。建议大家重点复习一下构建最小生成树的两种常用算法：Prim算法和Kruskal算法。

2.最短路径

最短路径问题是与日常生活密切相关的问题，例如路径选择、计算机网络路由选择等，也是考试的重点之一。《计算机学科专业基础综合辅导讲义》 最短路径问题分两种情况讨论。

最短路径算法：

1.Dijkstra算法

Dijkstra算法的主要特点是从起点逐层向外扩展，直至延伸到终点。

定义G=(V,E)，定义集合S存储已找到最短路径的顶点，集合T存储尚未找到最短路径的顶点，即T=V-S：

Dijkstra算法描述如下：

(1) 假设带权有向图由带权邻接矩阵边表示，edges[i][j]表示弧Vi和Vj上的权重。如果Vi和Vj不存在，则设置edges[i][j]=（用计算机上允许的最大值替换）。 S是从Vs开始找到的最短路径的端点集合，并初始化为空集。那么，从Vs到图上剩余顶点（端点）Vi可能到达的最短路径长度的初始值为：D[i]=deges[s][i] ViV

(2)选择Vj，使得D[j]=Min{D[i]|ViV-S}，Vj是当前获得的从Vs开始的最短路径的终点。设S=S{Vj}

(3)修改从Vs到集合V-S上任意顶点Vk所能到达的最短路径长度。若D[j]+edges[j][k]D[k]，则将D[k]修改为D[k]=D[j]+edges[j][k]

重复操作(2)(3)总共n-1次。由此，获得从Vs 到图上剩余顶点的最短路径。

2.Floyd算法

Floyd算法的核心思想是通过其权重矩阵找到图的每两点之间的最短路径矩阵。

建议大家重点掌握这两种最短路径算法，多做练习巩固。《计算机学科专业基础综合辅导讲义同步练习》 应用Floyd算法解决中岛娱乐中心选址问题。

3. 拓扑排序

1.拓扑排序的基本概念

AOV网络是一个有向图，可以形象地反映整个项目中各个活动之间的关系。在AOV网络中，如果不存在循环，所有的活动都可以按照线性顺序排列，使得每个活动的所有前驱活动都排列在这个活动的前面，那么这个序列就是一个拓扑序列。

2.拓扑排序特点：

(1)拓扑序列不唯一。

(2)AOV网络不一定具有拓扑序列。如果AOV网络中出现有向环，则意味着某项活动应以自身为先决条件。这是错误的，该项目将无法实施。

大家要注意拓扑排序的应用，例如：用拓扑排序来判断一个图中是否存在环。

4. 关键路径

如果在一个带权有向图中，顶点代表事件，有向边代表活动，边上的权重代表完成该活动的成本（比如该活动所需的时间），那么这个带权有向图就称为如图所示AOE网络。

在AOE网络中，起始顶点和结束顶点之间的最大路径长度是关键路径。由于AOE网络中的一些子项目（活动）可以同时进行，为保证每个子项目都能完成，完成该项目的最短时间就是AOE网络的关键路径长度。项目。

这部分要求大家能够解决关键路径。同步练习和《计算机学科专业基础综合考试全真模拟试题集》都配有相应的练习。

现在我们已经进入备考的最后冲刺阶段，建议在做模拟题的时候，应该选择与真题一致、难度与真题非常接近的模拟题，并严格按照考试时间做模拟题。

  相关文章:

  第1篇    减法的四种算法(减法的四个运算定律)    作者：admin

   8月底，考研大纲即将公布。预注册将于9月进行，正式注册将于10月进行。考研初试离我们越来越近了。朋友们早出晚归，努力复习、收集各种材料。很多人的状态可以用“忙、累、慌、乱”来形容。是不是意味着复习越努力、收集的信息越多，考研成功的概率就越大呢？并非如此。考研，你要学

  第2篇    mpa管理类联考考什么(管理类mpa联考过国家线难吗)    作者：admin

   1.学校声誉虽然MPA的学习内容与各学校的基础课程非常相似，但附加课程却明显不同，具有很强的特色。课程的设置和重点与各学校的专业特长和教学领域有很大关系。例如，对外经济贸易学校有以海关为主的课程，农业院校有以农业或扶贫为主的课程等。考生在选择时应根据自己的喜好考虑学校的声

  第3篇    考研政治真题试卷pdf(考研政治真题试卷2022)    作者：admin

   摘要本文主要从五个角度论证研究生政考试卷的重要性和必要性。首先，研究生政治考试试卷是研究生政治考试的重要组成部分。掌握真题真题可以帮助你更好的应对考试。其次，通过分析真题，可以了解考研政治的考点和命题思路，有助于提高备考效果。第三，通过分析真题，可

  第4篇    云南大学2021年硕士研究生拟录取(2020年云南大学研究生)    作者：admin

   云南大学研究生2023录取摘要云南大学是云南省重点大学之一，以优良的学风和丰富的研究资源而闻名。随着时间的流逝，云南大学2023年研究生招生即将拉开帷幕。本文将从五个角度论证并详细介绍云南大学2023年研究生招生的重要性以及招生政策的变化。1.录取政策的变化云南大学的研究生招生政策将随着时间的推移进行调整，以更好地适应当今社会的需求。2023年招生

  第5篇    南京大学的新闻传播研究生好考吗(南京大学新闻传播专业考研)    作者：admin

   南京大学新闻传播硕士考研经验摘要本文旨在分享我作为南京大学新闻与传播专业研究生的经历。我将从多个角度来论证这一点，包括准备计划、复习方法和技巧、面试准备、学术研究和准备阶段的实践经验。本文总结了我在考研期间所学到的知识，希望对即将考