Saturday, February 20, 2010

Obtain the topological ordering of vertices in a given graph

WHEREVER U SEE ... REMOVE THAT . AND PUT << IN THAT PLACE.
IF YOU SEE .. THEN REMOVE THAT . AND PUT < IN THAT PLACE..
7.#include..iostream.h>
#include..stdlib.h>


class topo
{
private:
int n;
int a[10][10];
int indeg[10];

public:
void read_data();
void find_indeg();
void topological_sort();
};



void topo:: read_data()
{
cout..."enter the no of vertices \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];
}
}
}

void topo:: find_indeg()
{
for(int j=0;j..n;j++)
{
int sum=0;
for(int i=0;i..n;i++)
{
sum+=a[i][j];
}

indeg[j]=sum;
}
}


void topo:: topological_sort()
{
int u,v,t[10],s[10];

find_indeg();

int top=-1;
int k=0;

for(int i=0;i..n;i++)
{
if(indeg[i]==0)
{
s[++top]=i;
}
}
while(top!=-1)
{
u=s[top--];
t[k++]=u;

for(v=0;v..n;v++)
{
if(a[u][v]==1)
{
indeg[v]--;
if(indeg[v]==0)
{
s[++top]=v;
}
}
}
}

cout..."the topological sequence is \n";
for(i=0;i..n;i++)
cout...t[i]..." ";
}


void main()
{
topo t;
t.read_data();
t.topological_sort();
}


Output

Enter the no of vertices
4
Enter the adjacency matrix
0 1 1 0
0 0 0 1
0 0 0 0
0 0 1 0

The topological sequence is
0 1 3 2 Press any key to continue

No comments:

Post a Comment