Programming, Network, Office, Hardware, Software, Design, Photography.. I am just a GEEK
1. Thuật toán Prim
Cho G=(X,E) là một đồ thị liên thông có trọng gồm n đỉnh. Thuật toán Prim được dùng để tìm ra cây khung NN của G.
|
1 2 3 4 |
Bước 1: Chọn tùy ý v X và khởi tạo Y:= {v}; T := Ø. Trong đó X là tập các đỉnh của đồ thị, Y là tập các đỉnh được chọn vào cây khung ngắn 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 e nối đỉnh w với đỉnh v trong Y với w X\Y và v Y ta chọn cạnh có trọng lượng nhỏ nhất. Bước 3: Gán Y:= Y {w} và T:= T {e} Bước 4: Nếu T đủ n-1 phần tử thì dừng, ngược lại làm tiếp tục bước 2. |
Chú ý: trong các thuật toán tìm 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ạnh song song thì có thể bỏ đi và chỉ để lại một cạnh trọng lượng nhỏ nhất trong chúng.
|
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 |
#define MAX 100 typedef struct { int n; int L[MAX][MAX]; // ma trận trọng số }GRAPH; typedef struct { int v; //đỉnh thứ nhất int w; //đỉnh thứ hai }EDGE; EDGE T[MAX]; //cạnh của cây khung ngắn nhất int nT; //số cạnh của cây T int lblVertex[MAX]; //nhãn đánh dấu đỉnh nào đã xét (1) và đỉnh nào chưa xét (0). // Đóng vai trò như tập X và Y trong thuật toán nói trên. int nLbl; //số phần tử của mảng lblVertex … void PrimAlg(GRAPH g) { // gán số cạnh của cây khung nT ban đầu là 0 … // khởi tạo nhãn của các đỉnh là chưa xét (0) … // gán nhãn đã xét (1) cho đỉnh 0 … while (nT < …) // số cạnh tối đa của cây khung { EDGE edgeMin; int nMinWeight = -1; // -1 nghĩa là chưa có cạnh min // duyệt các đỉnh w thỏa điều kiện chưa xét for (w…) if (…) { // tìm một đỉnh v bất kỳ đã xét và có // cung nối (trực tiếp) giữa v & w for (v…) if (… && …) { // kiểm tra nếu chưa có cạnh min (nMinWeight < 0) // hoặc trọng của (v, w) nhỏ hơn nMinWeight // thì cập nhật lại edgeMin = (v, w) if (… || …) { edgeMin.v = v; edgeMin.w = w; nMinWeight = …; } } } // thêm cạnh edgeMin vào cây khung T[nT] = edgeMin; nT++; // gán nhãn đã xét cho đỉnh w … } } … |
Chú ý: ta cũng cần xác định đồ thị đưa vào có liên thông hay không trước khi gọi hàm PrimAlg đồng thời chú ý đồ thị có hướng (xét cả hai chiều và lấy cạnh có trọng nhỏ nhất!!!quan trọng!!!).
2. Thuật toán Kruskal
Cho G=(X,E) là một đồ thị liên thông có trọng gồm n đỉnh. Thuật toán Kruskal được dùng để tìm ra cây khung ngắn nhất của G.
|
1 2 3 |
Bước 1: Sắp xếp các cạnh theo thứ tự trọng lượng tăng dần và khởi tạo T := Ø. Bước 2: Lấy cạnh e ở đầu danh sách đã sắp xếp (có trọng nhỏ nhất) . Nếu T + {e} không chứa chu trình thì gán T:= T + {e}. Loại cạnh e khỏi danh sách. Bước 3: Nếu T đủ n-1 phần tử thì dừng, ngược lại làm tiếp tục bước 2. |
Chú ý: trong các thuật toán tìm 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ạnh song song thì có thể bỏ đi và chỉ để lại một cạnh trọng lượng nhỏ nhất trong chúng.
So sánh với Prim: Trong Prim, chúng ta thực hiện việc mở rộng tập đã xét (ban đầu chỉ gồm một đỉnh, 0 cạnh thành n đỉnh, n-1 cạnh) dựa trên các cạnh ngắn nhất nối giữa tập đã xét và tập chưa xét. Như vậy, có trường hợp một cạnh sẽ phải xét đi xét nhiều lần rồi mới được chọn, thậm chí không hề được chọn.
Đối với Kruskal, cũng thêm lần lượt các cạnh vào đồ thị, theo thứ tự từ trọng nhỏ nhất đến trọng lớn nhất (như vậy mỗi cạnh sẽ chỉ được duyệt một lần duy nhất). Ta chỉ bổ sung cạnh vào cây khung nếu việc thêm cạnh này không làm phát sinh ra chu trình.
|
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 |
#define MAX 100 typedef struct { int n; int L[MAX][MAX]; // ma trận trọng số }GRAPH; typedef struct { int v; //đỉnh thứ nhất int w; //đỉnh thứ hai }EDGE; EDGE T[MAX]; //cạnh của cây khung ngắn nhất int nT; //số cạnh của cây T EDGE lstEdge[MAX*(MAX-1)/2]; //danh sách các cạnh trong đồ thị int nEdgeCount; //số phần tử của mảng lstEdge char lblVertex[MAX]; //nhãn đánh dấu đỉnh đã xét hay chưa int nLbl; //số đỉnh của đồ thị /*Khởi tạo mảng cạnh của đồ thị*/ void InitListEdge(GRAPH g) { nEdgeCount = 0; // Duyệt các cạnh của đồ thị for (i..) for (j..) if (…) { lstEdge[nEdgeCount].x = …; lstEdge[nEdgeCount].y = …; nEdgeCount++; } } /*Sắp xếp cạnh theo thứ tự tăng dần về trọng số*/ void SortListEdge(GRAPH g) { for (i…) for (j…) if (g.L[lstEdge[i].v][lstEdge[i].w]>g.L[lstEdge[i].v][lstEdge[i].w]) … } /* Kiểm tra khi thêm một cạnh có chỉ số idx trong danh sách lstEdge có tạo thành chu trình không*/ bool IsCircle(int idx) { //gợi ý: kiểm tra nhãn của hai đỉnh ứng với chỉ mục idx có giống nhau hay không // nếu có, trả về true, tức cạnh này sẽ tạo thành chu trình // nếu không, tìm nhãn nhỏ nhất (lab1) và lớn nhất(lab2) trong hai đỉnh, // cập nhật toàn bộ các đỉnh có nhãn lab2 bằng giá trị lab1 return …; } … void KruskalAlg(GRAPH g) { // gán số cạnh của cây khung nT ban đầu là 0 nT = 0; nLbl = …; // khởi tạo nhãn của các đỉnh là bằng số thứ tự của chính nó … // khởi tạo mảng cạnh của đồ thị … int eMinIndex = 0; // chỉ mục của cạnh nhỏ nhất while (nT < …) // số cạnh tối đa của cây khung { // chọn cạnh e bé nhất chưa xét if (eMinIndex < nEdgeCount ) { //Kiểm tra xem cạnh này có tạo thành chu trình khi thêm vào không if (IsCircle(eMinIndex) == false) { // thêm cạnh có chỉ mục eMinIndex vào cây khung T[nT] =…; nT++; } eMinIndex++; } else { //Dừng thuật toán … } } … } … |
Chú ý: ta cũng cần xác định đồ thị đưa vào có liên thông hay không đồng thời chú ý đồ thị có hướng (xét cả hai chiều và lấy cạnh có trọng nhỏ nhất!!!quan trọng!!!) trước khi gọi hàm KruskalAlg.
Buy me a coffee
d
hello
thanks