6.1 图的定义和基本术语

  • **稀疏图:**有很少边或弧的图(e<nlogn) 。记为TD(v)稠密图:有较多边或弧的图。
    **网:**边/弧带权的图。
    **邻接:**有边/弧相连的两个顶点之间的关系。(圆括号表示无序，尖括号表示有序)
    存在(v_i, v_j)，则称vi和vj互为邻接点;
    存在<v_i; v_j>，则称vi邻接到vj,vj邻接于vi

**关联(依附):**边/弧与顶点之间的关系。
存在(v, v)/，则称该边/弧关联于v,和vj

  • 当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时称其为有向树。

6.3 图的类型定义

6.4 图的存储结构

6.4.1 邻接矩阵表示法

分析1:无向图的邻接矩阵是对称的;
分析2:顶点i的度=第i行(列)中1的个数;
特别:完全图的邻接矩阵中，对角元素为0，其余1。

分析1:有向图的邻接矩阵可能是不对称的。
分析2:顶点的出度=第i行元素之和;顶点的入度=第i冽元素之和;

算法实现无向网：

邻接矩阵——有什么好处?
直观、简单、好理解
方便检查任意一对顶点间是否存在边
方便找任一顶点的所有“邻接点”(有边直接相连的顶点)
方便计算任一顶点的“度”(从该点发出的边数为“出度”，指向该点的边数为“入度”)

邻接矩阵——有什么不好?
不便于增加和删除顶点
浪费空间——存稀疏图（点很多而边很少)有大量无效元素)
浪费时间——统计稀疏图中一共有多少条边

6.4.2 邻接表

  • 如果边/弧上有权值，表结点可以多加一个数据
  • 邻接表不唯一
  • 若无向图中有n个顶点.e条边，则其邻接表需n个头结点和2e个表结点。适宜存储稀疏图。
  • 无向图中顶点v_i的度为第i个单链表中的结点数。

算法实现：

邻接矩阵和邻接表之间的关系

1.联系:
邻接表中每个链表对应于邻接矩阵中的一行，链表中节点个数等于一行中非零元素的个数
2.区别:
对于任一确定的无向图，邻接矩阵是唯一的(行列号与顶点编号—致)，但邻接表不唯一（链接次序与顶点编号无关)。
邻接矩阵的空间复杂度为O(n^2)，邻接表的空间复杂度为O(n+e)。前者多用于稠密图，后者稀疏图

*6.4.3 十字链表和多重邻接表