如何用C++语言实现AOV网的所有拓扑排序?(最好能实现动态演示)

发布网友发布时间：2022-04-30 17:13

共1个回答

热心网友时间：2022-06-28 05:46

#define max 图的顶点数
//弧节点的结构
typedef struct EdgeNode
{
int adjvex;
struct EdgeNode *next;
};
//顶点节点的结构
typedef struct Vnode
{
VertexType vertex;//顶点数据类型
EdgeNode *link;
}Adjlist[max];
//拓扑排序算法描述
void topsort(Adjlist g)
//假设G有n个顶点、e条边的有向图，g是他的邻接表，每个节点设两个
//域vex，next，对入度为0的顶点设计带链的栈，top指示栈的指针，in为入度
{
readlist();//输入e条弧并建立邻接表
top=0;
for(i=1;i<=n;i++)//查入度为0的顶点，并建立链栈
if(g[i].in==0)
{
g[i].in=top;
top=i;
}
m=0;//设m为计数器计算输出的顶点个数
while(top!=0)
{
j=top;
top=g[top].in;//退栈
printf("%d",j);
m++;//输出顶点并计数
q=g[j].link;//q是指针，指示以j为尾的弧
while(q!=NULL)
{
k=q->vex;//顶点k为j的直接后继
g[k].in=g[k].in-1;//入度减1
if(g[k].in==0)
{
g[k].in=top;
top=k;//入度为0的顶点进栈
}
q=p->next;
}
}
if(m<n)
printf("the network have cycle");//输出顶点数不足n，说明网中无环
}