图论 最小生成树相关概念

• 连通图:在无向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该无向图为连通图。
• 强连通图:在有向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该有向图为强连通图。
• 连通网:在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
• 生成树: 一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
• 最小生成树:在连通网里面,代价最小的生成树便是最小生成树

最小生成树(Prim&Kruskal)

• 实例:如电路网怎么建设成本最低
• Prim(普里姆)算法

• • Prim算法可以称为加点法,每次选择代价最小的边的点,从任一顶点开始,直至覆盖所有点
  • 算法思想:贪心
  • 算法流程:

• • • 令图的所有顶点集合位V;初始令集合u={s},v=V−u
    • 寻找集合u,v中可以组成最小权重边(u0,v0)并且加入到集合u中
    • 重复上述步骤,直到生成n-1条边或者n个顶点为止
    • 普里姆算法如图:

• Kruskal(克鲁斯卡尔)算法

• • Kruskal算法可以成为加边法,初始的生成边数为0,每次迭代选择最小代价的边,加入到最小生成树的边集合里面
  • 算法思想:贪心
  • Kruskal算法流程:

• • • 将图的所有边按照代价从小到大进行排序
    • 将图中的n个顶点看成n个树构成的森林
    • 按照权值从小到大选择边,所选的边的两个顶点应该属于独立的树,则将它们连接成一棵树
    • 重复第三步,直到全部顶点都属于一棵树,或者有n-1条边为止

• • 克鲁斯卡尔算法流程:

• Prim算法对于点操作,适用于稠密图;Kruskal算法对边进行操作,适用于稀疏图

最短路径

• 路径长度:指路径所经历的边的数目
• 带权路径长度:指路径所经过的边的权值之和
• 最短路径:指带权路径值最小的路径

最短路径(Dijkstra&Floyd)

• Dijkstra(迪杰斯特拉算法):

• • 用于求某点到其余各点的最短路径(只能计算权值大于0的边)
  • 算法思想:

• • • 贪心思想
    • 设存在顶点集合U、T;U中包含了已经确定的最小权值路径的点,T中包含未确定的最小权值路径的点
    • 初始状态时:U中只包含了U0源点
    • 接下来从T中选择距离U0权值最小的点,加入U中
    • 集合U中每新增一个节点,都需要刷新U0到T中剩余元素的最小权值;新增加的U节点权值为原先权值与新增加U之后的节点的最小值
    • 重复3、4步骤,直到T中的所有节点在U中

• • 算法流程图:

• Floyd(弗洛伊德算法):

• • 用于计算每一对顶点之间的最短距离
  • 算法思想:

• • • 弗洛伊德算法的核心是DP,dp[i][j]=Math.min(dp[i][j],dp[i][k]+dp[k][j]);
    • 弗洛伊德算法模板:

//k为中转节点  for(int k = 1; k <= n; k++)  //i为开始节点  for(int i = 1; i <= n; i++)  //j为结束节点  for(int j = 1; j <= n; j++)  //以k中间节点,求i至j的最低代价  if(a[i][j] > a[i][k]+a[k][j])  a[i][j] = a[i][k]+a[k][j];

• Floyd算法流程: