Tech
Forums
Jobs
Books
Events
Videos
Live
More
Interviews
Certification
Training
Career
Members
News
Blogs
Contribute
An Article
A Blog
A Video
An Ebook
An Interview Question
Register
Login
0
Answer
TOPOLOGICAL SORT
umesh adroja
8y
346
1
Reply
#include<iostream.h>
#include<conio.h>
class
topologicalorder
{
private
:
int
n;
int
a[10][10];
int
indegree[10];
public
:
void
read_data();
void
find_indegree();
void
topological_sort();
};
void
topologicalorder::read_data()
{
cout<<
"Enter the no of jobs :\n"
;
cin>>n;
cout<<
"Enter the adjancency matrix :\n"
;
for
(
int
i=0;i<n;i++)
{
for
(
int
j=0;j<n;j++)
{
cin>>a[i][j];
}
}
}
void
topologicalorder::find_indegree()
{
for
(
int
j=0;j<n;j++)
{
int
sum=0;
for
(
int
i=0;i<n;i++)
{
sum+=a[i][j];
}
indegree[j]=sum;
}
}
void
topologicalorder::topological_sort()
{
int
u,v,t[10],s[10];
find_indegree();
int
top=-1;
int
k=0;
for
(
int
i=0;i<n;i++)
{
if
(indegree[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)
{
indegree[v]--;
if
(indegree[v]==0)
s[++top]=v;
}
}
}
cout<<
"the topological sequence is :\n"
;
for
(i=0;i<n;i++)
cout<<t[i]<<
" "
;
}
void
main()
{
topologicalorder t;
clrscr();
t.read_data();
t.topological_sort();
getch();
}
Post
Reset
Cancel
Answers (
0
)
Next Recommended Forum
How to reset counting?
local database Search option