图的基本性质#

1.自环（self-loop）#

如果一个边只包含一个节点，那么它被称为自环。如下图。即同一个节点是起点也是终点。

一个常见的栗子就是网站，在当前网站点击网站开发者挂在当前网站的自身url，那么只会刷新一下，而不是去往新的网站。

2.多重边（multiedge）#

第一条多重边是无向的，第二条是有向的。

（ps:有向图：必须是 同方向 的多条边才算（比如 A→B 有两条），反方向（A→B 和 B→A）不算多重边！）

为什么需要有这个特性？

显而易见，你坐过高铁吗？

两个城市有不同铁道，他们的距离不同，要花费的费用不同，我们想要在图上呈现这些信息，所以多重边是必要的。

很好，有了自环和多重边纯纯是让图变得复杂了，没有二者的图叫做简单图。😱

3.简单提问#

给定顶点的数量，在一个简单图中，最大的边数是多少？

简单吗？光靠脑子想是想不出来滴！

我们来画个图吧。

我们来画四个节点的，多了不画，为什么？不要问。😭

显而易见，边的最小值可以是0.

一个顶点可以连接3个别的节点，所以最大边数是12！如图所示！

很乱吧，所以才画4个顶点，绝非偷懒为之！😋

所以我们可以得出结论。

对于有向图来说，顶点的数量为n，那么0<=|E|<=n(n-1)

对于无向图来说就不一样了，两个节点之间只能由一条双向边，否则就构成了多重边，所以最大边数是6，也就是有向图最大边数量的一半。

如果图中的边数量接近最大的可能边数比如接近n的平方，那么我们说这个图是稠密的。（Dense）

如果很少，比如接近顶点的数量，那么这个图是稀疏的。

这个定义是模糊的，没有准确数值的。

我们通常使用一个所谓的邻接矩阵来存储稠密的图，对于稀疏的我们则采用邻接表来存储。

4.路径#

一个图的路径是顶点的序列，序列中每个相邻对通过一条边的链接。

比如这里的路径就是<A.B.F.H>

如果顶点没有重复的，那么边也是没有重复的，**所以这样的路径被称为简单路径。**大部分时候，当我们说路径的时候我们的意思是简单路径。

所以我们通常定义无重复为“通路”（walk），路径则是简单路径的意思。

下图有一个边，两个顶点是重复的。

如果路径中的顶点可以重复但是边不能重复，那么称为trail，如下图。

所以我们现在有了三个名词。

💡 关系： Path ⊂ Trail ⊂ Walk （所有路径都是迹，所有迹都是行走，但反过来不成立！）

5.强连接#

一个图被称为强连接的条件是从任意顶点可以来到任意的其他顶点。

如果是无向图，我们可以直接称其为连接的。如果是一个有向图，我们可以称为强连接的。

如果将中间的图的所有边看作无向的，那么它就可以被转换成强链接，所以他被称为弱连接。

如果删去左边图的B和c中间的边，那么我们就可以将其称为未连接的。图的连接性是一个重要的属性！

6.环#

一个walk行走被称为是一个闭回路，也就是它的起点和结束都在同一个顶点，并且途径的长度必须比0大。途径或者路径的长度是这条路径的边数。

下图里长度是4，因为walk上有四条边。绿色的walk构成了一个闭合的环。

我们通常把简单的环（simple cycle）称为就是一个闭合的途径，除了起点，其他的顶点和边都不能重复。

一个没有循环的图被称为无环图（acyclic graph），典型的就是树。

有向无环图（directed acylic graph）也叫DAG，如下图。

图的环会有许多问题！比如从一个顶点到另一个顶点的最短路径设计算法