图的正式定义是什么

图的正式定义是：G = (V, E)

注意，V和E都是集合哦。

V是顶点的集合，而E是边的集合。

我画个图来举例吧：

如上图，令V1 = {1, 2, 3, 4}，E1 = {a, b, c, d, e}，就有图G1 = (V1, E1)。

值得一提的是，图的这些边可以用示例中a、b…这些字母来表示，也可以用顶点对来表示。

比如边c，我们观察下就知道，边c连接顶点1和顶点3，我们就可以将c写成(1, 3)。

还有，我们通常用n表示图的顶点数，用m表示图的边数。

还是以上图的图G1为例，n = 4，m = 5。

在计算机程序中表示图的主要方式是有邻接矩阵、关联矩阵、邻接表。

图G1的邻接矩阵、关联矩阵、邻接表分别为：

来个不恰当的比喻，我们看这个邻接矩阵，有点像正方形。

这是因为，有n个顶点的图G，它的邻接矩阵是n * n矩阵。

邻接矩阵里的元素要么是0要么是1。规则是这样的：如果顶点i和顶点j相邻，那么邻接矩阵的元素(i, j)为1。若不相邻，则为0。

所以我们不难知道，图的邻接矩阵是“对称矩阵”。

而关联矩阵则不然，它就不是对称的。

有n个顶点m条边的图G，它的关联矩阵是n * m矩阵。矩阵的行对应各顶点，列对应各边。

在图G中，如果顶点i和边j关联，那么关联矩阵的元素(i, j)为1，反之为0。

我们可以发现，在图的关联矩阵中，每列都恰好有两个1，这是符合逻辑的。（因为每个边两端都有一个顶点）

最后来聊聊“邻接表”。邻接表是一种链表，它以图的顶点为起点，将与该顶点关联的边以任意顺序连接起来。