一、图的存储方式种类

1、邻接矩阵法（最常考）

适用于：【有向图】和【无向图】都可以

• 1、先了解【无向图】和【有向图】怎么用【邻接矩阵】表示（写法）
  • 【无向图】：两个点直接连有边就是【1】、没有直接连着边就是【0】
    • 因此主对角线为0，矩阵是关于主对角线对称的【对称矩阵】
    • A[i][j]=A[j][i]（无向图一定是对称矩阵！！！）
  • 【有向图】：A与B有边并且A指向B，则A行B列为【1】；而B与A右边但被A指向、或B与A没边则为【0】
    • 因此主对角线为0，矩阵通常无法构成矩阵
    • 但是！！当各个连有边的点，互相指向，则可以构成【对称矩阵】
    • 也就是说：
      • 【对称邻接矩阵】不一定是无向图【（也可以是有向图）】
      • 但【不对称的邻接矩阵】一定是【有向图】
      • 一定要注意有向图的这个点
• 2、邻接矩阵查一个【顶点的度】
  • 【无向图】：该顶点的1行【或】1列的【非零元素个数】；
  • 【有向图】：【入度】是1【列】的非零元素；【出度】是1【行】的非零元素
    • 【时间复杂度】：O(n) 或 O(|V|)
• 3、邻接矩阵的【空间复杂度】：O(n^2)
• 4、【带权图（网）】的邻接矩阵表示：就是标上了【确切权值】，而不只是0、1
  • ​​​​​​​主对角线的值都是【0】
  • 没有边的值是【∞】
    • 注意：
      • 那么其实本质上只不过是把【有边是数值1】改成了【有边数值是全值】
      • 把【没边是数值0】改成了【没边数值是∞】
      • 所以【无向图】中一个顶点的度还是【它的行的非∞、非0元素个数】或【它的列的非∞、非0元素个数】
      • 【有向图】中一个顶点的【入度】还是【它的列的非∞、非0元素个数】、【出度】还剩【它的行的非∞、非0元素个数】
• 5、还有一种邻接矩阵是【A[i][j]^n】
  • 【次幂：n】就是表示这个邻接矩阵里，记录的【值1】代表【这两点之间：存在1条长度是n的路径】、【值k】代表【这两点之间：存在k条长度是n的路径】
  • 记录的【值0】表示【这两点之间：不存在长度为n的路径】
  • 注意：【值为1】、【值为k】、【值为0】都与【这两点间有无边】没有关系

【记忆特点】

• 邻接矩阵使用的是【顺序存储】（一维数组、二维数组）
• 【空间复杂度高：O(n^2)】
  • 而且【空间跟 “边” 没有关系！！！】
  • （注意区分：时间复杂度是O(n)）
• 不适合存储【稀疏图】、适合【稠密图】
  • 大量顶点之间没有边，却还要用【0 或 无穷】来存储，占用空间
• 而且【增加 / 删除节点】麻烦！！！需要修改整个矩阵结构

 【例题】

2、邻接表法（次常考）

适用于：【有向图】和【无向图】都可以

• 1、先了解【无向图】和【有向图】怎么用【邻接表】表示（写法）
  • 注意代码可以看一眼就行，以后要练大题的话再专门学一下就行
  • 另外这个图可以结合《计网第4章：路由算法》的迪杰斯特拉算法，一样的表示
• 2、邻接表的【空间复杂度】：
  • 无向图：O(|V| + 2|E|)
  • 有向图：O(|V| + |E|)
• 3、邻接表【查一个顶点的度】
  • 【无向图】：遍历该顶点后的【边链表节点个数】；
  • 【有向图】：
    • 【出度】是该顶点的【边链表节点个数】
    • 【入度】是该顶点【作为边表节点出现的次数】所以统计一个点的【出度：方便】、【入度：麻烦】！！！！
    • 【注意】！！！
      • 【无向图】：【边表节点个数】一定是【偶数个】
      • 【有向图】：【边表节点个数】一定是【奇数个】
• 4、重要！！！
  • 【邻接表】表示形式不唯一！！！边链表的节点顺序不唯一！！！
  • 【邻接矩阵】表示形式唯一！！！只有一种形式！！！

【记忆特点】

• 邻接表使用的是【链式存储】（单链表）
• 【空间复杂度低】：无向O(|V| + 2|E|)、有向O(|V| + |E|)
  • 适合存储【稀疏图】（不会浪费节点去记录【没有边】的值）
  • 注意：邻接表占用空间大小与【顶点数】和【边】都有关系
• 【时间复杂度】：n个顶点、e条边的图
  • 【有向图时间复杂度】=【无向图时间复杂度】：O( n + e )​​​​​​​
  • 【某点删除边】：同理！！
    • ​​​​​​​除了【有向图删出度】：O( n )
    • 【删某点所有边】=【删某点入度边】：O( n + e )
    • 反正反复记住【有向图的度】、【出度】都有可能遍历完【所有链表的孩子节点】！！！！
• 【出度方便】、【入度麻烦】！！！！
  • ​​​​​​​因为是【孩子表示法】
  • 【出度】：统计一个“父亲”它指向的“孩子节点个数”
  • 【入读】：统计该点作为“孩子”，在所有孩子节点出现的次数

【例题】

3、十字链表法（不常考，时间紧的可以略看一眼）

适用于：只适用于【有向图】

【记住】：

• 1、表示的是【有向图】！！！！！！！！！！！！！！
• 2、它的每个顶点节点后面的单链表，指的是【顶点的出弧表】！！！
  • 可以发现每个顶点后的【弧链表】每个节点的【头】，都是【此顶点】
  • 表示的意思：这就是【这个顶点】的【出度的弧】
  • 比如：V1的编号0，他出去的弧有<V1, V2>(0 , 1)、<V1, V3>(0 , 2)
• 3、每个顶点的第二格指【该顶点的入弧】
  • 只需要把【弧节点表】的节点里，【第二格】是【该顶点】的全连起来就行
  • 比如：图片里我用颜色标注了，同颜色的都连起来了，连这些节点的编号，都是同一顶点

【例题】

4、邻接多重表法（不常考，时间紧的可以略看一眼）

适用于：只适用于【无向图】

【记住】：

• 1、表示的是【无向图】！！！！！！！！！！！！！！
• 2、它的每个顶点节点后面的单链表，指的是【连了该顶点的边】！！！
  • 可以发现每个顶点后的【边链表】每个节点的【头】，都是【此顶点】
  • 表示的意思：这就是连着【这个顶点】的【边】
  • 比如：V1的编号0，他出去的弧有<V1, V2>(0 , 1)、<V1, V4>(0 , 3)
• 3、剩下所有节点的【空格】，只要前面编号一样，都连起来
  • 比如：图片里我用颜色标注了，同颜色的都连起来了，连这些节点的编号，都是同一顶点

【例题】

5、总结（各个存储方式对比）

二、图的基本操作

理解一下就行，黄色部分记住，大题选择题都会用到