TECHNOLOGIES
FORUMS
JOBS
BOOKS
EVENTS
INTERVIEWS
Live
MORE
LEARN
Training
CAREER
MEMBERS
VIDEOS
NEWS
BLOGS
Sign Up
Login
No unread comment.
View All Comments
No unread message.
View All Messages
No unread notification.
View All Notifications
Answers
Post
An Article
A Blog
A News
A Video
An EBook
An Interview Question
Ask Question
Forums
Monthly Leaders
Forum guidelines
umesh adroja
NA
27
844
TOPOLOGICAL SORT
Mar 31 2016 8:29 AM
#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();
}
Reply
Answers (
0
)
How to reset counting?
local database Search option