Open youngyangyang04 opened 2 months ago
图论章节给大家统一换成ACM输入输出模式,图论是在笔试还有面试中,通常都是以ACM模式来考察大家,而大家习惯在力扣刷题(核心代码模式),核心代码模式对图的存储和输出都隐藏了。
而图论题目的输出输出 相对其他类型题目来说是最难处理的。
ACM模式是最考察候选人对代码细节把控程度的, 图的构成,图的输出,这些只有ACM输入输出模式才能体现出来。
如果熟练ACM模式,那么核心代码模式没问题,但反过来就不一定了。
而且还有不少题目,力扣上没有题,例如 Bellman_ford系列 ,Floyd ,A* 等等,索性统一我自己来出题,这其中也是巨大的工作量。为了给大家带来极致的学习体验,我在很多细节上都下了功夫。
等大家将图论刷完,就会感受到我的良苦用心。加油
初学图论打卡
图的概念
分类:有向图是指 图中边是有方向的,无向图是指 图中边没有方向。加权有向图,就是图中边是有权值的。加权无向图也是同理。 度:无向图中有几条边连接该节点,该节点就有几度。在有向图中,每个节点有出度和入度。 连通:在无向图中,任何两个节点是可以相互到达的,我们称之为连通图 。极大连通子图称之为该图的一个连通分量。在有向图中,任何两个节点是可以相互到达的,我们称之为强连通图。极大连通子图称之为该图的一个强连通分量。
图的构造
邻接矩阵:邻接矩阵使用二维数组来表示图结构,是从节点的角度来表示图,有多少节点就申请多大的二维数组。 邻接表:邻接表 使用 数组 + 链表的方式来表示。
图的遍历
深度优先搜索(DFS)、广度优先搜索(BFS)。也可以在不同的数据结构上进行搜索:二叉树的递归遍历是 DFS,二叉树的层序遍历是 BFS。而在图论章节,则是在邻接表或邻接矩阵上进行搜索。
一刷没完结,二刷重启打卡
现在没事就翻了看看。感觉卡尔的文章写的真的通俗易懂,非常适合小白入门。
https://www.programmercarl.com/kamacoder/%E5%9B%BE%E8%AE%BA%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html