Bài 14-Thuật toán Prim

Thuật toán Prim do Robert Prim đưa ra vào năm 1957, ý tưởng chính của nó là lần lượt ghép vào cây khung các cạnh có trọng số tối thiểu liên thuộc với một đỉnh của cây mà không tạo ra chu trình trong cây. Thuật toán sẽ dừng khi có được n - 1 cạnh vào cây. Dưới đây là mô tả các bước của thuật toán Prim:

1. T = {cạnh có trọng số nhỏ nhất của G}

2. While số cạnh của T <  n - 1 do

     Nếu chọn được cạnh e thoả mãn đồng thời ba
         điều kiện sau:

       (a) e là cạnh có trọng số nhỏ nhất

       (b) e liên thuộc với một đỉnh trong T

       (c) khi thêm e vào cây khung T không tạo ra
              chu trình trong T

     thì thực hiện thêm cạnh e vào cây khung T;

     E* = E* È e;

Độ phức tạp của thuật toán là O(m + nlgn).

Dữ liệu vào:

/*vidu43.cpp*/

#include<stdio.h>

#include<conio.h>

typedef struct Canh

{

  int dau, cuoi;

  int trongso; // trọng số của cạnh

};

//trong ví dụ này mảng được đánh chỉ số bắt đầu là 1

Canh E[100], ESao[100];

// E lưu danh sách cạnh của đồ thị

// Esao lưu danh sách cạnh của cây khung T

int tongtrongso = 0;

// tổng trọng số của cây khung T

int k = 0; // k cho biết số cạnh của cây khung T

int TD[100]; // TD là tập đỉnh của cây khung T

int n, m;

void doctep(char tep[30]);

void hienthi();

int thuoc(int x);

// cho biết x co thuộc cây khung chưa?

int chonduoc(int j);

void primMST();

//tìm ra các cạnh và đưa vào Esao, tính tổng   //trọng   số của cây khung T

void sapxep();

void main()

{

  clrscr();

  doctep("dothi412.inp");

  hienthi();

  primMST ();

  printf("CAY KHUNG T = (V,E*)");

  printf("\nSo dinh la:%d, so canh la:%d",n,m);

  printf("\nTap canh E*:\n");

  for(int i = 1; i<= k; i++)

  printf("(%d, %3d, %3d)\n", 
           ESao[i].dau,ESao[i].cuoi,ESao[i].trongso);

  printf("\n---------------");

  printf("\nTong trong so la:%d",tongtrongso);

  getch();

}

int thuoc(int x)

{

  if(TD[x] = = 1)

     return 1;

  else

     return 0;

}

int chonduoc(int j)

{

  int kq = 0;

  if(((thuoc(E[j].dau)) &&(!thuoc(E[j].cuoi)))

   || ((thuoc(E[j].cuoi))&&(!thuoc(E[j].dau))))

  kq = 1;

  return kq;

}

void sapxep()

{

  int i, j; Canh x;

  for(i = 1;i<m; i++)

     for(j = i+1; j<= m; j++)

        if(E[i].trongso > E[j].trongso)

        {

           x = E[i]; E[i] = E[j]; E[j] = x;

        }

}

void primMST()

{

  sapxep();

  k++; // thêm cạnh đầu tiên vào cây khung T

  ESao[k] = E[1];

  tongtrongso+ = E[1].trongso;

  TD[ E[1].dau ] = 1;

  TD[ E[1].cuoi ] = 1; int j;

  while(k<n-1)

  {

     j = 2;

     while(j<= m)

     {

        if(chonduoc(j))

// liên thông vào TD, và không tạo chu trình

        {

         k++;

         ESao[k] = E[j];

          tongtrongso+ = E[j].trongso;

         // thêm đỉnh vào cây khung

         TD[ E[j].dau] = 1; TD[ E[j].cuoi] = 1;

         break;

        }

        j++;

     }

  }

}

void hienthi()

{

  printf("\nDO THI G = (V, E)");

  printf("\nSo dinh la:%d, so canh la:%d", n,m);

  for(int i = 1; i<= m; i++)

   printf("(%d, %3d, %3d)\n", E[i].dau, E[i].cuoi,
             E[i].trongso);

}

void doctep(char tep[30])

{

  int x,y,ts;

  FILE *fp;

  fp = fopen(tep,"rt");

  fscanf(fp,"%d%d\n", &x,&y);

  n = x; m = y;

  // đọc danh sách cạnh từ tệp lên mảng

  for(int i = 1; i<= m;i++)

  {

     fscanf(fp,"%2d%2d%2d",&x,&y,&ts);

     E[i].dau = x; E[i].cuoi = y;

     E[i].trongso = ts;

  }

  fclose(fp);

}

Tham khảo: Nguyễn Trường Xuân và các tác giả, Lý thuyết đồ thị và ứng dụng, nxb Giáo dục Việt Nan, 2017. 

Bình luận

Bài viết khác

Bài 16- Thuật toán Ford -Fulkerson

Thuật toán Ford - Fulkerson  Việc chứng minh định lý luồng cực đại - lát cắt cực tiểu cho ta một thuật toán tìm luồng cực đại (thuật toán Ford- Fulkerson)

Bài 15-Cài đặt thuật toán Dijkstra

Năm 1959, Edsger W. Dijkstra đưa ra một thuật toán rất hiệu quả để giải bài toán đường đi ngắn nhất. Thuật toán thực hiện việc gán và giảm giá trị của nhãn tại mỗi đỉnh của đồ thị.

Bài 14-Thuật toán Prim

Thuật toán Prim do Robert Prim đưa ra vào năm 1957, ý tưởng chính của nó là lần lượt ghép vào cây khung các cạnh có trọng số tối thiểu liên thuộc với một đỉnh của cây mà không tạo ra chu trình trong cây. Thuật toán sẽ dừng khi có được n - 1 cạnh vào cây. Dưới đây là mô tả các bước của thuật toán Prim.

Bài 13-Cài đặt thuật toán Kruskal tìm cây khung tối thiểu

File dữ liệu về đồ thị dạng text;

ĐỐI TÁC CỦA CHÚNG TÔI