镖局运镖

镖局运镖"/>

镖局运镖

  假设有n个城市和m条道路，对应无向图中的点和边。每条路的过路费对应边的权值。镖局现在需要选择一些道路进行疏通，以便边距可以达到任意一个城镇，要求花费的银子越少越好。换句话说，镖局的要求就是用最少的边让图连通（任意两点之间可以互相到达），将多余的边去掉。

  很显然，要想让有n个顶点的图连通，那么至少需要n-1条边。如果一个连通无向图不包含回路，那么就是一棵树，其实这里就是求一个图的最小生成树。这里我们仅讨论无向图的最小生成树。

  既然要求让边的总权值最小，自然可以想到首先选择最短的边，然后选择次短的边……直到选择了n-1条边为止。这就需要先对所有的边按照权值大小进行从小到大的排序，然后从最小的开始选，依次选择每一条边，直到选择了n-1条边让整个图连通为止。中间添加每一条边时还需要判断这条边对应的两个顶点是否已经连通，如果已经连通则舍弃这条边，进行下一条边的判断。

  判断两个顶点是否已经连通，可以使用深度优先搜索或者广度优先搜索，但这样效率很低。更好的选择是使用并查集，将所有顶点放入一个并查集中，判断两个顶点是否连通，仅需要判断两个顶点是否在同一个集合（即是否有共同的祖先）即可，这样时间复杂度仅为O(logN)。

  这个算法名为Kruskal，总结如下：首先按照边的权值进行从小到大的排序，每次从剩余的边中选择权值较小且边的两个顶点不在同一个集合内的边（就是不会产生回路的边），加入到生成树中，直到加入了n-1条边为止，代码如下：

struct edge {int u;int v;int w;
}; //为了方便排序，用一个结构体来存储边的关系vector<struct edge> e;//用于保存各边信息
vector<int> f;//并查集需要用到//快速排序 形参left是需要快排的数组的最左边元素的序号，right是需要快排的数组最右边元素的序号
void quicksort(int left, int right) {int i = left, j = right;struct edge temp;if (left > right)return;while (i != j) {//顺序很重要，因为我们设的基点是最左边的那个元素，所以从右边开始找while (e[j].w >= e[left].w && i < j) {j--;}while (e[i].w <= e[left].w && i < j) {i++;}if (i != j) {temp = e[i];e[i] = e[j];e[j] = temp;}}//将基准数归位(此时i已经等于j)temp = e[left];e[left] = e[i];e[i] = temp;//继续处理左边的，这是一个递归的过程quicksort(left, i - 1);//继续处理右边的，这是一个递归的过程quicksort(i + 1, right);return;
}//并查集中寻找祖先的函数
int getf(int v) {if (f[v] == v)return v;else {//这里是路径压缩，每次在函数返回的时候，顺带把路上遇到的人的祖先改为最后找到的祖先编号f[v] = getf(f[v]);return f[v];}
}//并查集合并两个子集的函数
bool merge(int v, int u) {int t1, t2;//t1,t2分别为v和u的大boss，每次双方的会谈都必须是各自的最高领导人才行t1 = getf(v);t2 = getf(u);if (t1 != t2) {//如果v和u两个节点的祖先不同//采用"靠左原则“，左边变成右边的祖先。即把右边的集合，作为左边集合的子集合。f[t2] = t1;return true;}return false;//v和u的祖先相同，即已经连通了，返回false
}int main()
{int n, m; //n表示顶点个数，m表示边的条数int count=0, sum=0;//count 保存当前已选了多少条边； sum保存最终选用的所有边的总权重cin >> n >> m;e.resize(m);f.resize(n, 0);//读入边for (int i = 0; i < m; i++) {//u：起点 v：终点 w:权值cin >> e[i].u >> e[i].v >> e[i].w;}//按照边的权值大小对边进行从小到大的快速排序quicksort(0, m - 1);//并查集初始化for (int i = 0; i < n; i++) {f[i] = i;}//Kruskal算法核心部分for (int i = 0; i < m; i++) {//判断一条边的两个顶点是否已经连通，即判断是否已在同一个集合中if (merge(e[i].u, e[i].v)) {//目前尚未连通，选用这条边count++;sum += e[i].w;}if (count == n - 1) //对n个顶点的图只需要n-1条边就可以全连通了break;}cout << "sum=" << sum;system("pause");
}

结果：

现在来讨论Kruskal算法的时间复杂度。对边进行快速排序是O(MlogM)，再m条边中找出n-1条边是O(MlogN），所以总的时间复杂度为O(MlogM+MlogN)。通常M比N要大很多，因此最终时间复杂度为O(MlogM)。