Thuật toán Prim – Tìm cây khung có trọng số nhỏ nhất

Chia sẻ: abcdef_45

Thuật toán Prim Cho G = (X, E) là một đồ thị liên thông có trọng số gồm n đỉnh. Thuật toán Prim được dùng để tìm ra cây khung nhỏ nhất của G.

Bạn đang xem 7 trang mẫu tài liệu này, vui lòng download file gốc để xem toàn bộ.

Nội dung Text: Thuật toán Prim – Tìm cây khung có trọng số nhỏ nhất

Thuật toán Prim – Tìm cây khung có trọng số nhỏ nhất




Thuật toán Prim

Cho G = (X, E) là một đồ thị liên thông có trọng số gồm n đỉnh. Thuật toán Prim
được dùng để tìm ra cây khung nhỏ nhất của G.

Bước 1: Chọn tùy ý x0 thuộc X và khởi tạo V:= { x0 }; T := Ø. Trong đó

X là tập các đỉnh của đồ thị, V là tập các đỉnh được chọn vào cây khung
nhỏ nhất và T là tập các cạnh của cây này.
Bước 2: Trong số những cạnh nối đỉnh x với đỉnh y mà x ∈ V và y ∈

X\V ta chọn cạnh e có trọng số nhỏ nhất. Nếu không có cạnh e thỏa y êu
câu: DỪNG (1)
Bước 3: Thêm đỉnh y vào tập V và thêm cạnh e vào tập T.

Bước 4: Nếu T đủ n – 1 phần tử thì DỪNG (2), ngược lại làm tiếp tục

bước 2.

Ghi chú: Khi thuật toán dừng theo trường hợp 1 (tìm không có cạnh từ V đi ra)
thì đồ thị không liên thông nên không có cây khung và do đó c ũng không có
cây khung nhỏ nhất.

Cài đặt thuật toán Prim

Trong các thuật toán tìm cây khung ngắn nhất chúng ta có thể bỏ đi hướng các
cạnh và các khuyên; đối với các cạnh song song thì có thể bỏ đi và chỉ để lại một
cạnh trọng số nhỏ nhất trong chúng. Vì vậy dữ liệu nhập cho thuật toán thường là
ma trận trọng số L được quy ước như sau
Lij = Trọng lượng cạnh nhỏ nhất nối i đến j nếu có

Lij = 0 nếu không có cạnh nối i đến j


Ma trận có thể tổ chức bằng mảng 2 chiều (tĩnh hoặc động) trong bộ nhớ. Tập
V có thể tổ chức bằng một mảng 1 chiều (tĩnh hoặc động) l ưu các đỉnh hoặc là
một mảng dùng để dánh dấu (theo kiểu h àm đặc trưng: V[i] = 1 nếu i thuộc V
và V[i] = 0 nếu ngược lại).

Bài tập

Sử dụng thuật toán Prim để tìm cây khung nhỏ nhất trong đồ thị vô hướng có trọng
số.
Cấu trúc file dữ liệu đầu vào:

Dòng đầu tiên: số đỉnh đồ thị (N)

N dòng tiếp theo: ma trận kề của đồ thị với quy ước:

+ A[i][j] = W: trọng số của đường nối trực tiếp từ i đến j
+ A[i][j] = 0: không có đường nối trực tiếp từ i đến j
Các đỉnh được đánh chỉ số từ 0



Cấu trúc file dữ liệu đầu ra:

Nếu tìm được cây khung nhỏ nhất:

+ Dòng đầu chứa số nguyên k là trọng lượng cây khung cực tiểu
+ Dòng tiếp theo là các cạnh (u, v) thuộc cây khung này,
Nếu không tìm được ghi là “NULL” (KHÔNG dấu “”)

Lưu ý: cách xuất các cạnh theo qui ước (u,v) và các cạnh cách nhau bởi

dấu “;”

Ví dụ:
Mã nguồn hướng đối tượng bài tập thuật toán Prim – tải về (VC++ Project)

Tập tin PrimAlgo.h

//(C) http://kithuatlaptrinh.tk

#ifndef _PRIM_ALGO_H
#define _PRIM_ALGO_H

#include
#include
#include
using namespace std;

struct Edge
{
int v1, v2;
float w;
};

class PrimAlgo
{
int nVer;
int nT;
float wSum;
vector VSet;
vector T;
vector B; //weight matrix

public:
void LoadMatrix(istream& inDev);
bool LoadMatrix(char* fName);
void ShowTree(ostream& outDev);
bool ShowTree(char* fName);

bool FindEdge(Edge& e);
void PutToVSet(int v);
void PutToTree(Edge e);
void RunAlgo(int v_begin = 0);

PrimAlgo();
};

#endif



Tập tin PrimAlgo.cpp

//(C) http://kithuatlaptrinh.tk

#include "PrimAlgo.h"

PrimAlgo::PrimAlgo()
{
nVer = 0;
}

void PrimAlgo::LoadMatrix(istream &inDev)
{
inDev >> nVer;

VSet.resize(nVer);
B.resize(nVer);

int i, j;
for (i = 0; i < nVer; ++i)
{
B[i].resize(nVer);
for (j = 0; j < nVer; ++j)
inDev >> B[i][j];
}
}

bool PrimAlgo::LoadMatrix(char *fName)
{
ifstream inFile(fName);
if (inFile)
{
LoadMatrix(inFile);
return true;
}
return false;
}

void PrimAlgo::ShowTree(ostream &outDev)
{
if (nT == nVer - 1)
{
outDev
Đề thi vào lớp 10 môn Toán |  Đáp án đề thi tốt nghiệp |  Đề thi Đại học |  Đề thi thử đại học môn Hóa |  Mẫu đơn xin việc |  Bài tiểu luận mẫu |  Ôn thi cao học 2014 |  Nghiên cứu khoa học |  Lập kế hoạch kinh doanh |  Bảng cân đối kế toán |  Đề thi chứng chỉ Tin học |  Tư tưởng Hồ Chí Minh |  Đề thi chứng chỉ Tiếng anh
Theo dõi chúng tôi
Đồng bộ tài khoản