, if(q->ivex==1)q=q->ilink else q=q->jlink; if(r->ivex=i)r->lik=pJ/注意i值既可能出现在边结点的ivex域中, else r-> blink=p;∥又可能出现在边结点的jvex域中 }/else/插入i链表尾部 if(!G ad]mulit [ ] firstedge)G. adjmulist[].firstedge=p; else q=G. adjmulist i firsted ge, while(q) q if(q->jvexDq=q->jlink; else q=q->ink; if(r->jex=D)r->jlink=p else r->ilink=p lele/插入j链表尾部 i//for eturn oK 3//Build AdjList 720 int Pass MGraph( MGraph g判断一个邻接矩阵存储的有向图是不是可传递的, 是则返回1,否则返回0 for(x=0; X<G. vexnum; x++) for(y=0; y<G. vexnum; y++) if(G arcs]yD for(z=0; Z<G. vexnum; Z++) if(zl=x&& G arcs[z]&& G arcs][z]) return0/图不可传递的条件 i/if eturn i//Pass MGraph 分析:本算法的时间复杂度大概是O(n^2*d) 721 int Pass ALGraph( ALGraph G判断一个邻接表存储的有向图是不是可传递的, 是则返回1,否则返回0{ r=q; if(q->ivex==i) q=q->ilink; else q=q->jlink; } if(r->ivex==i) r->ilink=p;//注意 i 值既可能出现在边结点的 ivex 域中, else r->jlink=p; //又可能出现在边结点的 jvex 域中 }//else //插入 i 链表尾部 if(!G.adjmulist[j].firstedge) G.adjmulist[j].firstedge=p; else { q=G.adjmulist[i].firstedge; while(q) { r=q; if(q->jvex==j) q=q->jlink; else q=q->ilnk; } if(r->jvex==j) r->jlink=p; else r->ilink=p; }//else //插入 j 链表尾部 }//for return OK; }//Build_AdjList 7.20 int Pass_MGraph(MGraph G)//判断一个邻接矩阵存储的有向图是不是可传递的, 是则返回 1,否则返回 0 { for(x=0;x<G.vexnum;x++) for(y=0;y<G.vexnum;y++) if(G.arcs[x][y]) { for(z=0;z<G.vexnum;z++) if(z!=x&&G.arcs[y][z]&&!G.arcs[x][z]) return 0;//图不可传递的条件 }//if return 1; }//Pass_MGraph 分析:本算法的时间复杂度大概是 O(n^2*d). 7.21 int Pass_ALGraph(ALGraph G)//判断一个邻接表存储的有向图是不是可传递的, 是则返回 1,否则返回 0