保研复习数据结构-图(10)

这篇具有很好参考价值的文章主要介绍了保研复习数据结构-图(10)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一.图的定义和基本术语

1.什么是图?

图(Graph)是由顶点的有穷非空集合V(G)和顶点之间边的集合E(G)组成,通常表示为:G=(V,E),其中,G表示图,V是图G中顶点的集合,E是图G中边的集合。

2.什么是完全图(Completed graph)?

对于有n个顶点的无向图,边e的数目为 0 ~ n(n-1)/2,对于无向完全图,共有n(n-1)/2条边。对于有向图,边的数目是0 ~ n(n-1),有向完全图的边数为n(n-1)。有很少条边或弧的图称为稀疏图(Sparse graph),反之称为稠密图(Dense graph)。

3.什么是网(Network)?

带权的图,权是指边或弧上带有相应的数字。

4.什么是子图(Subgraph)?

图的顶点集的子集and图的边集的子集

5.一个图的所有顶点的度数的和的一半等于边数:

6.什么是图中的回路或环(Cycle)?

第一个顶点和最后一个顶点相同的路径称为回路或者环。

7.什么是连通图(Connected Graph)?

如果对于图中任意两个顶点Vi和Vj都有路径,那么说明这个图是连通图。

8.什么是连通分量(Connected component)?

指的是无向图中的极大连通子图=子图and连通图

9.什么是强连通图?什么是强连通子图?

对于有向图中的连通图,和有向图中的连通分量。

10.什么是生成树(Spanning Tree)?

生成树是一个连通图的极小连通子图,它包含树所需的全部顶点。顶点数为n的生成树一定含有n-1条边。如果一个含有n个顶点的图的边数小于n-1,那么这个图一定是非连通图;如果边数大于n-1,那么一定包含环。

11.什么是生成森林?

对应于非连通图,是由多个生成树组成的包含图中所顶点的森林。

二.最小生成树(Minimum Cost Spanning Tree)

1.什么是最小生成树?

所有边代价和最小的生成树称为最小生成树

2.Prim算法和Kruskal算法利用的是最小生成树的什么性质?

MST性质:假设N=(V , { E })是一个连通网,如果U是顶点集V的一个非空子集,如果存在一条权重(代价)最小的边使得,那么必然存在一棵包含的最小生成树。

3.Prim算法是什么?

Prim算法基于贪心对于连通加权无向图来选择最小生成树的算法,每次选出一条距离已有最小生成树最短的边加入到集合中,最终实现最小生成树

具体流程:

  1. 用两个集合A{}和集合B{}分别表示找到的点集和未找到的点集。
  2. 对于元素a属于A,元素b属于B,选择一条最小的边(a,b)加入最小生成树
  3. 直到A=V,B为空

4.Kruskal算法是什么?

Prim算法是基于点,Kruskal算法是基于边。

先将边从小到大排列,从小到大添加不构成环路的边,由于要排序,所以复杂度为O(nlogn)

  1. 将边按照权重从小到大排列
  2. 枚举第一个边,加入MST里,判断是否成环
  3. 如果成环则跳过,否则确定这条边为MST里的
  4. 继续枚举下一条边,直到所有的边都枚举完

三.拓扑排序(Topological Sort)

1.什么是拓扑排序?

针对于有向无环图,只有有向无环图才存在拓扑排序。拓扑排序是针对有向无环图的拓扑序列,这个序列满足:(1)每个顶点出现且仅出现一次(2)如果存在一条从A到B的路径,那么A一定在B的前面

2.拓扑排序的过程?

  1. 选择一个没有前驱(入度为0)的顶点
  2. 删除这个顶点和所有以它为起点的边
  3. 重复操作12,直到整个图为空或者剩余结点,后一种状况说明图存在环路。

四.关键路径(Critical Path)

1.什么是关键路径?

关键路径是针对于AOE(Activity on edge)来说的,AOE中边表示活动,权重表示活动持续的时间,顶点表示事件。所有有最早开始时间和最晚开始时间相同的事件组成的路径为关键路径。

2.关键路径的求解步骤?

  1. 绘制项目网络图,标志个活动的持续时间和活动之间的逻辑关系。
  2. 计算每个活动的最早开始时间(ES)和最晚开始时间(LS),以及最早完成时间(EF)和最晚完成时间(LF) 。
  3. 计算每个活动的浮动时间,即LS-ES或LF-EF。
  4. 找出浮动时间为零的活动,这些活动所构成的路径就是关键路径。

五.最短路径(Minimum Path)

1.迪杰斯特拉算法(单源最短路径)

  1. 从所有未访问的点中,找出当前距离最小的,设为u,并将其标记为已访问的。
  2. 调整u的所有边(若是有向图则为出边)连接的并且未被访问过的点:若weight[u->v] + dist[u] < dist[v], 则将dist[v]更新为dist[u]+weight[u->v]。
  3. 重复1和2步骤,直到所有点都被标记为已访问的,则dist[i]即s到i的最短距离。如果只想求从s到某一点的最短距离,那么当该点被标记为访问过之后可直接退出。
  4. 补充:如果除了最短距离之外还想求出具体的路径,只需建立一个pre数组,在步骤2后添加操作:pre[v] = u(前提是dist[v]被更新)。

2.弗洛伊德算法(多源最短路径)

