• 最小生成树算法之 Kruskal 和 Prim

    1、Kruskal算法

    1.1 流程

    1. 总是从 权值最小的边 开始考虑，，依次考察权值依次变大的边；
    2. 当前的边要么进入最小生成树的集合，要么丢弃；
    3. 如果当前的边进入最小生成树的集合中 不会形成环，就要当前边；
    4. 如果当前的边进入最小生成树的集合中 会形成环，就不要当前边；
    5. 考察完所有边之后，最小生成树的集合也得到了。

    1.2 说明

    无向图，保证所有点都连通的情况下，权重最小。

    使用到 并查集 ：

    • 一开始每个点都是独立的集合，然后选择权重最小的边，判断该边的两个点是否在同一个集合；
    • 如果在同一个集合则说明这条边会形成环，则不需要当前边；
    • 如果不在同一个集合中，则不会形成环，就要当前边，并将两个点所在的集合进行合并。

    1.3 实现

    C++ 版

    //Kruskal算法
class UnionFind {
private:
    //key：某个节点， value: key节点往上的点
    unordered_map<Vertex*, Vertex*> father;
    //key节点所在集合的节点数
    unordered_map<Vertex*, int> size;

public:
    UnionFind() {}

    void init(vector<Vertex*> &vs) {
        father.clear();
        size.clear();

        for (Vertex *v : vs) {
            father[v] = v;
            size[v] = 1;
        }
    }

    Vertex* find(Vertex *v) {
        return father[v] == v ? v : father[v] = find(father[v]);
    }

    void merge(Vertex *v1, Vertex *v2) {
        Vertex *f1 = find(v1), *f2 = find(v2);
        if (f1 != f2) {
            if (size[f1] >= size[f2]) {
                father[f2] = f1;
                size[f1] += size[f2];
                size.erase(f2);
            } else {
                father[f1] = f2;
                size[f2] += size[f1];
                size.erase(f1);
            }
        }
    }
};

struct EdgeComparator {
    bool operator()(Edge* const &e1, Edge* const &e2) const {
        return e1->weight > e2->weight;
    }
};

unordered_set<Edge*> kruskalMST(Graph *graph) {
    UnionFind *uf = new UnionFind();

    vector<Vertex*> vs;

    for (auto &kv : graph->vertexs) {
        vs.push_back(kv.second);
    }

    uf->init(vs);

    //建立边的小根堆
    priority_queue<Edge*, vector<Edge*>, EdgeComparator> que;

    for (auto &e : graph->edges) { //M条边
        que.push(e);//O(logM)
    }

    unordered_set<Edge*> result;
    while (!que.empty()) { //M条边
        Edge *edge = que.top(); //O(logM)
        que.pop();
        if (uf->find(edge->from) != uf->find(edge->to)) { //O(1)
            result.insert(edge);
            uf->merge(edge->from, edge->to);
            cout << "选择的边：[" << edge->weight << ", " << edge->from->value << ", " << edge->to->value << "]" << endl;
        }
    }

    return result;
}

int main() {
	GraphGenerator *gg = new GraphGenerator();
	cout << "Kruskal:" << endl;
    vector<vector<int> > infos1 {
        {1, 1, 2},
        {3, 1, 4},
        {5, 1, 3},
        {2, 4, 3},
        {3, 4, 2},
        {5, 2, 3},
    };

	//createGraph函数的实现见https://blog.csdn.net/u011386173/article/details/126275411?spm=1001.2014.3001.5501
    Graph *g1 = gg->createGraph(infos1); 
    unordered_set<Edge*> res = kruskalMST(g1);
    for (Edge *e : res) {
        cout << e->weight << endl;
    }
    return 0;
}

    • 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
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99

    Java 版

    import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.Stack;

//undirected graph only
public class Kruskal {

	// Union-Find Set
	public static class UnionFind {
		// key: 某一个节点， value: key节点往上的节点
		private HashMap<Node, Node> fatherMap;
		// key: 某一个集合的代表节点, value: key所在集合的节点个数
		private HashMap<Node, Integer> sizeMap;

		public UnionFind() {
			fatherMap = new HashMap<Node, Node>();
			sizeMap = new HashMap<Node, Integer>();
		}
		
