6.1 图的基本概念
| 基本元素 | G=(V,E) | V(G) | E(G) | |V|>0 | |E| | | 度 | 度TD(v) | 入度ID | 出度OD | | | | 路径 | 回路/环 | 简单路径 | 简单回路 | 路径长度、距离 | | | 有向图衍生概念 | 有向边/弧<v,w> | 弧尾v | 弧头w | v邻接到w | | | 无向图衍生概念 | 无向边/边(v,w) | w和v互为邻接点 | 边(v,w)依附于w和v | 边(v,w)和w,v相关联 | | | AOE网衍生概念 | 开始顶点/源点 | 结束顶点/汇点 | 关键路径（路径长度最大） | 关键活动（关键路径上的活动） | |
图的分类：
| 不相交的概念1 | 不相交的概念2 | 衍生概念 | | 有向图 | 无向图 | | | 有向完全图 | （简单/无向）完全图 | | | 强连通图（有向图） | 连通图、非连通图（都是无向图） | | | 简单图 | 多重图 | | | 稀疏图 | 稠密图 | | | 连通分量=极大连通子图（边最多） | 生成树=极小连通子图（边最少） | | | 生成子图（顶点数不变） | | | | 带权图/网 | | 边的权值 | | 有向树 | | | | AOV网∈有向无环图DAG（可表示表达式） | AOE网∈DAG | 拓扑排序 |
6.2 图的存储
| 邻接矩阵 | 邻接表 | 十字链表 | 邻接多重表 | | 顶点结点 | 一维数组（可省略） | 顶点表：顺序存储 | 顺序存储 | 顺序存储 | | 边结点 | 二维数组 | 边表/出边表：单链表 | 弧结点：十字链表 | 链表 | | 优点 | | 易得到顶点的出度 | 易求得顶点的出度和入度 | 比邻接表更易判断两点间的关系 | | 缺点 | 占用空间大 | 不易得到顶点的入度 | | | | 适用范围 | 无向图、有向图、带权图/网 | 无向图、有向图 | 有向图 | 无向图 | | 其他 | 邻接矩阵A^n的元素=由顶点i到顶点j的长度为n的路径数目 | 逆邻接表的优缺点与之相反 | | 所有依附于同一顶点的边串联在同一链表中；边结点跟边一一对应 |
6.3 图的遍历
| 广度优先搜索BFS | 深度优先搜索DFS | | 类似于树的遍历 | 二叉树的层序遍历 | 树的先序遍历 | | 辅助 | 队列 | 递归工作栈 | | 是否递归 | 否 | 是（因为需往回退） | | 需辅助数组标记是否被访问过 | 是 | 是 | | 原理——外循环 | 外循环次数=子图个数 | 同左 | | 原理——内部——初始化 | 内循环第一步：对外循环的当前顶点先访问再压入队列中 | 访问当前顶点 | | 原理——内部——循环 | 当队列不空时：出队列——其邻接点依次访问并入队列 | 遍历当前顶点的邻接点，重走“内部”函数 | | 空间复杂度 | 辅助队列→O(|V|) | 递归工作栈→O(|V|) | | 时间复杂度——邻接表 | 每个顶点至少入队一次+搜每个点的邻接点时每个边至少访问一次=O(|V|)+O(|E|) | 同左 | | 时间复杂度——邻接矩阵 | 查找每个点的邻接点需O(|V|)→O(|V|^2) | 同左 | | 应用 | 生成广度优先生成树 | 生成深度优先生成树/森林 | | 应用 | 求非带权图的单源最短路径d(v_0,v_i)：令v_0为BFS外循环的第一个结点 | |
6.4 图的应用
| 最小生成树MST——Prim | 最小生成树MST——Kruskal | 最短路径——Dijkstra | 最短路径——Floyd | 拓扑排序 | | 使用范围 | 非带权图、带权图（MST唯一） | 同左 | 带权图：单源最短路径 | 带权图：每对顶点间 | AOV网 | | 类似方法 | Dijkstra | | Prim | | | | 原理——初始化 | 任选一个顶点 | 每个顶点自成一个连通分量 | 把源点放入集合S，
dist[]初始值dist[0]=arcs[0][i] | 邻接矩阵 | 将没前驱的顶点入栈，选一个出栈 | | 原理——循环 | 添加最小权值且不构成回路的边 | 同左 | 选出最小权边并将顶点v_j放入S，
修改V-S中的每个顶点v_k：若dist[k]>dist[j]+arcs[j][k]则令左=右 | 依次把各个顶点作为中介顶点，即依次令k=0,1…n，并修改矩阵元素值：
? | 将与其相连的点入度-1，并将入度变为0的点入栈 | | 时间复杂度 | O(|V|^2) | 用堆存放边故每次选最小权边需O(log|E|)*用并查集描述生成树=O(|E|log|E|) | O(|V|^2) | O(|V|^3) | 删除顶点+删除相应的边=O(|V|+|E|) | | 适用于 | 边稠密的图 | 边稀疏而顶点较多的图 | 权值为正 | 不允许带负权的边成回路 | 邻接矩阵是三角矩阵时 |
|