最小生成树算法

Posted by Felix Zhang on 2020-06-21
Words 755 and Reading Time 3 Minutes
Viewed Times

图论

1. 并查集

1
2
查找（find）：确定元素属于哪个集合。不断向上查找，找到根节点，根据根节点判断是否属于同一集合；
合并（union）：将两个子集合并为一个集合。将一棵树作为另外一棵树的子树，从而变成更大的树；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void find(int x){
  while(x != father[x]){
    x = find(father[x]);
  }
  return father[x];
}
void Union(int x, int y){
  x = find(x);
  y = find(y);
  if(x != y){
    if(height[x] > height[y]){
       father[y] = x;
    }else if(height[x] < height[y]){
       father[x] = y;
    }else{
       father[x] = y;
       height[y]++;
    }
  }
  return;
}

2. 最小生成树：用最小的代价遍历全部的节点

Kruskal算法

1
2
3
4
5
6
7
Input：一个加权连通图(V,E)
Output: 利用集合得到的最小生成树（V_new, E_new）
1 对所有边按照权重排序
2 根据权重对边从小到大遍历：
3    如果边的两点不属于一个集合：
4       将u,v放入一个集合中，并将边放入边集合
5 最后使用Find函数判断是否只有一个最小生成树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct Edge{
  int from;
  int to;
  int weight;
  bool operator<(const edge& e)const {
    return weight < e.weight;
  }
};

int Kruskal(int n, int edgenum){
  Initial(n);
  sort(edge, edge+edgenum);//edge是一个边类型数组
  int sum = 0;
  for(int i = 0; i < edgenum; ++i){
    Edge cur = edge[i];
    //满足下述条件的边是属于最小生成树的
    if(find(cur.from) != find(cur.to)){
      union(cur.from, cur.to);
      sum += cur.weight;
    }
  }
  return sum;
}

Prim算法

1
2
3
4
5
6
Input：一个加权连通图(V,E)
Output: 利用集合得到的最小生成树
1 选定任意一个节点，填入V_new中，E_new为空集
2 REPEAT UNTIL V_new = V
3   在集合E中选择权重最小的边（u,v），其中u为V_new中的元素，v不在V_new中
4   将v加入V_new中，并且将上述边加入E_new中

3. 最短路径：某两个特定节点之间的最短路

Dijskstra算法（广搜+优先队列）

1
2
3
4
5
6
Input: 图G=(V,E)，源点s，终点v，集合S，V
Output: 权重和最小的路径
1 将源点s放入优先级队列qu中
2 Repeat:
3   取出优先级队列中的头部节点，做广度优先遍历，并对距离进行更新
4 返回目标终点的距离值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
struct edge{
  int to;
  int length;
  edge(int t, int l): to(t), length(l){}
};

struct point{
  int number;
  int distance;
  point(int n, int d): number(n), distance(d) {}
  bool operator<(const point& p) const{
    return distance > p.distance;//此处考虑到queue使用的是最大堆实现的
  }
};
//基于优先级队列的广搜：每次优先考虑离s最近的点
void dijskstra(int s){
  priority_queue<point> qu;
  dis[s] = 0;
  qu.push(point(s,dis[s]));
  while(!qu.empty){
    int cur = qu.top().number;
    qu.pop();
    for(int i = 0; i < graph[cur].size(); ++i){
      int v = graph[cur][i].to;
      int d = graph[cur][i].length;
      if(dis[v] > dis[u] + d){
        dis[v] = dis[u] + d;
        qu.push(point(u, dis[v]));
      }
    }
  }
  return;
}

4. 拓扑排序：有向图的排序

5. 关键路径

This is copyright.

FEATURED TAGS
FRIENDS