本文主要是介绍代码随想录算法训练营第三十九天| 图论理论基础,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
今天是图论入门的第一天,主要的学习内容主要是图论的理论基础。
图论理论基础
图的种类
图一般可以分为有向图和无向图,无向图是指边没有方向,有向图是指边有方向,其中,还存在一种加权有向图,指的是每条边上带有一定的权重。
有向图
无向图
加权有向图
图的度
接下来的一个概念是节点的度,指的是有几条边连接这个节点。
对于有向图,则可以细分为出度和入度,出度指的是从该节点出现的边,入度指的是指向该节点的边。例如对于节点3,出度为1,入度为2.
图的连通性
在无向图中,任意两个节点都是可以到达的,我们称为连通图,相反则称为非连通图。
连通图
非连通图
除此之外,对于有向图,如果任意两个节点都是可达的,我们称之为强连通图。
图的构造
构造图一般有两种方法,即邻接表和邻接矩阵。
邻接表就是用一个二维数组对图进行存储,如果i点指向j点,那么grid[i][j]=1;对于无向图,grid[i][j]和grid[j][i]都为1.邻接表在存储点多边少的数据时会申请过大的二维数组,造成空间浪费。不适合用于存储稀疏图。
邻接表存储方法
邻接矩阵是另一种图的存储方式,使用数组+链表的方式进行存储。
如图所示,节点1指向节点3和节点5,节点2指向节点4,节点3和节点5,以此类推。邻接表在存储稀疏图时有更好的空间利用率,但检查任意两节点是否存在边效率较低。
图的遍历方法
图的遍历方法主要分为两周:深度优先搜索(DFS),广度优先搜索(BFS)。
这篇关于代码随想录算法训练营第三十九天| 图论理论基础的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!