DS冲刺整理做题定理(三)图论合集

这篇具有很好参考价值的文章主要介绍了DS冲刺整理做题定理(三)图论合集。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

第三期,总结性地来说一下图论,也是数据结构中最核心最难的一章~

DS冲刺整理做题定理(三)图论合集,数据结构,图论,数据结构,算法,考研


目录

一.图的基本概念

二.图的存储及其基本操作

三.图的遍历

四.图的应用


        在数学中,图是描述于一组对象的结构,其中某些对象对在某种意义上是“相关的”。这些对象对应于称为顶点的数学抽象(也称为节点或点),并且每个相关的顶点对都称为边(也称为链接或线)。通常,图形以图解形式描绘为顶点的一组点或环,并通过边的线或曲线连接。

        图G=(V,E)是一个二元组(V,E)使得E⊆[V]的平方,所以E的元素是V的2-元子集。为了避免符号上的混淆,我们总是默认V∩B=Ø。集合V中的元素称为图G的定点(或节点、点),而集合E的元素称为边(或线)。通常,描绘一个图的方法是把定点画成一个小圆圈,如果相应的顶点之间有一条边,就用一条线连接这两个小圆圈,如何绘制这些小圆圈和连线时无关紧要的,重要的是要正确体现哪些顶点对之间有边,哪些顶点对之间没有边。

        图可用于在物理、生物、社会和信息系统中建模许多类型的关系和过程,许多实际问题可以用图来表示。因此,图论成为运筹学、控制论、信息论、网络理论、博弈论、物理学、化学、生物学、社会科学、语言学、计算机科学等众多学科强有力的数学工具。在强调其应用于现实世界的系统时,网络有时被定义为一个图,其中属性(例如名称)之间的关系以节点和或边的形式关联起来。

一.图的基本概念

1.完全图:有n(n-1)/2条边的无向图~

2.子图:某个图边集和点集的子集所构成的生成子图~

3.连通:在任意两个顶点之间都存在着边~(无向图的极大连通子图称为连通分量)

4.对于有向图:如果任意两点之间都有双向路径,则该图被称为强连通的;有向图中的极大强连通子图称为有向图的强连通分量~

5.生成树:包含图中所有顶点的一个极小连通子图~

(极小连通子图:既要保持图连通又要使得边数最少得子图~)

6.简单路径:顶点不重复出现的路径~

二.图的存储及其基本操作

1.邻接矩阵:将结点之间的关系存储在一个矩阵中,无向图和有向图的略有不同~

2.邻接表法:将每个节点所连通的结点以链表的方式接在后面,并以此类推~

3.十字链表:专用于有向图的链式结构,分为弧结点和顶点结点两种,对于Vi的尾和头都容易找到

4.邻接多重表:专用于无向图的链式结构,同样分为两种结点~

三.图的遍历

1.DFS:深度优先搜索,类比图的先序遍历~

2.BFS:广度优先搜索,类比与二叉树的层序遍历~

四.图的应用

1.最小生成树:生成树包含所有顶点,并且尽可能包含少的边;若某棵生成树的权值之和最小,则其称为最小生成树~

2.Prim是根据边来构造最小生成树的过程,克鲁斯卡尔算法则是通过每次挑选权值最小的边~

3.迪杰斯特拉算法用于计算单源最短路径,而弗洛伊德则可以找到所有顶点之间的最短路径~

4.拓补排序,关键路径暂不赘述~文章来源地址https://www.toymoban.com/news/detail-773879.html

到了这里,关于DS冲刺整理做题定理(三)图论合集的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 算法分析与设计考前冲刺 (算法基础、数据结构与STL、递归和分治、 动态规划、贪心算法、 回溯算法)

    算法分析与设计考前冲刺 算法基础 算法是一系列解决问题的清晰指令,代表着用系统的方法描述解决问题的策略机制。 程序是算法用某种程序设计语言的具体的 具体实现 算法特征: 有穷性(有限步) 确定性 输入 输出 可行性(有限时间) 算法的复杂性: 时间复杂性 和空间复

    2024年02月02日
    浏览(42)
  • 数据结构【DS】Ch6 图

    2024年01月20日
    浏览(35)
  • 离散数学 --- 图论基础 --- 子图和补图,握手定理

    1.生成子图:点集合不变,边集合是原图的边集合的子集 2.导出子图:点集合是原图点集合的非空子集V,然后再在原图的边集合中找到两个端点均在点集合V中的边元素,并将这些边元素称成一个新的边集合,得到的这个边集合就是导出子图的边集合 (点集合V和得到的新的边

    2023年04月08日
    浏览(42)
  • 全面理解链表数据结构:各种节点操作、做题技巧,易错点分析与题目清单(C++代码示例,不断更新)

    链表是一种线性数据结构,它包含的元素并不是物理上连续的,而是通过指针进行连接。链表中的每个元素通常由一个节点表示,每个节点包含一个数据元素和一个或多个链接(指针)。 链表的主要类型包括: 单向链表 (Singly Linked List):每个节点包含一个指向下一个节点

    2024年02月07日
    浏览(41)
  • 【数据结构】实验六:图论

    采用邻接矩阵表示法创建无向图G ,依次输出各顶点的度。 输入格式: 输入第一行中给出2个整数i(0i≤10),j(j≥0),分别为图G的顶点数和边数。 输入第二行为顶点的信息,每个顶点只能用一个字符表示。 依次输入j行,每行输入一条边依附的顶点。 输出格式: 依次输出各顶点的

    2024年02月05日
    浏览(46)
  • NeuDs 数据结构 图论

    在一个有权无向图中,若 b 到 a 的最短路径距离是12,且 c 到 b 之间存在一条权为2的边,则 c 到 a 的最短路径距离一定不小于10。 T 解析: 我们首先来分析b-a有几种可能,首先是b到a有直接的路径,其次b通过其他的结点到达a点。 如果是b通过c点到达a点我们就可以知道,min{

    2024年02月08日
    浏览(41)
  • 【图论基础数据结构及其应用】

    本文主要介绍Java中图论基础数据结构的基本原理、实现方式以及使用场景。图论是研究非线性方程组及其解的数学领域,广泛应用于计算机科学中,如网络拓扑、交通网络、地理信息系统等。 图是由节点(Vertex)和边(Edge)组成的数据结构。节点表示图中的对象或实体,而

    2024年02月12日
    浏览(48)
  • 【数据结构】排序合集(万字详解)

    排序,以字面意思来说就是通过特定的算法将一组或多组无序或者接近有序的数据,以升序或者降序的方式重新进行排序组合; [7,4,2,9,8,6,5,1,3]; 以升序的方式进行排序最终为: [1,2,3,4,5,6,7,8,9]; 排序算法就是如何使得数据按照要求排列的方法; 排序的算法多种多样,基本的排序

    2024年02月08日
    浏览(36)
  • CAP定理整理

    CAP定理是分布式系统设计中最基础、最关键的理论,CAP定理又称CAP原则,指的是在一个分布式系统中,Consistency(一致性)、 Availability(可用性)、Partition tolerance(分区容错性), 最多只能同时三个特性中的两个 ,三者不可兼得 Consistency (一致性): “all nodes see the same dat

    2024年02月07日
    浏览(33)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包