噢噢噢噢噢噢噢噢噢噢噢噢噢噢噢噢被加精力！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
感谢@AC君谢谢谢谢谢谢谢谢谢谢
小萌新发帖，望大佬支持
孩子们这并不好笑，但谁知道我有一天心血来潮作死想把近1000字的笔记打到电脑上去
正文：
图论基础
一，图的概念
1，定义：图是一种由顶点和边组成的非线性数据结构，顶点表示数据内容，边表示关系
2，分类：(1),无向图(或称为“无向网络”“无向图形”)：由没有方向的边组成的图
(2),有向图：由有方向的边组成的图
(3),权图：边上带有权值的图（权值：边的权重(weight)）
3，简单图和多重图：
(1),自环和重边：
①，自环：边的两端是同一个节点
②，重边：连接同两个结点的多条边
(2),简单图：不存在自环和重边的图
(3),多重图：存在自环和重边的图
4，图的度：指与一个结点相连的边的数量
(1),无向图：与目标节点相连的边数
(2),有向图：
①，入度：指向该节点的边数
②，出度：从该节点出发的边数
5，路径：
(1),定义：从一个结点到另一个结点的连续边构成的序列
(2).路径长度：一路径中经过边的数量(或权值和)
(3),分类：
①，简单路径：从一个节点到另一个结点的不重复序列
②，非简单路径：从一个节点到另一个结点的可重复序列
注意：有向图的路径必须遵循边的方向
6，环路：
(1),定义：起点和终点相同的路径
(2),分类：
①，简单环路：起点和终点相同的不重复路径
②，非简单环路：起点和终点相同的可重复路径
注意：不包括任何环路的图叫无环图
7，连通图：
(1),定义：任意两点间都存在路径的图(可以不是直接路径)
(2),分类：①强连通图；②若连通图；③非连通图。
注意：强连通图和弱连通图是相对的
8，完全图：
(1),无向完全图(UCG)：
①定义：图中任意两点间均存在一条无向边
②边数：n(n-1)/2
(2),有向完全图(DCG):
①定义：图中任意两点间均存在方向相反的两条边
②边数：n(n-1)
9，稠密图和稀疏图(相对概念)
(1),稀疏图：图中边较少，边之间连接相对稀疏
(2),稠密图：图中边较多，边之间连接相对稠密
二，图的存储
1，目标：存储图的顶点信息和边信息
2，方法：
(1),邻接矩阵：一维数组+二维数组
①一维数组V[i]：存储i顶点的信息
②二维数组G[i][j]：存储边的信息(如:权值，端点，这个需要用到结构体进行绑定)，G[i][j]表示从顶点i到j这条边
③优点：时间复杂度低(仅为O(1))
④缺点：需求的空间过大
有向图单项存储，无向图双向存储
适用于稠密图
例：(无向图)
输入：5 5 | 1 2 | 2 3 | 3 4 | 4 5 | 5 1 ("|"表示换行)
特殊性质：无向图的邻接矩阵关于x = y对称
(2),邻接表：vector数组，结构体(常用)
①vector数组：存储顶点的所有邻接点和边的数据
②结构体：将边与权值绑定
③优点：省空间
适用于稀疏图
例：(无向图)
输入：5 5 | 1 2 | 2 3 | 3 4 | 4 5 | 5 1 ("|"表示换行)
三，图的遍历
1，图的深度优先遍历：
例：
给定一个无向图，
第一行输入两个数字n,m，分别代表无向图的顶点数和边数
接下来m行，输入两个数字u,v代表u,v间有一条无向边，保证该图是连通图
遍历所有节点并输出
2，图的广度优先遍历：(个人比较喜欢用这个，因为手贱想多打点更习惯广搜的逻辑)
例：
给定一个无向图，
第一行输入两个数字n,m，分别代表无向图的顶点数和边数
接下来m行，输入两个数字u,v代表u,v间有一条无向边，保证该图是连通图
遍历所有节点并输出
四，推荐题目
图的题单
个人觉得比较基础的题与较难的题都在这里面了，欢迎各位大佬们来尝尝咸淡
来道题吧
T41351.连接组件数
这道题很简单，就是遍历一遍看谁没有被标记就进去广搜并计数即可
再来一个
这个稍难一点，那也只需在队列弹出后计数即可
T45469.连通块问题(BFS)
(看看我这个小透明吧码字好累)求赞@AC君
