, 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
for(x=0; X<G. vexnum; x++) for(p=G vertices[x]. firstarc: p: p=p->nextarc) y=p->adjvex for(q=G vertices ]. firstarc; q: q=q->nextarc) if(zl=x&&! is adj(G, x, z)) return 0; i//for i//Pass ALGraph int is adj( ALGraph C, int m, int ny/判断有向图G中是否存在边(mn),是则返回1, 否则返回0 for(p=G vertices(m). firstarc p: p=p->nextarc) if(p->adjvex--n) return 1 return 0 i//is adj 722 int visited MAXSIZE]∥指示顶点是否在当前路径上 int exist_ path DFS( ALGraph G, int i, int j)∥/深度优先判断有向图G中顶点i到顶点 j是否有路径是则返回1,否则返回0 ifi=j) return1;∥就是 visited [F=1 for(p=G vertices ]. firstarc, p: p=p->nextarc) k=p->adjvex if(!visited [k]&& exist_path(kj) return 1/下游的顶点到j有路径 i//else i//exist path DFS 7.23 int exist path BFS( ALGraph g,nti,itj)∥广度优先判断有向图G中顶点i到顶点 j是否有路径,是则返回1,否则返回0
{ for(x=0;x<G.vexnum;x++) for(p=G.vertices[x].firstarc;p;p=p->nextarc) { y=p->adjvex; for(q=G.vertices[y].firstarc;q;q=q->nextarc) { z=q->adjvex; if(z!=x&&!is_adj(G,x,z)) return 0; }//for }//for }//Pass_ALGraph int is_adj(ALGraph G,int m,int n)//判断有向图 G 中是否存在边(m,n),是则返回 1, 否则返回 0 { for(p=G.vertices[m].firstarc;p;p=p->nextarc) if(p->adjvex==n) return 1; return 0; }//is_adj 7.22 int visited[MAXSIZE]; //指示顶点是否在当前路径上 int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图 G 中顶点 i 到顶点 j 是否有路径,是则返回 1,否则返回 0 { if(i==j) return 1; //i 就是 j else { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { k=p->adjvex; if(!visited[k]&&exist_path(k,j)) return 1;//i 下游的顶点到 j 有路径 }//for }//else }//exist_path_DFS 7.23 int exist_path_BFS(ALGraph G,int i,int j)//广度优先判断有向图 G 中顶点 i 到顶点 j 是否有路径,是则返回 1,否则返回 0 {
int visited MAXSIZE] InitQueue(Q) EnQueue(Q, 1) while(!Queue Empty(Q)) DeQueue(Q, u) sited=1 for(p=G vertices[i]. firstarc: p: p=p->nextarc) if(k-j return 1 if( visited [k] EnQueue(Q, k) i//for eturn 0 i/lexis BFS 724 void s traverse nonrecursive( Graph G∥非递归遍历强连通图G int visited MAXSIZe] Init Stack (S); Push( S Get vex(S,1),∥将第一个顶点入栈 Ⅴ isited=1 while(!Stack Empty(s)) while(gettop(s, I)&&i) First AdjVex(g, i) if(j&&!visited si(); visited Gll Push(Sj),∥向左走到尽头 i//while if(!StackEmpty(s)) Pop(sj) Gettop(s, 1) k= NextAdjVex(Gj)∥向右走一步 if(k&&!visited [kD)
int visited[MAXSIZE]; InitQueue(Q); EnQueue(Q,i); while(!QueueEmpty(Q)) { DeQueue(Q,u); visited[u]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { k=p->adjvex; if(k==j) return 1; if(!visited[k]) EnQueue(Q,k); }//for }//while return 0; }//exist_path_BFS 7.24 void STraverse_Nonrecursive(Graph G)//非递归遍历强连通图 G { int visited[MAXSIZE]; InitStack(S); Push(S,GetVex(S,1)); //将第一个顶点入栈 visit(1); visited =1; while(!StackEmpty(S)) { while(Gettop(S,i)&&i) { j=FirstAdjVex(G,i); if(j&&!visited[j]) { visit(j); visited[j]=1; Push(S,j); //向左走到尽头 } }//while if(!StackEmpty(S)) { Pop(S,j); Gettop(S,i); k=NextAdjVex(G,i,j); //向右走一步 if(k&&!visited[k]) {