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

2023-12-14 22:49:02

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


目录

一.图的基本概念

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

三.图的遍历

四.图的应用


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

????????图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://blog.csdn.net/jsl123x/article/details/135003532
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。