nusrath is this correct

[tasha]

DIJKSTRA ALGO





#include<iostream.h>
class dijkstra
{
private:int n,a[10][10],d[10],p[10];
public:void read_data();
void print_path();
void optimal_solu(int,int);
};
void dijkstra::optimal_solu(int source,int des)
{
int i,j,u,v,min,s[10];
for(i=0;i<n;i++)
{
d[i]=a[source][i];
s[i]=0;
p[i]=source;
}
s[source]=1;
for(i=1;i<n;i++)
{
min=9999;
u=-1;
for(j=0;j<n;j++)
{
if(s[j]==0)
{
if(d[j]<min)
{
min=d[j];
u=j;
}
}
}
if(u==-1)
return;
s[u]=1;
if(u==des)
return;
for(v=0;v<n;v++)
{
if(s[v]==0)
{
if(d[u]+a[u][v]<d[v])
{
d[v]=d[u]+a[u][v];
p[v]=u;
}
}
}
}
}
void dijkstra::read_data()
{
int i,j;
cout<<"enter the num of nodes"<<endl;
cin>>n;
cout<<"enter the adjacency matrix"<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
cin>>a[i][j];
}
}
}

void dijkstra::print_path()
{
for(int source=0;source<n;source++)
{
for(int des=0;des<n;des++)
{
optimal_solu(source,des);
if(d[des]==9999)
cout<<des<<"is not reachable form"<<source<<endl;
else
{
cout<<"the shortest path is shown below"<<endl;
int i=des;
while(i!=source)
{
cout<<i<<"<--";
i=p[i];
}
cout<<i<<"="<<d[des]<<endl;
}
}
}
}
int main()
{
dijkstra a;
a.read_data();
a.print_path();
}



KRUSKAL ALGO



#include<iostream.h>
class kruskal
{
int c[10][10];
public: int m,n;
void obtain();
void min();
};
void kruskal::obtain()
{
int i,j,u,v;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
c[i][j]=999;
}
}
for(i=0;i<n;i++)
{
cout<<"enter the next edge u v "<<endl;
cin>>u>>v;
cout<<"enter cost"<<endl;
cin>>c[u][v];
c[v][u]=c[u][v];
}
}
int find(int v,int p[])
{
while(p[v]!=v) v=p[v];
return v;
}
void union_ij(int i,int j,int p[])
{
if(i<j)
p[j]=i;
else
p[i]=j;
}

void kruskal::min()
{
int count,i,p[10],min,j,u,v,k,t[10][2],sum;
count=0;
k=0;
sum=0;
for(i=0;i<n;i++)
p[i]=i;
while(count<n)
{
min=999;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(c[i][j]<min)
{
min=c[i][j];
u=i;
v=j;
}
}
}
if(min==999)
break;
i=find(u,p);
j=find(v,p);
if(i!=j)
{
t[k][0]=u , t[k][1]=v,k++;
count++;
sum+=min;
union_ij(i,j,p);
}
c[u][v]=c[v][u]=999;
}
if(count==n-1)
{
cout<<"cost of spanning tree= "<<sum<<endl;
cout<<"spanning tree is shown below"<<endl;
for(k=0;k<n-1;k++)
cout<<t[k][0]<<","<<t[k][1]<<endl;
return;
}
cout<<"spanning tree doesnt exist"<<endl;
}
int main()
{
kruskal k;
cout<<"enter no of nodes"<<endl;
cin>>k.m;
cout<<"enter the no. of edges"<<endl;
cin>>k.n;
cout<<"enter the edge list"<<endl;
k.obtain();
k.min();
}


PRIMS ALGO



#include<iostream.h>
class prims
{
int n;
int a[10][10];
public:
void read();
void spantree();
};
void prims::spantree()
{
int i,j,u,v,min,sum,k,t[10][2],p[10],d[10],s[10];
int source;
min=9999;
source=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(a[i][j]!=0 && a[i][j]<=min)
{
min=a[i][j];
source=i;
}
}
}
for(i=0;i<n;i++)
{
d[i]=a[source][i];
s[i]=0;
p[i]=source;
}
s[source]=1;
sum=0;
k=0;
for(i=1;i<n;i++)
{
min=9999;
u=-1;
for(j=0;j<n;j++)
{
if (s[j]==0)
{
if(d[j]<=min)
{
min=d[j];
u=j;
}
}
}

t[k][0]=u;
t[k][1]=p[u];
k++;

sum+=a[u][p[u]];
s[u]=1;
for(v=0;v<n;v++)
{
if(s[v]==0 && a[u][v]<d[v])
{
d[v]=a[u][v];
p[v]=u;
}

}}
if (sum>=9999)
cout<<"spannin tree not existin"<<endl;
else
{
cout<<"spannin tree exists and min tree is"<<endl;
for(i=0;i<n-1;i++)
{
cout<<t[i][0]<<" "<<t[i][1]<<endl;
}
cout<<"the cost of spannin tree="<<sum<<endl;
}
}
void prims::read()
{
int i,j;
cout<<"enter no of nodes"<<endl;
cin>>n;
cout<<"enter cost adjacendy matrix"<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
cin>>a[i][j];
}
}
}
int main()
{
prims a;
a.read();
a.spantree();
}