弗洛伊德算法可以给出图中任意两个结点之间的最短路径,比迪杰斯特拉更一般。

Foyd算法的思想是将n个节点的网络表示为n行n列的矩阵,而矩阵中的元素(i,j)表示从节点i到节点j的距离,如果两点直接没有边相连,则相应的元素就是无穷().文章来源地址https://www.toymoban.com/news/detail-847994.html

  1. 邻接矩阵dist储存路径,同时最终状态代表点点的最短路径。如果没有直接相连的两点那么默认为一个很大的值(不要溢出)!而自己的长度为0.
  2. 第1个到第n个点依次加入图中。每个点加入进行试探是否有路径长度被更改。
  3. 而上述试探具体方法为遍历图中每一个点(i,j双重循环),判断每一个点对距离是否因为加入的点而发生最小距离变化。如果发生改变,那么两点(i,j)距离就更改。
  4. 重复上述直到最后插点试探完成。

到了这里,关于保研复习数据结构-图(10)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构(期末总复习)

    目录 第一章 绪论 第二章 线性表 线性表常用操作辨析总结 第三章 栈和队列 第四章 串 第五章 数组与广义表 第六章 树 1.结构体成员的类型必须是基本数据类型。(F) 原因: 结构体成员类型不只是基本数据类型,同时也可以是另一种结构体类型,也可以是指针类型,同时也

    2024年02月03日
    浏览(46)
  • 数据结构复习+答案

    一、选择题:(每小题2分,共30分) 1、在数据的逻辑结构中,树结构和图结构都是( ) A.非线性结构 B.线性结构 C.动态结构 D.静态结构 2.在一个长度为n的顺序表中插入一个元素的算法的时间复杂度为( ) A.O(1) B.O(log n) C.O(n) D.O(n2) 3.指针p1和p2分别指向两个无头

    2024年02月12日
    浏览(41)
  • 数据结构复习

    什么是数据结构?数据结构是抽象数据类型的物理实现 抽象数据结构,怎么理解抽象 数据结构 抽象数据类型:对数据类型的描述,这种描述是抽象的,描述1.数据对象集,2.与数据集合关联的操作集 抽象:不依赖于具体实现,只描述是什么,不涉及如何做到 数据对象类型的抽

    2024年02月10日
    浏览(31)
  • 【数据结构】复习题(一)

    一、选择题 1.组成数据的基本单位是()。 A. 数据项 B.数据类型 C.数据元素 D.数据变量 2.设数据结构A={D,R},其中D={1,2,3,4},R={r},r={1,2,2,3, 3,4,4,1},则数据结构A是()。 A.线性结构 B.树型结构 C.图型结构 D.集合 3.数组的逻辑结构不同于下列()的逻辑结构。 A.线性表 B.栈 C.队列 D.树 4.二

    2024年02月04日
    浏览(43)
  • 数据结构期末复习(2)链表

    链表(Linked List)是一种常见的数据结构,用于存储一系列具有相同类型的元素。链表由节点(Node)组成,每个节点包含两部分:数据域(存储元素值)和指针域(指向下一个节点)。通过节点之间的指针连接,形成一个链式结构。 链表可以分为单向链表和双向链表两种类型

    2024年02月03日
    浏览(52)
  • 数据结构与算法--pta复习

    拓扑序一定是唯一的 F 如果从有向图 G 的每一点均能通过深度优先搜索遍历到所有其它顶点,那么该图一定不存在拓扑序列 T AOE图的权值最大的边(活动)一定是关键活动  F 在关键路径上的活动都是关键活动,而关键活动也必在关键路径上。T 关键路径是AOE网中从源点到汇

    2024年01月16日
    浏览(42)
  • 【数据结构】期末考试复习(考点+例题)

    线性表,栈,队列- 操作应用结果 树的构造,遍历(中序),存储,哈夫曼树,最佳二叉排序树,平衡二叉排序树, 散列(必考)快速查找,函数构造,冲突地址,平均查找长度 排序算法结果,代码(交换,比较次数,对应过程,复杂度)不考冒泡! 图的存储,遍历,最小

    2024年02月11日
    浏览(54)
  • 数据结构复习题(包含答案)

    1、研究数据结构就是研究( D  )。 A. 数据的逻辑结构                      B. 数据的存储结构    C. 数据的逻辑结构和存储结构    D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是(  A )。 A. 空间复杂度和时间复杂度         B. 正

    2024年02月09日
    浏览(36)
  • 数据结构,第8章:排序(复习)

    目录 直接插入排序: 1. (程序题) 折半插入排序: 希尔排序: 3. (程序题) 冒泡排序 : 2. (程序题) 快速排序 : 5. (程序题)  简单选择排序: 4. (程序题) 堆排序: 6. (程序题) 前置知识:  稳定排序:如果有两个相等的元素在排序前后的相对顺序保持不变,那么排序算法是

    2024年02月04日
    浏览(29)
  • 软考复习之数据结构篇

    目录 算法设计 算法复杂度 概率算法 存储结构 顺序存储 链式存储 单链表 循环链表 双链表 散列存储 索引存储 树 二叉树 满二叉树 完全二叉树 四种遍历方式 前序遍历 中序遍历 后序遍历 层序遍历 哈夫曼树(最优二叉树) 二叉排序树 平衡二叉树 森林 树转二叉树 二叉树转

    2024年02月19日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包