前置知识:

连通图: 图上任意两点之间,都有路径,那么这个图就是连通图.

强连通图: 图上任意两点之间,都有一条边直接相连.

最大联通子图: 一个图的连通子图,如果加入任意一个其他的顶点,都会导致该子图不再连通,那么这个子图就是原来这个图的一个最大连通子图.

无向图: 图中的边没有方向—其实是双向的.

有向图: 图中的"边"(弧)有方向—只能从弧的起点到弧的终点—单向的.

边: 没有方向的,双向的.

弧: 有方向约束,不能反方向.

有权(重)图: 边的代价.

公式:

n个顶点的连通无向图,最多有多少条边(握手定理)= $n*(n-1)/2$ ,最少有多少条边= $n-1$ .

…

邻接矩阵概述

什么是邻接:

邻接: 2个相邻的点,就是邻接.

邻接矩阵是一种用于表示图的数据结构.实际上就是个二维数组—是个方阵.

在邻接矩阵中,行和列都对应图的顶点,如果两个顶点之间存在一条弧,那么对应的矩阵元素就是1（或者是边的权重,对于带权图）,否则就是0.

矩阵的行和列分别代表一条边的起点和终点,即第i行第j列的元素,代表顶点i到顶点j是否有一条边.

此外,对于无向图,由于边是双向的,所以第 $i$ 行第 $j$ 列的元素和第 $j$ 行第 $i$ 列的元素是相同的(在该方阵中关于主对角线对称),都表示顶点 $i$ 和顶点 $j$ 之间是否存在边.

但对于有向图,行和列的意义就有所不同了.如果我们有一条从顶点 $i$ 指向顶点 $j$ 的边,那么在邻接矩阵中,第 $i$ 行第 $j$ 列的元素会是1（或者是边的权重,对于带权图）,而第 $j$ 行第 $i$ 列的元素会是0,除非还存在一条从顶点 $j$ 指向顶点 $i$ 的边.

例如,对于以下图,我们可以创建相应的邻接矩阵：

对应的邻接矩阵为：

优缺点

优点:

缺点:

空间消耗大

邻接矩阵的空间复杂度为O(n^2),其中n为顶点数.因此,对于顶点数非常多,但边数相对较少的稀疏图来说,邻接矩阵可能会浪费大量的空间.

因此,邻接矩阵更适合表示边数相对较多的稠密图.

可以很容易地使用二维数组来实现它.对于无权图,使用0和1来表示边的存在与否；对于带权图,使用特殊值（例如最大的整数）来表示边的不存在.