10. 网络流问题和最小生成树

阅读信息

约 648 个字 2 分钟本页总访问量：加载中... 次

:compass:Class Ten

Network Flow Problems 网络流问题

城市改造涉及地下管网工程。从起点到终点有不同管道，不同管道的流量不同，用有向图表示。要求计算出最大流量。一种方法：

遍历图，找到一条从起点到终点的路径，这条路径的最大流量为管道权值的最小值。然后每条边减去取到的路径最大流量，剩余图重新遍历。直到没有从起点到终点的路径时，得到的流量和为最大流量。

有什么问题？选择路径时可能与其他路径冲突，导致其他路径上路径被删除。修改：建立反悔机制，某条线段流向可改变。具体操作：

在某条路径删除后，添加流量相同的反向边。相当于将来可以反悔，重新经过被删除的边。直到所有和起点相连的边都指向起点，终止。

时间复杂度：\(T=O(f\cdot \left| E\right|)\)，f 是最大流量改进：

下一步有不同选择时，优先选择流量大的边。
每次选择边最少。

进一步强化：最大流量可能有不同路径，各个路径通过时有代价。需要找到最大流量且最低代价的路径。

最小生成树(Mininum Spanning Tree)

给定一个图，找到权重最小的生成树。贪心算法(Greedy Method) 数学优化：给定函数和区间，求函数在区间上的最大值。随机选一个点，找出这个点的值 f(x0)。到左右 x0+d，x0-d，取三个值中最大值。每次找左右 d 的距离。当左右值都小于当前值时停止。这种方法取到局部最优解。得到全局最优解，每次移动时有一定概率跳到其他位置。

如何求最小生成树？

prim：以点为中心。

随机找一个点，找和它连接的最短的边加入。再找和这个局部的树和外部连接的最短的边（边的一个端点局部的树中，另一个端点在树外），加入。重复找最短边、加入，直到所有的点都在树内。
kruskal：以边为中心（选择 n-1 条边，使得它构成树且权值和最小）。

将所有边从小到大排列。从最短边开始，每次放一条边进去检查是否构成回路（这条边的两个端点是否连通），如果构成回路则跳过。当放入的边数到达 n-1 时停止。

DFS 深度优先搜索

C
void dfs(点 v) {
  vis[v] = true;
  for (与v相连的点w) {
    if (!vis[w]) {
      dfs(w);
    }
  }
}

如果整体不连通，在外面套 for 循环遍历图中所有点。

C
void dfsConn(图 g) {
  for (g中的点v) {
    if (!vis[v]) {
      dfs(v);
      // ????
    }
  }
}