		public void makeSets(Collection<Node> nodes) {
			fatherMap.clear();
			sizeMap.clear();
			for (Node node : nodes) {
				fatherMap.put(node, node);
				sizeMap.put(node, 1);
			}
		}

		private Node findFather(Node n) {
			Stack<Node> path = new Stack<>();
			while(n != fatherMap.get(n)) {
				path.add(n);
				n = fatherMap.get(n);
			}
			while(!path.isEmpty()) {
				fatherMap.put(path.pop(), n);
			}
			return n;
		}

		public boolean isSameSet(Node a, Node b) {
			return findFather(a) == findFather(b);
		}

		public void union(Node a, Node b) {
			if (a == null || b == null) {
				return;
			}
			Node aDai = findFather(a);
			Node bDai = findFather(b);
			if (aDai != bDai) {
				int aSetSize = sizeMap.get(aDai);
				int bSetSize = sizeMap.get(bDai);
				if (aSetSize <= bSetSize) {
					fatherMap.put(aDai, bDai);
					sizeMap.put(bDai, aSetSize + bSetSize);
					sizeMap.remove(aDai);
				} else {
					fatherMap.put(bDai, aDai);
					sizeMap.put(aDai, aSetSize + bSetSize);
					sizeMap.remove(bDai);
				}
			}
		}
	}
	

	public static class EdgeComparator implements Comparator<Edge> {

		@Override
		public int compare(Edge o1, Edge o2) {
			return o1.weight - o2.weight;
		}

	}

	public static Set<Edge> kruskalMST(Graph graph) {
		UnionFind unionFind = new UnionFind();
		unionFind.makeSets(graph.nodes.values());
		// 从小的边到大的边，依次弹出，小根堆！
		PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
		for (Edge edge : graph.edges) { // M 条边
			priorityQueue.add(edge);  // O(logM)
		}
		Set<Edge> result = new HashSet<>();
		while (!priorityQueue.isEmpty()) { // M 条边
			Edge edge = priorityQueue.poll(); // O(logM)
			if (!unionFind.isSameSet(edge.from, edge.to)) { // O(1)
				result.add(edge);
				unionFind.union(edge.from, edge.to);
			}
		}
		return result;
	}
}

    • 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
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99

    2、Prim 算法

    2.1 流程

    1. 可以从任意节点出发来寻找最小生成树

    2. 某个点加入到被选取的点中后，解锁这个点出发的所有新的边

    3. 在所有解锁的边中选最小的边，然后看看这个边会不会形成环

    4. 如果会，不要当前边，继续考察剩下解锁的边中最小的边，重复3）

    5. 如果不会，要当前边，将该边的指向点加入到被选取的点中，重复2）

    6. 当所有点都被选取，最小生成树就得到了

    2.2 实现

    C++ 版

    struct EdgeComparator {
    bool operator()(Edge* const &e1, Edge* const &e2) const {
        return e1->weight > e2->weight;
    }
};

//Prim 算法
unordered_set<Edge*> primMST(Graph *graph) {
    //解锁的边进入小根堆
    priority_queue<Edge*, vector<Edge*>, EdgeComparator> que;
    //解锁的点
    unordered_set<Vertex*> vertexSet;
    //存放选择的边
    unordered_set<Edge*> result;

    for (auto &kv : graph->vertexs) { //随便选择一个点
        Vertex *v = kv.second; //v为开始点

        if (!vertexSet.count(v)) {
            vertexSet.insert(v);

            for (Edge *edge : v->adjE) { //由一个点解锁相连的边，注意此处的v是fromV，所以如果是无向图同一条边需要输入两次
                que.push(edge);
            }

            while (!que.empty()) {
                Edge *edge = que.top(); //获取解锁的边中权重最小的边
                que.pop();
                Vertex *toV = edge->to; //可能的新点
                if (!vertexSet.count(toV)) { //集合中不包含时就是新的点
                    vertexSet.insert(toV);
                    cout << "选择的边：[" << edge->weight << ", " << edge->from->value << ", " << edge->to->value << "]" << endl;
                    result.insert(edge);
                    for (Edge *nextEdge : toV->adjE) {
                        que.push(nextEdge);
                    }
                }
            }
        }
        //break; //如果就是一张图，那就需要break（只需要一个起始点）； 如果是森林，那就不用break（多个起始点）
    }

    return result;
}

