C++ code for Kruskal Algorithm

Discussion in 'C++' started by ravi_forum, Sep 12, 2006.

  1. ravi_forum

    ravi_forum New Member

    Joined:
    Sep 12, 2006
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    Sir,

    I wanted to know the implementation code for krushkal algorithm in C++.

    Anyone can help me to give the code.
    ThnQ
     
  2. Aztec

    Aztec New Member

    Joined:
    May 9, 2006
    Messages:
    90
    Likes Received:
    0
    Trophy Points:
    0
    Take a look here
     
  3. ravi_forum

    ravi_forum New Member

    Joined:
    Sep 12, 2006
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    Thanks for the link.
     
  4. Pratish

    Pratish New Member

    Joined:
    Nov 10, 2007
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    I wanted to know the implementation code for krushkal algorithm, Breadth first search and index sequencial search in C++/C/Java. I also want to knw the code for converting Infix expression to postfix and prefix expression using stack and binary tree...
     
  5. Pratish

    Pratish New Member

    Joined:
    Nov 10, 2007
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    uiyityyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
     
  6. NewsBot

    NewsBot New Member

    Joined:
    Dec 2, 2008
    Messages:
    1,267
    Likes Received:
    2
    Trophy Points:
    0
    Make sure you do not make posts like this one or we may be forced to ban you.
     
  7. hosam

    hosam New Member

    Joined:
    Aug 15, 2011
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    Thank you very much for helping us ... and I hope to continue this site in the production and the continuation of Members to work together to build a new minds in this world .. and far from politics
     
  8. Jacobhine

    Jacobhine New Member

    Joined:
    Aug 8, 2011
    Messages:
    5
    Likes Received:
    0
    Trophy Points:
    0
    Thanks for the link Aztec, it is helpful
     
  9. Linda87st

    Linda87st New Member

    Joined:
    Oct 27, 2011
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    Thank you very much for helping us ... and I hope to continue this site in the production and the continuation of Members to work together to build a new minds in this world .. and far from politics
     
  10. pravinkandala

    pravinkandala New Member

    Joined:
    Nov 25, 2011
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    yet student!!
    Location:
    Hyderabad, India
    Home Page:
    https://www.facebook.com/pravinkandala
    Code:
    /* Write C++ programs to implement the Kruskal’s algorithm to generate a minimum cost spanning tree */
    
    #include<iostream>
    #include<conio.h>
    #include<stdlib.h>
    using namespace std;
    int cost[10][10],i,j,k,n,m,c,visit,visited[10],l,v,count,count1,vst,p;
     
    main()
    {
    int dup1,dup2;
    cout<<"enter no of vertices";
    cin >> n;
    cout <<"enter no of edges";
    cin >>m;
    cout <<"EDGE Cost";
    for(k=1;k<=m;k++)
    {
    cin >>i >>j >>c;
    cost[i][j]=c;
    cost[j][i]=c;
    }
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    if(cost[i][j]==0)
    cost[i][j]=31999;
    visit=1;
    while(visit<n)
    {
    v=31999;
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    if(cost[i][j]!=31999 && cost[i][j]<v  && cost[i][j]!=-1 )
    {
    int count =0;
    for(p=1;p<=n;p++)
    {
    if(visited[p]==i || visited[p]==j)
    count++;
    }
    if(count >= 2)
    {
    for(p=1;p<=n;p++)
    if(cost[i][p]!=31999 && p!=j)
    dup1=p;
    for(p=1;p<=n;p++)
    if(cost[j][p]!=31999 && p!=i)
    dup2=p;
     
    if(cost[dup1][dup2]==-1)
    continue;
    }
    l=i;
    k=j;
    v=cost[i][j];
    }
    cout <<"edge from " <<l <<"-->"<<k;
    cost[l][k]=-1;
    cost[k][l]=-1;
    visit++;
    int count=0;
    count1=0;
    for(i=1;i<=n;i++)
    {
    if(visited[i]==l)
    count++;
    if(visited[i]==k)
    count1++;
    } 
    if(count==0)
    visited[++vst]=l;
    if(count1==0)
    visited[++vst]=k;
    }
    }
    
    
    OUTPUT
    enter no of vertices4
    enter no of edges4
    EDGE Cost
    1 2 1
    2 3 2
    3 4 3
    1 3 3
    edge from 1–>2edge from 2–>3edge from 1–>3
     
  11. sourabh1989

    sourabh1989 New Member

    Joined:
    Mar 15, 2012
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    hii sir,
    plz give me the explanation of this code.. i have some doubts in this code..

    thanks.

    Regards
    sourabh khandelwal
     
  12. lishihong108

    lishihong108 New Member

    Joined:
    Mar 26, 2012
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    student
    Location:
    China
    Hello,everyone,!I am new here .Today is my first day.I'm from China.My English is not very good.Because I majorde in programming and very like it.I come here.I want to make freinds with people who spaeak English.My e-mail is lishihong108@gmail.com.If you interested to me,please e-mail to me.I wait your voice.Good luck to you!
     
  13. happyuk

    happyuk New Member

    Joined:
    Apr 14, 2013
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    Google "kruskal boost mfc" for a C++ / MFC application that allows the user to interactively add nodes, links etc and uses the Boost Graph library to calculate the minimal spanning tree.
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice