دوشنبه بیست و پنجم اردیبهشت 1391ساعت 23:24 | 

یکشنبه بیست و چهارم اردیبهشت 1391ساعت 15:37 | 

-> This Program is to implement Kruskal algorithm.

-> This program is to find minimum spanning tree
for undirected weighted graphs

-> Data Structers used:
Graph:Adjacency Matrix

-> This program works in microsoft vc++ 6.0 environment.

**************************************************************/

#include<iostream.h>
class kruskal
{
private:
int n; //no of nodes
int noe; //no edges in the graph
int graph_edge[100][4];

int tree[10][10];

int sets[100][10];
int top[100];
public:
void read_graph();
void initialize_span_t();
void sort_edges();
void algorithm();
int find_node(int );
void print_min_span_t();
};

void kruskal::read_graph()
{
cout<<"*************************************************\n"
<<"This program implements the kruskal algorithm\n"
<<"*************************************************\n";
cout<<"Enter the no. of nodes in the undirected weighted graph ::";
cin>>n;

noe=0;

cout<<"Enter the weights for the following edges ::\n";
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
cout<<" < "<<i<<" , "<<j<<" > ::";
int w;
cin>>w;
if(w!=0)
{
noe++;

graph_edge[noe][1]=i;
graph_edge[noe][2]=j;
graph_edge[noe][3]=w;
}
}
}

// print the graph edges

cout<<"\n\nThe edges in the given graph are::\n";
for(i=1;i<=noe;i++)
cout<<" < "<<graph_edge[i][1]
<<" , "<<graph_edge[i][2]
<<" > ::"<<graph_edge[i][3]<<endl;

}

void kruskal::sort_edges()
{
/**** Sort the edges using bubble sort in increasing order**************/

for(int i=1;i<=noe-1;i++)
{
for(int j=1;j<=noe-i;j++)
{
if(graph_edge[j][3]>graph_edge[j+1][3])
{
int t=graph_edge[j][1];
graph_edge[j][1]=graph_edge[j+1][1];
graph_edge[j+1][1]=t;

t=graph_edge[j][2];
graph_edge[j][2]=graph_edge[j+1][2];
graph_edge[j+1][2]=t;

t=graph_edge[j][3];
graph_edge[j][3]=graph_edge[j+1][3];
graph_edge[j+1][3]=t;
}
}
}

// print the graph edges

cout<<"\n\nAfter sorting the edges in the given graph are::\n";
for(i=1;i<=noe;i++)
cout<<" < "<<graph_edge[i][1]
<<" , "<<graph_edge[i][2]
<<" > ::"<<graph_edge[i][3]<<endl;
}

void kruskal::algorithm()
{
// ->make a set for each node
for(int i=1;i<=n;i++)
{
sets[i][1]=i;
top[i]=1;
}

cout<<"\nThe algorithm starts ::\n\n";

for(i=1;i<=noe;i++)
{
int p1=find_node(graph_edge[i][1]);
int p2=find_node(graph_edge[i][2]);

if(p1!=p2)
{
cout<<"The edge included in the tree is ::"
<<" < "<<graph_edge[i][1]<<" , "
<<graph_edge[i][2]<<" > "<<endl<<endl;

tree[graph_edge[i][1]][graph_edge[i][2]]=graph_edge[i][3];
tree[graph_edge[i][2]][graph_edge[i][1]]=graph_edge[i][3];

// Mix the two sets

for(int j=1;j<=top[p2];j++)
{
top[p1]++;
sets[p1][top[p1]]=sets[p2][j];
}

top[p2]=0;
}
else
{
cout<<"Inclusion of the edge "
<<" < "<<graph_edge[i][1]<<" , "
<<graph_edge[i][2]<<" > "<<"forms a cycle so it is removed\n\n";
}
}
}

int kruskal::find_node(int n)
{
for(int i=1;i<=noe;i++)
{
for(int j=1;j<=top[i];j++)
{
if(n==sets[i][j])
return i;
}
}
return -1;
}

int main()
{
kruskal obj;
obj.read_graph();
obj.sort_edges();
obj.algorithm();
return 0;
}
===
منبع :
http://ds4beginners.wordpress.com/2006/10/05/kruskals-algorithm-for-minimum-spanning-tree/

شنبه شانزدهم اردیبهشت 1391ساعت 1:59 | 

جمعه یکم اردیبهشت 1391ساعت 13:43 | 

چهارشنبه بیست و سوم فروردین 1391ساعت 15:3 | 

دوشنبه بیست و یکم فروردین 1391ساعت 12:43 | 

#include <iostream.h>
#include <conio.h>
#include <string.h>
int main()
{
    char strNum1[50];
    char strNum2[50];
    int carry = 0;

    cout<< "Please Enter a Number"<<endl;
    cin >> strNum1;

    cout << "please enter another number"<<endl;
    cin >> strNum2;

    int min = (strlen(strNum1)>strlen(strNum2)) ? strlen(strNum2) : strlen(strNum1);
    char result[50];

    strrev(strNum1);
    strrev(strNum2);

    int i=0;
    for(; i<min;i++)
    {
        int a = strNum1[i]-48;
        int b = strNum2[i]-48;
        result[i] = (a +b + carry)%10;
        carry = (a + b + carry)/10;
        result[i] += 48; 
    }

    if(strlen(strNum1)>strlen(strNum2))
    {
        while(i<strlen(strNum1))
        {
            result[i] = ((strNum1[i]-48 + carry)%10)+48;
            carry = (strNum1[i]-48 + carry)/10;
            i++;
        }
    }
    else
    {
        while(i<strlen(strNum2))
        {
            result[i] = ((strNum2[i]-48 + carry)%10)+48;
            carry = (strNum2[i]-48 + carry)/10;
            i++;
        }
    }
    if(carry>0) result[i++] = carry+48;
    result[i++] = '\0';

    strrev(result);
    cout<<result;
    getch();
    return 0;
}

دوشنبه بیست و یکم فروردین 1391ساعت 11:47 | 

 int chartoint(char _num)
    {
        int num; 
        num = _num-48;
        return num;  
    }

دوشنبه بیست و یکم فروردین 1391ساعت 11:36 | 

پنجشنبه هفدهم فروردین 1391ساعت 5:35 | 

پنجشنبه هفدهم فروردین 1391ساعت 5:1 |