云大《数据结构》课程教学课件-第7章 图(160P).pptVIP

for(j=0;jn;j++)/*扫描顶点表,依次取顶点v j*/ {p=dig[j].link; while(p)/*扫描顶点的v j的出边表*/ {/*计算各边v j,v k所代表的活动ai的e[i]和l[i]*/ k=p?adjvex; e[++i] =ve[j]; l[i]=vl[k]-p?dut; printf(“%d\t%d\t%d\t%d\%d\t”,/*输出活动ai的 有关信息*/ dig[j].vertex+1,dig[k].vertex+1,e[i],l[i],l[i]-e[i]); if(l[i]==e[i]) printf(critical activity); printf(\n); p=p-next; } } } 上述算法的时间复杂度为O(n+e)。 返回首页 返回主目录 * 数据结构 * 作业: 7.12 * * * * * * * * * 数据结构 * 二、如何构造拓扑排序？ 2、拓扑排序算法的具体实现： 1、基本思想1）从网中选择一个入度为零的顶点且输出之；2）从网中删除此顶点及其所有出边。反复执行这两步，直至所有顶点都已输出，或者直到余留在网中的顶点入度都不为零时为止。 技巧1：表的顶点表中增加一个入度域，用于存储各个顶点的当前入度值。 * 数据结构 * 技巧1：表的顶点表中增加一个入度域，用于存储各个顶点的当前入度值。 vertex id link 顶点表中元素的结构 v0 v1 v2 v3 v4 邻接表 vertex id link v0v1v2v3v4 1 2 3 2 4 4 3 ^ 01222 * 数据结构 * for(k=0;ke;k++) {scanf(%d%d,i,j); s=malloc(sizeof(edgenode)); s?adjvex=j;s?next=dig[i].link;dig[i].link=s;dig[j].id++; }} creatadjlist(dig)vexnode dig[ ];{int i,j,k; edgenode *s; for(i=0;in;i++) {dig[i].vertex=getchar( ); dig[i].id=0; dig[i].link=NULL; } 建立上述邻接表的算法如下： * 数据结构 * 二、如何构造拓扑排序？ 2、拓扑排序算法的具体实现： 1、基本思想1）从网中选择一个入度为零的顶点且输出之；2）从网中删除此顶点及其所有出边。反复执行这两步，直至所有顶点都已输出，或者直到余留在网中的顶点入度都不为零时为止。 技巧1：表的顶点表中增加一个入度域，用于存储各个顶点的当前入度值。 * 数据结构 * 技巧2：为了避免每次寻找入度为0的顶点时重复扫描顶点表，引入一个链栈(队列也可),将一次扫描找到的入度为0的顶点入栈。这样，以后选入度为0的顶点时，可直接从栈顶取。并且，在排序过程中，一旦出现新的入度为0的顶点，将其入栈。 技巧3：算法在具体实现过程中，没有开辟额外的堆栈空间，而是利用顶点表中入度为0的元素所占空间组成一个静态链栈，入度为0的元素的id域为静态链栈结点的链域。 vertex id link v0v1v2v3v4 1 2 3 2 3 ^ 01220 ^ vertex id link v0v1v2v3v4 1 2 3 2 3 ^ -11220 ^ top (top=4) * 数据结构 * 3、拓扑算法梗概 （1）??? 扫描顶点表，将入度为零的顶点入栈； （2）??? while（栈非空） {  将栈顶顶点vj弹出并输出之； 检查vj的出边表，将每条出边〈vj,vk〉的 终点vk的入度减1。 若vk的入度变为0，则把vk推入栈； } （3）若输出的顶点数小于n，则输出“有回路”；否则拓扑排序正常结束。 * 数据结构 * topsort(dig)vexnode dig[ ];{ int i,j,k,m=0,top=-1; edgenode *p; for (i=0;in;i++) if (dig[i].id==0)  {dig[i].id=top; top=i; } /*AOV网的邻接表*/