22.1图的表示
邻接链表 adjacency-list
权重图 权重函数
邻接矩阵表示
directed gragh
Exercise
22.1-1
邻接链表 出度out-degree $d_-$：$O(|E|+|V|)$ 入度$d_+$：遍历 $O(|E|+|V|)$
22.1-2
7个节点的完全二叉树
$\begin{bmatrix} 0 & 1 & 1 & 0 & 0 & 0 & 0 \ 1 & 0 & 0 & 1 & 1 & 0 & 0 \ 1 & 0 & 0 & 0 & 0 & 1 & 1 \ 0 & 1 & 0 & 0 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 & 0 & 0 & 0 \0 &0 & 1 & 0 & 0 & 0 & 0 \ 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{bmatrix} $
22.1-3
$G \to G^T$
邻接矩阵 将矩阵转置即可 $O(|V|^2)$
邻接链表 创建新链表 $O(|E|+|V|)$
22.1-4
multigragh多图
22.2BFS
Prim的最小生成树算法 Dijkstra单源最短路径
广度优先树