关于图论【理论基础】

一、图的种类1、无向2、有向3、权值二、各种度1、度2、出度3、入度三、连通性1、连通图2、强连通图3、连通分量4、强连通分量// 连通图是指无向图的连通性// 强连通图只要有多一个“强”字就是有向图指有向图的连通性// 连通分量(/强连通分量)前提是连通(/强连通)、关键是“极大”//子图是基础// 接下来以无向图的连通分量举例// 一个无向图可以有多个连通分量例如上图中顶点123是一个连通分量顶点45也是一个// 只要符合“子图、连通、极大”就是一个连通分量四、图的构造1、朴素存储2、邻接矩阵3、邻接表// 引出邻接矩阵// 引出邻接表【总结】邻接矩阵适合顶边多的稠密图稠密图就是边很多邻接表适合边少的稀疏图稀疏图就是边很少五、图的遍历DFSDepth-First Search深度优先搜索深搜BFSBreadth-First Search广度优先搜索广搜