代码随想录 图论理论基础

一、图的基本概念：

1.图的概念：二维坐标中，两点可以连成线，多个点连成的线就构成了图。当然，图也可以就一个节点，甚至没有节点（空图）。

2.图的种类：整体上，图一般分为有向图和无向图。

（1）有向图：图中的边是有方向的。

（2）无向图：图中的边是没有方向的。

（3）加权有向图：图中的边是有权值的。

（4）加权无向图：同理。

3.度：

（1）无向图的度：在无向图中，有几条边连接该节点，该节点就有几度。如下图所示，在该无向图中，节点4的度为5，节点6的度为3。

（2）有向图的度：在有向图中，每个节点有出度和入度。出度是指从该节点出发的边的个数，入度是指指向该节点的边的个数。如下图所示，在该有向图中，节点3的入度为2，出度为1；节点1的入度为0，出度为2。