概念#

• 有向图 无向图
• 带权图
• 简单图 多重图
• 子图
• 完全图
• 连通图 连通分量 强连通分量 弱连通分量 极大连通子图
• 生成树 生成森林 极小连通子图
• 树
• 度
  • 对无向图 度之和为边数乘2
  • 对无向图 入度等于初度等于边数，总度等于入度与出度之和
• 路径 两个顶点之间的顶点序列
  • 回路 简单回路
  • 路径长度：路径上边的数量
  • 距离 最短路径
• 对于简单无向图
  • 当$|E| < |V| - 1$ 一定是非连通的
  • 当$|E| > (|V| - 1)(|V| - 2)/2$ 一定是连通的 有一个节点是一个孤岛，其余节点构成完全图，有一个桥连接两个岛屿
  • 当$|E|$ 介于两者之间可能是…也可能是…
• 对于简单有向图
  • 当$|E| < |V|$ 一定是非强连通的
  • 当$|E| > (|V| - 1)(|V| - 2)$ 一定是强连通的 有一个节点是一个孤岛，其余节点构成完全图，有一个桥连接两个岛屿
  • 当$|E|$ 介于两者之间可能是…也可能是…
• 当简单 有向图/无向图 边数/顶点数固定 （强）连通/非（强）连通 顶点数/边数 至多/至少为，一共16种情况思考每种情况的答案是多少

物理存储结构#

遍历#

BFS#

• 时间复杂度 遍历所有节点的所有边所以对于邻接矩阵而言复杂度是$O(n^2)$,对于邻接表是$O(n+e)$

DFS#

• 同上

BFS/DFS 生成树/森林#

（带权图）最小生成树#

BFS/DFS#

仅适用于非带权图

prim#

• 每次将代价最小的顶点接入树
• 适合边稠密的情况
• $O(n^2)$

kruskal#

• 每次选择权值最小的边，连接两个连通分量
• 适合边稀疏的图
• 采用堆存放边的集合选出最小的边
• 复杂度
  • 每次选择边$O(loge)$
  • 最坏需要$e$轮,复杂度$O(eloge)$

最短路径#

bfs#

仅适用于无权图

dijk#

• final[] 标记对应节点是否已经找到最短路径
• dist[]计算出的最短路径长度
• path[]计算出的最短路径的前驱
• 不适合求有负权值的图
• 类比#prim
• 时间复杂度$O(n^2)$

floyd#

• 不能有负的回路
• 复杂度$O(n^3)$

DAG#

描述表达式#

拓扑排序#

使用dfs实现#

dfs(node) {
	for neigh in node.neighbours.filter(_ => !_.has_visited) {
		dfs(neigh)
	}
	print(node)
} 

输出序列是一个逆拓扑排序，对其反转后得到拓扑排序

经典实现#

• 从AOV网中找一个入度为0的顶点并输出
• 从AOV网中删除这个顶点和所有以它为起点的边
• 重复直到AOV网为空或者不存在入度为0的点为止
• 遍历所有节点的所有边所以对于邻接矩阵而言复杂度是$O(n^2)$,对于邻接表是$O(n+e)$

//假定采用邻接矩阵实现
topological_sort(g) => Maybe<int[]> {
	s := []
	indegree = g.vexs.map(_ => _.indegree)
	res := []
	for (i, _) in indegree.enum().filter((_, indegree) => indegree === 0) {
		s.push(i)
	}
	while Some(i) = s.pop() {
		res.push(i)
		for neigh in g.vex[i] {
			indegree[neigh]--
			if indegree[neigh] === 0 { s.push(neigh) }
		}
	}
	if res.len === g.vex_num {
		return Just(res)
	} else {
		return Nothing
	}
}

关键路径#

• AOE网，边是活动，顶点是里程碑
• 事件的最早开始时间 事件的最晚开始时间
• 活动的最早开始时间 弧的起点的事件的最早开始时间
• 活动最晚开始时间 弧的终点的事件的最晚开始时间减去活动的长度
• 活动的余量 活动最晚开始时间与最早开始时间之差
• 遍历所有节点的所有边所以对于邻接矩阵而言复杂度是$O(n^2)$,对于邻接表是$O(n+e)$

其他#

• 上三角的邻接矩阵必定是有向无环图
• 有向无环图不一定是上三角阵

• 拓扑序列唯一得不到唯一的有向无环图 如123对应下面两种可能

检测环路#

• #DFS
• #拓扑排序