图论理论基础

图的概念

0个以上的节点及节点之间边构成了图。0个节点就是空图。

图的种类

有向图：边有方向

无向图：边无方向

加权有向图

加权无向图

度

属于节点的概念。

无向图中有几条边连接该节点，该节点就有几度。

在有向图中，每个节点有出度和入度。

出度：从该节点出发的边的个数。

入度：指向该节点边的个数。

连通性

连通图

无向图中，任意两个节点都可到达，为连通图。

如果有节点不能到达其他节点，则为非连通图。

强连通图

有向图中，任意两个节点都可相互到达，为强连通图。

连通分量

无向图中的极大连通子图称之为该图的一个连通分量。

强连通分量

有向图中的极大强连通子图称之为该图的强连通分量。

图的构造

朴素存储

把所有边存下来，也就是把边的两个节点存下来，因为两个节点就能代表一条边。因此可以用数组，也可以用map，或者类，都能表示这种边的关系。

优点：直观。

缺点：但如果我们想知道两个节点是否相连，我们就需要把存储空间都枚举一遍才行。

同时，我们在深搜和广搜的时候，都不会使用这种存储方式。

邻接表

使用数组+链表的方式。从变得数量来表示图， 有多少边就有多大链表。

有多少边 邻接表才会申请多少个对应的链表节点。

邻接矩阵

使用二维数组表示图结构。从节点的角度表示图，多少个节点就多大的二维数组。

隐患：在 边少，节点多的情况下，会导致申请过大的二维数组，造成空间浪费

优点：表达简单、检查两个节点之间的连通情况非常快、适合稠密图

缺点：不适合稀疏图

图的遍历方式

深搜和广搜，支持不同的数据结构。二叉树章节我们已见识过。