Thuật toán Prim - Tìm Cây Khung Nhỏ Nhất

THUẬT TOÁN PRIM

Có bao giờ bao giờ bạn hỏi vì sao giữa các địa điểm trong một thành phố lại có nhiều đường đi đến như vậy. Vậy có cách nào vừa đảm bảo có đường đi giữa mọi điểm trong thành phố mà chi phí làm đường lại nhỏ nhất không. Tất nhiên là có rồi và thuật toán Prim sẽ giúp bạn giải quyế việc đấy một cách dễ dàng.

Thuật toán Prim - Tìm Cây Khung Nhỏ Nhất

THUẬT TOÁN

MÔ TẢ THUẬT TOÁN:

• Bước khởi tạo: Chọn một đỉnh làm gốc sau đó xét đường nối đỉnh gốc đến các đỉnh còn lại, nếu không có thì cho khoảng cách vô cùng.
• Bước 1.1: Chọn đỉnh có đường nối ngắn nhất đã tìm ở bước trước, đánh dấu là đã xét.
• Bước 1.2: Xét tiếp đường nối từ đỉnh trên đến các đỉnh còn lại chưa xét tới. Nếu phát hiện đỉnh có đường nối ngắn hơn bước trên thì cập nhật lại đường nối tại đỉnh đó.
• Lặp lại 2 bước trên đến khi đánh dấu hết các đỉnh.

ĐỒ THỊ MẪU:

MINH HỌA CÁCH GIẢI BẰNG TAY:

CODE:

	#include<iostream>
	#include<map>
	#include<stack>
	#include<vector>
	using namespace std;
	int total_weight = 0;
	vector< pair<int, int> > prim(const vector< vector< pair<int, int> > > &adj) {
	stack<int> S; // push đỉnh được chọn sau mỗi bước
	vector< pair<int, int> > V(adj.size(), {INT_MAX, 1}); // V[i].second và i là cặp đỉnh được chọn, V[i].first là trọng số
	vector<bool> mark(adj.size(), 0); // Đánh dấu đỉnh đã được chọn
	S.push(1);
	V[1] = {0, 1};
	while (!S.empty()) {
	int u = S.top();
	mark[u] = 1;
	S.pop();
	// Xét các đỉnh lân cận chưa được chọn, đỉnh nào có trọng số mới nhỏ hơn thì cập nhật vào V
	for (auto e : adj[u]) {
	int v = e.first;
	int c = e.second;
	if (V[v].first > c && !mark[v]) {
	V[v] = {c, u};
	}
	}
	// Tìm đỉnh có trọng số nhỏ nhất để thực hiện bước tiếp theo
	int w_min = INT_MAX;
	int p;
	for (int i = 1; i < adj.size(); i++) {
	if (!mark[i]) {
	if (V[i].first < w_min) {
	w_min = V[i].first;
	p = i;
	}
	}
	}
	// Nếu còn đỉnh chưa được chọn thì push vào S vào cộng tổng trọng số
	if (w_min != INT_MAX) {
	total_weight += w_min;
	S.push(p);
	}
	}
	return V;
	}
	int main() {
	int n = 6;
	vector< vector< pair<int, int> > > adj(n + 1);
	// add khoảng cách từ u dến v
	auto add_edge = [&adj] (int u, int v, int w) {
	adj[u].push_back({v, w});
	adj[v].push_back({u, w});
	};
	add_edge(1, 3, 7);
	add_edge(1, 6, 3);
	add_edge(2, 4, 9);
	add_edge(2, 5, 6);
	add_edge(2, 6, 4);
	add_edge(3, 4, 8);
	add_edge(3, 6, 5);
	add_edge(4, 5, 2);
	add_edge(4, 6, 1);
	vector< pair<int , int> > min = prim(adj);
	cout << "Minimum Spanning Tree: ";
	for (unsigned int i = 2; i< min.size(); i++) {
	cout << "(" << min[i].second << ", " << i << ") ";
	}
	cout << endl << "Total Weight: " << total_weight;
	}

view raw prim.cpp hosted with ❤ by GitHub

KẾT QUẢ:

Minimum Spanning Tree: (6, 2) (6, 3) (6, 4) (4, 5) (1, 6)
Total Weight: 15

CÂY KHUNG NHỎ NHẤT:

LỜI KẾT

Trên đây là những kiến thức mà mình được dạy cũng như là tìm hiểu về thuật toán Prim, nếu còn gì sai sót các bạn hãy comment ở bên dưới cho mình biết nhé. Chúc các bạn một tuần làm việc và học tập hiệu quả!

Đánh Giá Bài Viết: