1、定义及相关概念

• 图G由顶点集V和边集E组成，记为G=(V,E)，其中V(G)表示图G中顶点的有限非空集合，E(G)表示图G中顶点之间的关系（边）的集合。
  1 图的定义
• 无向图（连通）和有向图（强连通：双向）
• 连通图和强连通图
  任意两个节点之间都是连通/强连通的。
  连通分量：极大连通子图
  强连通分量：极大强连通子图
• 简单图和多重图
  简单图：无重复边无节点到自身的边
• 完全图：全连接
• 子图：G'=(V',E')是子图则有V'是V的子集，E'是E的子集。
• 生成树和生成森林
  生成树：连通图包含全部顶点的一个极小连通子图
  生成森林：非连通图所有连通分量的生成树组成生成森林
• 顶点的度
  无向图：以该顶点位端点的边的数目TD(v)
  有向图：
  出度：以v为起点的有向边的个数，记为OD(v)
  入度：以v为终点的有向边的个数，记为ID(v)
• 稠密图和稀疏图
  边多和边少，界定：|E|<|V|log|V|
• 有向树
  顶点入度为0，其余顶点入度为1的有向图
• 路径、路径长度、距离、回路

2、存储结构

（1）邻接矩阵

结点数为n的如邻接矩阵A是n*n的。顶点编号，若有向边<vi,vj>∈E，则 A[i][j]=1，否则为0；

2 邻接矩阵
3 邻接矩阵定义方法 顶点类型，边类型，顶点数组，边二维数组，顶点数目，边数目

空间复杂度为O(n²)，适用于稠密图。矩阵运算Aⁿ的含义：Aⁿ[i][j]表示从顶点vi到vj长度为n的路径的条数。

（2）邻接表

对于稀疏图，邻接矩阵会有很多浪费。
定义：为每一个顶点建立一个单链表存放与他相邻的边。两种表

• 顶点表：顺序储存，存放顶点的数据和边表的头指针
  -（出） 边表：链式存储，存放一个顶点所有的出边，一个链表节点表示一条从该顶点到链表节点顶点的边

  
  4 邻接表结点结构
  

  data存放顶点的值，firstarc存放单链表头指针；adjvex存放弧头的值，nectarc存放下一个边表结点的地址

  
  5 邻接表图示
  6 邻接表语言定义
  特点：空间复杂度无向图O(|V|+2*|E|)有向图O(|V|+|E|)；适用于稀疏图。
  7 对比邻接图和邻接表

（3）十字链表

邻接表找结点的入边要遍历所有链表，太麻烦。十字链表便于寻找入边和出边。定义：有向图的一种链式储存结构。
firstin入边单链表的头指针； firstout出边单链表的头指针；

8 十字链表结点结构

tailvex尾域弧尾；headvex头域弧头；hlink指针域，弧头相同的下一条边；tlink指针域，弧尾相同的下一条边；info边的权重。

9 十字链表语言结构

（4）邻接多重表

邻接表删除无向图结点时，要遍历两个链表。无向图的链式存储结构。
ivex该边的第一个端点；ilink与该端点相邻的下一个边表结点的指针；jvex第二个端点； jlink与第二个端点相邻的下一个边表结点的指针。

10 邻接多重表结点结构
11 邻接多重表语言结构

3、遍历方法

（1）DFS

（2）BFS

图片.png

4、应用

（1）最小生成树

（2）最短路径

（3）拓扑排序

有向无环图简称DAG；AOV顶点表示一个活动；拓扑排序对DAG所有顶点的排序。

拓扑排序算法思想

（4）关键路径