인접 표 토폴로지 정렬
2253 단어 인접 표 토폴로지 정렬
// , ,
#include<stdio.h>
#include<malloc.h>
#include<stack>
using namespace std;
#define MAX_VERTEX_NUM 20
int visited[100];
typedef struct arcnode
{
int adjvex;
struct arcnode *nextarc;
int info;
}*arcnod,arcnode1;
typedef struct vertexnode
{
int data;
arcnode1 *firstarc;
}*vertexnod,vertex;
typedef struct
{
vertex ver[MAX_VERTEX_NUM];
int vexnum,arcnum;
}*adjlist,adjlist1;
int find(adjlist &g,int x)
{
int x1;
for(int i=0;i<g->vexnum;i++)
{
if(g->ver[i].data==x)
{
x1=i;
break;
}
}
return x1;
}
void create(adjlist &g)
{
int i,k=1,x1,x2;
arcnod s1;
printf(" : ");
scanf("%d%d",&g->vexnum,&g->arcnum);
printf(" : ");
for(i=0;i<g->vexnum;i++)
{
scanf("%d",&g->ver[i].data);
g->ver[i].firstarc=NULL;
}
for(i=0;i<g->arcnum;i++)
{
adjlist g1,g2;
g1=g;
g2=g;
printf(" %d , , : ",k++);
scanf("%d%d",&x1,&x2);
int t1=x1,t2=x2;
x1=find(g1,x1);
x2=find(g2,x2);
s1=(arcnod)malloc(sizeof(arcnode1));
s1->adjvex=x2;
s1->nextarc=g->ver[x1].firstarc;
g->ver[x1].firstarc=s1;
}
}
void findID(adjlist &g,int indegree[MAX_VERTEX_NUM])
{
int i;
arcnod p;
for(i=0;i<g->vexnum;i++)
indegree[i]=0;
for(i=0;i<g->vexnum;i++)
{
p=g->ver[i].firstarc;
while(p!=NULL)
{
indegree[p->adjvex]++;
p=p->nextarc;
}
}
}
int toposort(adjlist &g)
{
stack<int>dsta;
int indegree[MAX_VERTEX_NUM];
int i,count,k,k0;
arcnod p;
findID(g,indegree);
for(i=0;i<g->vexnum;i++)
if(indegree[i]==0)
dsta.push(i);
count=0;
while(!dsta.empty())
{
k0=dsta.top();
dsta.pop();
printf("%d ",g->ver[k0].data);
count++;
p=g->ver[k0].firstarc;
while(p!=NULL)
{
k=p->adjvex;
indegree[k]--;
if(indegree[k]==0)
dsta.push(k);
p=p->nextarc;
}
}
if(count<g->vexnum)
return 0;
else
return 1;
}
int main()
{
adjlist g;
g=(adjlist)malloc(sizeof(adjlist1));
create(g);
int t=toposort(g);
printf("
[%d]
",t);
return 0;
}