数据结构——图

• 极大强连通子图：强连通子图
• 极小强连通子图：生成树

  MST

• MST性质：设G=（V，E）是一个连通图，通过某种算法构造其最小生成树，T=（U，TE）是正在构造的最小生成树。如果边（u,v)是G中所有一端在U中（即u∈U）而另一端在V-U中（即v∈V-U）具有最小值的一条边，则必存在一棵包含边（u,v)的最小生成树。

  Prim算法

  从一个顶点出发，依次将权值小的边加入正在构造的最小生成树

图表示

• 顶点数组与邻接矩阵
• 邻接表

图遍历

DFS

• 生成树

  BFS

• 生成森林