BFS ALGO


#include<iostream.h>

class reachable
{
int n,s[20],a[20][20],source;

public:

void read_data()
{
cout<<"Enter the number of nodes\n";
cin>>n;
cout<<"Enter the adjacency matrix\n";
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>a[i][j];
}
}
cout<<"Enter the source\n";
cin>>source ;
}

void print_data()
{
for(int i=0;i<n;i++)
{
if(s[i]==0)
cout<<"Vertex"<<i<<"is not reachable\n";
else
cout<<"Vertex"<<i<<"is reachable\n";

}
}


void bfs_traversal()
{
int f,r,q[20],u,v;

for(int i=1;i<=n;i++)s[i]=0;

f=r=0;
q[r]=source;
s[source]=1;

while(f<=r)
{
u=q[f++];
for(v=1;v<=n;v++)
{
if(a[u][v]==1 && s[v]==0)
{
s[v]=1;
q[++r]=v;
}}
}
}
};


int main()
{

reachable a;
a.read_data();
a.bfs_traversal();
a.print_data();
}


HORSPOOL ALGO



#include<iostream.h>
#include<string.h>
#include<stdio.h>
class horspool
{
char p[40],t[40];
int m,n,s[256];
public: void read()
{
cout<<"enter text string";
gets(t);
cout<<"enter the pattern string";
gets(p);
}
void shift()
{
int i;
m=strlen(p);
for(i=0;i<128;i++)
s[i]=m;
for(i=0;i<m-1;i++)
{
s[p[i]]=m-1-i;
}
}
int pattern()
{
int i,k;
shift();
m=strlen(p);
n=strlen(t);
i=m-1;
while(i<n)
{
k=0;
while(k<m && t[i-k]==p[m-1-k])
{
k++;
}
if(k==m) return i-m+1;
i=i+s[t[i]];
}
return -1;
}
};
int main()
{
horspool a;
int pos;
a.read();
pos=a.pattern();
if(pos==-1)
cout<<"pattern string not found";
else cout<<"pattern string found at"<<pos+1<<"position";
}



DFS ALGO


#include<iostream.h>
class graph
{
private : int n;
int a[10][10];
public : void read()
{
int i,j;
cout<<"enter no. of node: "<<endl;
cin>>n;
cout<<"enter cost adjacency matrix"<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
cin>>a[i][j];
}
}
}
void dfs(int u,int s[])
{
int v;
s[u]=1;
for(v=0;v<n;v++)
{
if (a[u][v]==1 && s[v]==0)
{
dfs(v,s);
}
}
}
void reachab()
{
int i,source,s[10];
for(i=0;i<n;i++) s[i]=0;
cout<<"enter the source"<<endl;
cin>>source;
dfs(source,s);
for(i=0;i<n;i++)
{
if (s[i]==0)
cout<<"node"<<i<<"is not reachable"<<endl;
else cout<<"node"<<i<<"is reachable"<<endl;
}
}
int conn()
{
int i,j,flag,s[10];
for(j=0;j<n;j++)
{
for(i=0;i<n;i++)
dfs(j,s);
flag=0;
for(i=0;i<n;i++)
{
if(s[i]==0) flag=1;
}
if (flag==0) return 1;
}
return 0;
}
};
int main()
{
graph g;
g.read();
g.reachab();
int flag=g.conn();
if(flag==1)
cout<<"graph is connected"<<endl;
else cout<<"graph not connected"<<endl;
}


N QUEENS PROBLEM



#include<iostream.h>
#include<math.h>

#define true 1
#define false 0

void print_solution(int n,int x[])
{
char c[100][100];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
c[i][j]='X';

for(int i=1;i<=n;i++)
c[i][x[i]]='Q';

for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<c[i][j];
}
cout<<"\n";
}
}


int place(int x[],int k)
{
for(int i=1;i<k;i++)
if(x[i]==x[k] || i-x[i]==k-x[k] || i+x[i]==k+x[k])
return false;
return true;
}

void nqueens(int n)
{
int x[100],count=0,k=1;
x[k]=0;
while(k!=0)
{
x[k]+=1;
while((x[k]<=n)&&(!place(x,k)))
x[k]+=1;
if(x[k]<=n)
{
if(k==n)
{
count++;
cout<<"solution"<<count<<"is\n";
print_solution(n,x);
}
else
{
k++;
x[k]=0;
}
}
else
{
k--;
}
}
return;
}
int main()
{
int n;
cout<<"enter vthe number of queens\n";
cin>>n;
nqueens(n);
}

[Zeillinger]

Man, this could be a really great post if it was a little organized. Took me a few minutes to get it but this is actually an implementation of the following algorithms / solution to the following problems (haven't actually checked any of code):

(1) http://en.wikipedia.org/wiki/Dijkstra's_algorithm
(2) http://en.wikipedia.org/wiki/Prim's_algorithm
(3) http://en.wikipedia.org/wiki/Kruskal's_algorithm
(4) http://en.wikipedia.org/wiki/Breadth-first_search
(5) http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm
(6) http://en.wikipedia.org/wiki/Depth-first_search
(7) http://en.wikipedia.org/wiki/Eight_queens_puzzle