新建 文本文档 (3).txt

这个是数据结构几个重要的实验,大家方便的话可以

有向图的拓扑排序:
基本要求:
1.输入顶点和边的信息,以改进的邻接链表作为图的存储结构,然后输出图的邻接矩阵
2. 编写函数实现图的拓扑排序,并输出图经过拓扑排序后得到的序列
实现提示:
图的存储结构:
typedef struct node0
{ int vex;0
struct node link;}edgenode;
typedef struct vnode0
{ int id;0
struct node link;0
} vexnode;0
拓扑排序算法 :
void toposort(vexnode dig[ ]) 0
{ /*AOV网的邻接链表 */0
edgenode *p;0
top=0; m=0;0
for(i=1; i0) 0
{ j=top; top=dig[top].id;0
printf(〃%d\n〃, j); /*删除入度为零的顶点并输出 */0
m++; p=dig[j].link;0
While (p![KG-*2]=NULL) 0
{ k=p->vex;0
dig[k].id--; /*把以vj为尾的弧的头顶点vk的入度减1*/0
if (dig[k]==0) {dig[k].id=top; top=k; }0
p=p->link;0
}0
}0
if (m } /*toposort*/0