// 请保证graph是连通图
// graph[i][j]表示点i到点j的距离，如果是系统最大值代表无路
// 返回值是最小连通图的路径之和
int prim(vector<vector<int>> &graph) {
    int size = graph.size();
    vector<int> distances(size);
    vector<bool> visit(size);
    visit[0] = true;

    for (int i = 0; i < size; i++) {
        distances[i] = graph[0][i];
    }


    int sum = 0;
    for (int i = 1; i < size; i++) {
        int minPath = INT_MAX;
        int minIndex = -1;
        for (int j = 0; j < size; j++) {
            if (!visit[j] && distances[j] < minPath) {
                minPath = distances[j];
                minIndex = j;
            }
        }

        if (minIndex == -1) {
            return sum;
        }

        visit[minIndex] = true;
        sum += minPath;

        for (int j = 0; j < size; j++) {
            if (!visit[j] && distances[j] > graph[minIndex][j]) {
                distances[j] = graph[minIndex][j];
            }
        }
    }

    return sum;
}

    • 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
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86

    Java 版

    import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

// undirected graph only
public class Prim {

	public static class EdgeComparator implements Comparator<Edge> {

		@Override
		public int compare(Edge o1, Edge o2) {
			return o1.weight - o2.weight;
		}

	}

	public static Set<Edge> primMST(Graph graph) {
		// 解锁的边进入小根堆
		PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());

		// 哪些点被解锁出来了
		HashSet<Node> nodeSet = new HashSet<>();
		
		
		
		Set<Edge> result = new HashSet<>(); // 依次挑选的的边在result里

		for (Node node : graph.nodes.values()) { // 随便挑了一个点
			// node 是开始点
			if (!nodeSet.contains(node)) {
				nodeSet.add(node);
				for (Edge edge : node.edges) { // 由一个点，解锁所有相连的边
					priorityQueue.add(edge);
				}
				while (!priorityQueue.isEmpty()) {
					Edge edge = priorityQueue.poll(); // 弹出解锁的边中，最小的边
					Node toNode = edge.to; // 可能的一个新的点
					if (!nodeSet.contains(toNode)) { // 不含有的时候，就是新的点
						nodeSet.add(toNode);
						result.add(edge);
						for (Edge nextEdge : toNode.edges) {
							priorityQueue.add(nextEdge);
						}
					}
				}
			}
			// break; //如果就是一张图，那就需要break；如果是森林，就不用break
		}
		return result;
	}

	// 请保证graph是连通图
	// graph[i][j]表示点i到点j的距离，如果是系统最大值代表无路
	// 返回值是最小连通图的路径之和
	public static int prim(int[][] graph) {
		int size = graph.length;
		int[] distances = new int[size];
		boolean[] visit = new boolean[size];
		visit[0] = true;
		for (int i = 0; i < size; i++) {
			distances[i] = graph[0][i];
		}
		int sum = 0;
		for (int i = 1; i < size; i++) {
			int minPath = Integer.MAX_VALUE;
			int minIndex = -1;
			for (int j = 0; j < size; j++) {
				if (!visit[j] && distances[j] < minPath) {
					minPath = distances[j];
					minIndex = j;
				}
			}
			if (minIndex == -1) {
				return sum;
			}
			visit[minIndex] = true;
			sum += minPath;
			for (int j = 0; j < size; j++) {
				if (!visit[j] && distances[j] > graph[minIndex][j]) {
					distances[j] = graph[minIndex][j];
				}
			}
		}
		return sum;
	}

	public static void main(String[] args) {
		System.out.println("hello world!");
	}
}

    • 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
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
  • 相关阅读:
    4519. 正方形数组的数目
    比postman更好用的接口管理软件——Apifox
    程序员面对生活
    Redis分布式锁
    with语句和上下文管理器
    Cholesterol-PEG-NHS NHS-PEG-CLS 胆固醇-聚乙二醇-活性酯可修饰小分子材料
    Java语法详解
    ZooKeeper数据模型/znode节点深入
    什么牌子的蓝牙耳机好？音质好的蓝牙耳机推荐
    QueryWrapper方法解释
  • 原文地址：https://blog.csdn.net/u011386173/article/details/126389465