ZEROCATH

身无长物江湖远,胸有沟壑天地宽

0%

数据结构——图

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

    MST

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

    Prim算法

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

图表示

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

图遍历

DFS

  • 生成树

    BFS

  • 生成森林