Từ 1 tới 10 trên tổng số 10 kết quả

Đề tài: Giải thuật Kruskal. Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật kruskal??

  1. #1
    Ngày gia nhập
    03 2009
    Bài viết
    3

    Mặc định Giải thuật Kruskal. Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật kruskal??

    Anh chị nào làm ơn giúp em với!!!!!
    Hướng dẫn cho em cách để viết chương trình bài toán tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật kruskal viết trên ngôn ngữ lập trình c thì phải làm sao.xin cho em 1 vd cu thể giúp e với
    Em xin thanks!

  2. #2
    Ngày gia nhập
    03 2009
    Bài viết
    1

    hiiiiiiiii bài toán" tìm cây khung có trong lượng nhỏ nhất "là gì vậy?
    trông giống như là bài toán tìm số nhỏ nhất vậy nhỉ

  3. #3
    Ngày gia nhập
    03 2009
    Bài viết
    3

    dạ đúng rùi đó. Ai có lòng hảo tâm giup dùm em di!!!!

  4. #4
    Ngày gia nhập
    05 2009
    Bài viết
    2

    Arrow Code hoàn chỉnh bài toán cây khung nhỏ nhất với thuật toán Kruscal này bạn ơi

    Đoạn Code này với dữ liệu vào từ bàn phím đó.

    #include <conio.h>
    #incude <stdio.h>
    int n, m, Index[100], Distance[100], Dau[100], Cuoi[100], K_Dau[100], K_Cuoi[100];


    /*------------------------------------------------------------------------*/
    int Input();
    int MakeHeap(int *A, int i, int n);
    int Kruscal();
    /*------------------------------------------------------------------------*/
    int Input()
    {
    int i, temp;

    printf("\n Nhap so dinh: "); scanf("%d",&n);

    for(i=1;i<=n;i++)
    Index[i]=0;
    printf("\n Nhap so canh: "); scanf("%d",&m);

    printf("\n Nhap danh sach canh:\n");
    for(i=1;i<=m;i++)
    {
    printf("\n canh %d bat dau tai dinh: ",i); scanf("%d",&temp);
    Dau[i]=temp;
    printf("\n Ket thuc tai dinh: "); scanf("%d",&temp);
    Cuoi[i]=temp;
    printf("\n Do dai canh %d-%d: ",Dau[i],Cuoi[i]); scanf("%d",&temp);
    Distance[i]=temp;
    }

    printf("\n Danh sach cac canh");
    for(i=1;i<=m;i++)
    {
    printf("\n %d-%d:%3d",Dau[i], Cuoi[i],Distance[i]);
    }
    return 1;
    }
    /*------------------------------------------------------------------------*/
    int MakeHeap(int *A, int i, int m)
    {
    int temp, j=2*i;
    int key=A[i];

    while(j<=m)
    {
    if((j<m)&&(A[j]>A[j+1]))
    j=j+1;
    if(key<=A[j])
    return 1;
    else
    {
    A[j/2]=A[j];
    A[j]=key;

    temp=Dau[j];
    Dau[j]=Dau[j/2];
    Dau[j/2]=temp;

    temp=Cuoi[j];
    Cuoi[j]=Cuoi[j/2];
    Cuoi[j/2]=temp;

    j=j*2;
    }
    }

    return 1;
    }
    /*------------------------------------------------------------------------*/
    int Kruscal()
    {
    int t, i, j, count, temp1, temp2;

    t=1;
    i=m-1;
    count=1;
    for(j=m/2;j>=1;j--)
    MakeHeap(Distance,j,m);

    while(t<=n-1)
    {
    if((Index[Dau[1]]!=Index[Cuoi[1]]))
    // Kiem tra xem canh bo sung co tao thanh chu trinh khong qua chi so Index cua dinh
    {
    K_Dau[t]=Dau[1];
    K_Cuoi[t]=Cuoi[1];
    t++;

    if(Index[Dau[1]]>Index[Cuoi[1]])
    {
    temp1=Index[Dau[1]];
    temp2=Index[Cuoi[1]];
    // danh dau cac dinh trong cung mot cay cung mot chi so.
    for(j=1;j<t;j++)
    {
    if(Index[K_Dau[j]]==temp2)
    Index[K_Dau[j]]=temp1;

    if(Index[K_Cuoi[j]]==temp2)
    Index[K_Cuoi[j]]=temp1;
    }
    }
    if(Index[Dau[1]]<=Index[Cuoi[1]])
    {
    temp1=Index[Cuoi[1]];
    temp2=Index[Dau[1]];
    // danh dau cac dinh trong cung mot cay cung mot chi so.
    for(j=1;j<t;j++)
    {
    if(Index[K_Dau[j]]==temp2)
    Index[K_Dau[j]]=temp1;

    if(Index[K_Cuoi[j]]==temp2)
    Index[K_Cuoi[j]]=temp1;
    }
    }
    }
    if((Index[Dau[1]]==0)&&(Index[Cuoi[1]]==0)) // Truong hop hai dinh tu do chua tham gia vao cay nao
    {
    K_Dau[t]=Dau[1];
    K_Cuoi[t]=Cuoi[1];
    t++;
    // Danh chi so cay khung .
    Index[Dau[1]]=count;
    Index[Cuoi[1]]=count;
    count++;
    }
    // Tao lai dong .

    temp1=Distance[1];
    Distance[1]=Distance[i+1];
    Distance[i+1]=temp1;

    temp1=Dau[1];
    Dau[1]=Dau[i+1];
    Dau[i+1]=temp1;

    temp1=Cuoi[1];
    Cuoi[1]=Cuoi[i+1];
    Cuoi[i+1]=temp1;

    MakeHeap(Distance,1,i);
    i--;
    }
    // Hien thi cay khung nho nhat.

    printf("\n Cac canh cua cay khung nho nhat");
    for(j=1;j<t;j++)
    printf("\n %d-%d",K_Dau[j],K_Cuoi[j]);
    return 1;
    }
    /*------------------------------------------------------------------------*/

    int main(int argc, char* argv[])
    {
    Input();
    Kruscal();

    getch();
    return 0;
    }
    Đã được chỉnh sửa lần cuối bởi kid1412_chv : 17-05-2009 lúc 04:26 AM. Lý do: chưa cho Code vào khung

  5. #5
    Ngày gia nhập
    10 2009
    Nơi ở
    Milky Way professional final
    Bài viết
    357

    Cảm ơn nhiều nhe!

  6. #6
    Ngày gia nhập
    04 2009
    Bài viết
    2

    Mặc định Giải thuật Kruskal. Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật kruskal??

    thanks nhieu .ban giai thichchut duoc khong

  7. #7
    Ngày gia nhập
    11 2011
    Bài viết
    4

    Mặc định Hay wa..

    Em đang cần cái này.
    Chương trình này chạy rất ok.
    Nếu cải tiến sang nhập bằng tay thì ok hơn đó anh.

  8. #8
    Ngày gia nhập
    08 2012
    Bài viết
    1

    minh khong chay dc chuong trinh nay..huhu...
    không hiểu nữa..ai gửi cho mình bài này viết bằng dev c++ dc không?

  9. #9
    Ngày gia nhập
    01 2013
    Nơi ở
    Học viện Kỹ thuật Quân Sự
    Bài viết
    247

    Code đây.
    Mình làm trên file.
    Đồ thị vào từ file. (*.INP)
    Cây khung tối thiểu cũng xuất số liệu ra file. (*.OUT)

    Bạn cứ mở các file này bằng notepad là xem được.

    File đính kèm bên dưới nhé.
    Attached Files Attached Files
    Nếu cần giúp đỡ, hỗ trợ:
    Bài Tập. Đồ Án. Tools. Phần mềm. Liên hệ:
    Facebook: http://www.facebook.com/thuecodedoan
    Website: https://thuecodedoan.wordpress.com
    Email: thuecodedoan@gmail.com
    Sđt: 094.76.76.854

  10. #10
    Ngày gia nhập
    01 2013
    Nơi ở
    Học viện Kỹ thuật Quân Sự
    Bài viết
    247

    Đây là code vào dữ liệu từ bàn phím.
    Code:
    /*
      Programme:Cay Khung Nho Nhat
      Copyright: DTH46 - MILITARY TECHNICAL ACADEMY
      Author: Nguyen Sy Bach
      Date/Time: 24/02/13 17:53
      */
    
    #include<stdio.h>
    int dd[101], dc[101], P[101], tplt[101], Trace[101];
    int n, m, SumP = 0;
    void Input(){
         printf ("\nNhap so dinh: ");
         scanf ("%d",&n);
         printf ("\nNhap so canh: ");
         scanf ("%d",&m);
         printf ("\nNhap do thi theo thu tu: (dinh dau) (dinh cuoi) (trong so) roi Enter\n");
         for (int i = 1; i <= m; ++i)
             scanf ("%d %d %d",&dd[i],&dc[i],&P[i]);
    }
    void HopLai(int i, int k){
         int tg;
         tg = tplt[i];
         for (int j = 1; j <= n; ++j)
             if (tplt[j] == tg)
                tplt[j] = tplt[k];
    }
    void QuickSort(int *P, int left, int right){
         if (left >= right)
            return;
         int i = left, k = right;
         int key = P[(i+k)/2];
         while (i <= k){
               while (P[i] < key)
                     ++i;
               while (key < P[k])
                     --k;
               if (i <= k){
                  if (i < k){
                     P[i] += P[k]; // day chi la doi cho P[i] va P[k] thoi ma
                     P[k] = P[i]-P[k];
                     P[i] -= P[k];
                     // ==============
                     dd[i] += dd[k];   // day cung vay. Chi la doi cho
                     dd[k] = dd[i]-dd[k];
                     dd[i] -= dd[k];
                     //==================
                     dc[i] += dc[k];  // day cung the
                     dc[k] = dc[i] - dc[k];
                     dc[i] -= dc[k];
                  }
                  ++i;
                  --k;
               }
         }
         QuickSort(P,left,k);
         QuickSort(P,i,right);
    }
    void Process(){
         int k = 0, index = 1;
         for (int i = 1; i <= n; ++i)
             tplt[i] = i;
         QuickSort(P,1,m);
         while (k < n){
               if (tplt[dd[index]] != tplt[dc[index]]){
                  HopLai(dd[index],dc[index]);
                  ++k;
                  SumP += P[index];
                  Trace[k] = index;
               }
               ++index;
         }
    }
    void Output(){
    	printf ("\nTong trong so cua cay khung: "); 
        printf ("%d",SumP);
        printf ("\nCay khung: (dinh dau) (dinh cuoi):\n");
        for (int k = 1; k < n; ++k)
             printf ("\n%d %d",dd[Trace[k]],dc[Trace[k]]);
    }
    int main(){
        Input();
        Process();
        Output();
    }
    Nếu cần giúp đỡ, hỗ trợ:
    Bài Tập. Đồ Án. Tools. Phần mềm. Liên hệ:
    Facebook: http://www.facebook.com/thuecodedoan
    Website: https://thuecodedoan.wordpress.com
    Email: thuecodedoan@gmail.com
    Sđt: 094.76.76.854

Các đề tài tương tự

  1. Lưu đồ giải thuật Kruskal
    Gửi bởi nguyenhaily trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 4
    Bài viết cuối: 18-01-2015, 11:42 PM
  2. Giải thuật Kruskal là như thế nào?
    Gửi bởi nguyenhaily trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 21-09-2010, 12:11 AM
  3. lưu đồ giải thuật Kruskal. Giúp em sửa với
    Gửi bởi nguyenhaily trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 15-09-2010, 02:28 PM
  4. Tìm cây có trọng lượng nhỏ nhất bằng giải thuật Kruskal
    Gửi bởi nguyenhaily trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 30-08-2010, 12:04 PM
  5. giải thuật kruskal !
    Gửi bởi haba trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 02-04-2009, 11:10 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn