关于图论【理论基础】

一、图的种类

1、无向

2、有向

3、权值

二、各种度

1、度

2、出度

3、入度

三、连通性

1、连通图

2、强连通图

3、连通分量

4、强连通分量

// 连通图是指无向图的连通性

// 强连通图（只要有多一个“强”字，就是有向图）指有向图的连通性

// 连通分量(/强连通分量)前提是连通(/强连通)、关键是“极大”

//（子图是基础）

// 接下来以无向图的连通分量举例

// 一个无向图可以有多个连通分量（例如上图中顶点123是一个连通分量，顶点45也是一个）

// （只要符合“子图、连通、极大”，就是一个连通分量）

四、图的构造

1、朴素存储

2、邻接矩阵

3、邻接表

// 引出邻接矩阵

// 引出邻接表

【总结】

邻接矩阵适合顶边多的稠密图（稠密图就是边很多）

邻接表适合边少的稀疏图（稀疏图就是边很少）

五、图的遍历

DFS（Depth-First Search，深度优先搜索）深搜

BFS（Breadth-First Search，广度优先搜索）广搜