输入有向图的顶点数

输入有向图的顶点数 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 1/31 Computer Department 计算机系 第六章 图 1、输入有向图的顶点数,边数,顶点信息和边的信息建立邻接。 Status Build_AdjList(ALGraph &G) { InitALGraph(G); scanf("%d",&v); if(v < 0) { return ERROR; /*顶点数不能为负*/ } G.vexnum = v; scanf("%d",&a); if(a < 0) { return ERROR; /*边数不能为负*/ } G.arcnum = a; for(m=0;m < v;++m) { G.vertices[m].data = getchar(); /*输入各顶点的符号*/ } for(m=1;m <= a;++m) { 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 2/31 Computer Department 计算机系 t = getchar(); /*t为弧尾*/ h = getchar(); /*t为弧尾,h为弧头*/ if((i = LocateVex(G,t)) < 0) { return ERROR; } if((j = LocateVex(G,h)) < 0) { return ERROR; /*顶点未找到*/ } p = (ArcNode* )malloc(sizeof(ArcNode)); if(!G.vertices.[i].firstarc) { G.vertices[i].firstarc = p; } else { for(q = G.vertices[i].firstarc;q->nextarc;q = q->nextarc); q->nextarc = p; } p->adjvex = j; p->nextarc = NULL; } 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 3/31 Computer Department 计算机系 return OK; } /*Build_AdjList*/ 2、在邻接矩阵表示的图G上插入顶点v。 Status Insert_Vex(MGraph &G, char v) { if(G.vexnum+1) > MAX_VERTEX_NUM ) { return INFEASIBLE; } G.vexs[++G.vexnum] = v; return OK; }/*Insert_Vex*/ 3、在邻接矩阵表示的图G上插入边(v,w)。 Status Insert_Arc(MGraph &G,char v,char w) { if((i = LocateVex(G,v)) < 0) { return ERROR; } if((j = LocateVex(G,w)) < 0) { return ERROR; } 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 4/31 Computer Department 计算机系 if(i == j) { return ERROR; } if(!G.arcs[i][j].adj) { G.arcs[i][j].adj = 1; ++G.arcnum; } return OK; }/*Insert_Arc*/ 4、在邻接矩阵表示的图G上删除顶点v。 Status Delete_Vex(MGraph &G,char v) { n = G.vexnum; if((m = LocateVex(G,v)) < 0) { return ERROR; } G.vexs[m]<->G.vexs[n]; /*将待删除顶点交换到最后一个顶点*/ for(i = 0;i < n;++i) { G.arcs[i][m] = G.arcs[i][n]; 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 5/31 Computer Department 计算机系 G.arcs[m][i] = G.arcs[n][i]; /*将边的关系随之交换*/ } G.arcs[m][m].adj = 0; --G.vexnum; return OK; }/*Delete_Vex*/ 5、在邻接矩阵表示的图G上删除边(v,w)。 Status Delete_Arc(MGraph &G,char v,char w) { if((i = LocateVex(G,v)) < 0) { return ERROR; } if((j = LocateVex(G,w)) < 0) { return ERROR; } if(G.arcs[i][j].adj) { G.arcs[i][j].adj = 0; --G.arcnum; } return OK; 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 6/31 Computer Department 计算机系 }/*Delete_Arc*/ 6、在邻接表表示的图G上插入边(v,w)。 Status Insert_Arc(ALGraph &G,char v,char w) { if((i = LocateVex(G,v)) < 0) { return ERROR; } if((j = LocateVex(G,w)) < 0) { return ERROR; } p=(ArcNode * )malloc(sizeof(ArcNode)); p->adjvex = j; p->nextarc = NULL; if(!G.vertices[i].firstarc) { G.vertices[i].firstarc = p; } else { for(q = G.vertices[i].firstarc;q->q->nextarc;q = q->nextarc) if(q->adjvex == j) 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 7/31 Computer Department 计算机系 { return ERROR; /*边已经存在*/ } q->nextarc = p; } ++G.arcnum; return OK; }/*Insert_Arc*/ 7、在十字链表表示的图G上删除顶点v。 Status Delete_Vex(OLGraph &G,char v) { if((m = LocateVex(G,v)) < 0) { return ERROR; } n = G.vexnum; for(i = 0;i< n;++i) /*删除所有以v为头的边 { if(G.xlist[i].firstin->tailvex == m) /*如果待删除的边是头链上的第一个结点*/ { q = G.xlist[i].firstin; G.xlist[i].firstin = q->hlink; free(q); 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 8/31 Computer Department 计算机系 --G.arcnum; } else /*否则*/ { for(p = G.xlist[i].firstin;(p && p->hlink->tailvex) != m;p = p->hlink); if(p) { q = p->hlink; p->hlink = q->hlink; free(q); --G.arcnum; } }/*else*/ }/*for*/ for(i = 0;i < n; ++i) /*删除所有以v为尾的边*/ { if(G.xlist[i].firstout->headvex == m) /*若待删除的边是尾链上的第一个结点*/ { q = G.xlist[i].firstout; G.xlist[i].firstout = q->tlink; free(q); G.arcnum--; } 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 9/31 Computer Department 计算机系 else /*否则 { for(p = G.xlist[i].firstout; (p && p->tlink->headvex) != m;p = p->tlink); if(p) { q = p->tlink; p->tlink = q->tlink; free(q); G.arcnum; -- } }/*else*/ }/*for*/ for(i = m;i< n;++i) /*顺次用结点m之后的顶点取代前一个顶点*/ { G.xlist[i] = G.xlist[i+1]; /*修改表头向量*/ for(p = G.xlist[i].firstin;p;p = p->hlink) { p->headvex--; } for(p = G.xlist[i].firstout;p;p = p->tlink) { p->tailvex--; /*修改各链中的顶点序号*/ } 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 10/31 Computer Department 计算机系 } --G.vexnum; return OK; }/*Delete_Vex*/ 8、在邻接多重表表示的图G上删除边(v,w)。 Status Delete_Arc(AMLGraph &G,char v,char w) { if((i = LocateVex(G,v)) < 0) { return ERROR; } if((j = LocateVex(G,w)) < 0) { return ERROR; } if(G.adjmulist[i].firstedge->jvex == j) { G.adjmulist[i].firstedge = G.adjmulist[i].firstedge->ilink; } else { for(p = G.adjmulist[i].firstedge;(p && p->ilink->jvex) != j;p = p->ilink); if (!p) 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 11/31 Computer Department 计算机系 { return ERROR; /*未找到*/ } p->ilink = p->ilink->ilink; } /*在i链表中删除该边*/ if(G.adjmulist[j].firstedge->ivex == i) { G.adjmulist[j].firstedge = G.adjmulist[j].firstedge->jlink; } else { for(p = G.adjmulist[j].firstedge;(p && p->jlink->ivex)!= i;p = p->jlink); if (!p) { return ERROR; /*未找到*/ } q = p->jlink; p->jlink = q->jlink; free(q); } /*在i链表中删除该边*/ --G.arcnum; return OK; }/*Delete_Arc*/ 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 12/31 Computer Department 计算机系 9、输入有向图的顶点数,边数,顶点信息和边的信息建立邻接多重表。 Status Build_AdjMulist(AMLGraph &G) { InitAMLGraph(G); scanf("%d",&v); if(v<0) { return ERROR; /*顶点数不能为负*/ } G.vexnum = v; scanf(%d",&a); if(a < 0) { return ERROR; /*边数不能为负*/ } G.arcnum = a; for(m = 0;m < v;++m) { G.adjmulist[m].data = getchar(); /*输入各顶点的符号*/ } for(m = 1;m <= a;++m) { t = getchar(); 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 13/31 Computer Department 计算机系 h = getchar(); /*t为弧尾,h为弧头*/ if((i = LocateVex(G,t)) < 0) { return ERROR; } if((j = LocateVex(G,h)) < 0) { return ERROR; /*顶点未找到*/ } p= (EBox* )malloc(sizeof(EBox)); p->ivex = i; p->jvex = j; p->ilink = NULL; p->jlink = NULL; /*边结点赋初值*/ if(!G.adjmulist[i].firstedge) G.adjmulist[i].firstedge = p; else { q = G.adjmulist[i].firstedge; while(q) { r = q; if(q->ivex == i) { 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 14/31 Computer Department 计算机系 q = q->ilink; } else { q = q->jlink; } } if(r->ivex == i) { ->ilink == p;/*注意i值既可能出现在边结点的ivex域中*/r } else { r->jlink = p; /*又可能出现在边结点的jvex域中*/ } }/*else插入i链表尾部*/ if(!G.adjmulist[j].firstedge) { p; G.adjmulist[j].firstedge = } else { q = G.adjmulist[i].firstedge; 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 15/31 Computer Department 计算机系 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; } }/**插入j链表尾部*/ }/*for*/ return OK; 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 16/31 Computer Department 计算机系 }/*Build_AdjList*/ 10、判断一个邻接矩阵存储的有向图是不是可传递的,是则返回1,否则返回0。 int Pass_MGraph(MGraph G) { 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*/ 11、判断一个邻接表存储的有向图是不是可传递的,是则返回1,否则返回0。 int Pass_ALGraph(ALGraph G) { for(x = 0;x < G.vexnum; ++x) for(p = G.vertices[x].firstarc;p;p = p->nextarc) 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 17/31 Computer Department 计算机系 { 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*/ 12、判断有向图G中是否存在边(m,n),是则返回1,否则返回0。 int is_adj(ALGraph G,int m,int n) { for(p = G.vertices[m].firstarc;p;p = p->nextarc) { if(p->adjvex == n) { return 1; } } return 0; 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 18/31 Computer Department 计算机系 }/*is_adj*/ 13、深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0。 int visited[MAXSIZE]; /*指示顶点是否在当前路径 int exist_path_DFS(ALGraph G,int i,int j) { 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 */ 14、广度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0。 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 19/31 Computer Department 计算机系 int exist_path_BFS(ALGraph G,int i,int j) { 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; 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 20/31 Computer Department 计算机系 }/*exist_path_BFS */ 15、非递归遍历强连通图G。 void STraverse_Nonrecursive(Graph 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)) { 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 21/31 Computer Department 计算机系 Pop(S,j); Gettop(S,i); k = NextAdjVex(G,i,j); /*向右走一步*/ if(k && !visited[k]) { visit(k); visited[k] = 1; Push(S,k); } }/*if*/ }/*while*/ }/*Straverse_Nonrecursive*/ 16、判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径。 int visited[MAXSIZE]; int exist_path_len(ALGraph G,int i,int j,int k) { if(i == j && k == 0) { return 1; /*找到了一条路径,且长度符合要求*/ } else if(k > 0) { visited[i] = 1; 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 22/31 Computer Department 计算机系 for(p = G.vertices[i].firstarc;p;p = p->nextarc) { l = p->adjvex; if(!visited[l]) { if(exist_path_len(G,l,j,k-1)) { return 1; /*剩余路径长度减一*/ } } }/*for*/ visited[i] = 0; /*本题允许曾经被访问过的结点出现在另一条路径中*/ }/*else*/ return 0; /*没找到 }/*exist_path_len*/ 17、求有向图G中顶点u到v之间的所有简单路径,k表示当前路径长度。 int path[MAXSIZE]; int visited[MAXSIZE]; /*暂存遍历过程中的路径*/ int Find_All_Path(ALGraph G,int u,int v,int k) { path[k] = u; /*加入当前路径中 visited[u] = 1; if(u == v) /*找到了一条简单路径 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 23/31 Computer Department 计算机系 { printf("Found one path!\n"); for(i = 0;path[i]; ++i) { printf("%d",path[i]); /*打印输出*/ } } else for(p = G.vertices[u].firstarc;p;p = p->nextarc) { l = p->adjvex; if(!visited[l]) { Find_All_Path(G,l,v,k+1); /*继续寻找 } } visited[u] = 0; path[k] = 0; /*回溯*/ }/*Find_All_Path */ main() { ... Find_All_Path(G,u,v,0); /*在主函数中初次调用,k值应为0*/ 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 24/31 Computer Department 计算机系 ... }/*main*/ 18、求邻接表方式存储的有向图G的顶点i到j之间长度为len的简单路径条数。 int GetPathNum_Len(ALGraph G,int i,int j,int len) { if(i == j && len == 0) { return 1; /*找到了一条路径,且长度符合要求*/ } else if(len>0) { sum = 0; /*sum表示通过本结点的路径数*/ visited[i] = 1; for(p = G.vertices[i].firstarc;p;p = p->nextarc) { l = p->adjvex; if(!visited[l]) sum + =GetPathNum_Len(G,l,j,len-1)/*剩余路径长度减一*/ }/*for*/ visited[i] = 0; /*本题允许曾经被访问过的结点出现在另一条路径中*/ }/*else*/ return sum; }/*GetPathNum_Len*/ 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 25/31 Computer Department 计算机系 19、求有向图中所有的简单回路。 int visited[MAXSIZE]; int path[MAXSIZE]; /*暂存当前路径*/ int cycles[MAXSIZE][MAXSIZE]; /*储存发现的回路所包含的结点*/ int thiscycle[MAXSIZE]; /*储存当前发现的一个回路*/ int cycount = 0; /*已发现的回路个数*/ void GetAllCycle(ALGraph G) { for(v = 0;v < G.vexnum;++v) { visited[v] = 0; } for(v = 0;v < G.vexnum;++v) { if(!visited[v]) { DFS(G,v,0); /*深度优先遍历*/ } } }/*DFSTraverse*/ void DFS(ALGraph G,int v,int k)/*k表示当前结点在路径上的序号*/ { visited[v] = 1; 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 26/31 Computer Department 计算机系 path[k] = v; /*当前路径*/ for(p = G.vertices[v].firstarc;p;p = p->nextarc) { w = p->adjvex; if(!visited[w]) { DFS(G,w,k+1); } else /*发现了一条回路*/ { for(i = 0;path[i] != w;++i); /*找到回路的起点*/ for(j = 0;path[i+j];++i) { thiscycle[j] = path[i+j];/*把回路复制下来*/ } if(!exist_cycle()) { cycles[cycount++] = thiscycle; /*若该回路尚未被记录过,就添加到记录中*/ } for(i = 0;i < G.vexnum;++i) { thiscycle[i]=0; /*清空目前回路数组*/ 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 27/31 Computer Department 计算机系 } }/*else*/ }/*for*/ path[k] = 0; visited[k] = 0; /*注意只有当前路径上的结点visited为真.因此一旦遍历中发现当前 结点visited为真,即表示发现了一条回路*/ }/*DFS*/ int exist_cycle()/*判断thiscycle数组中记录的回路在cycles的记录中是否已经存在 { int temp[MAXSIZE]; for(i = 0;i < cycount;++i) /*判断已有的回路与thiscycle是否相同*/ { /*也就是,所有结点和它们的顺序都相同*/ j = 0; c = thiscycle &# 0;; /*例如,142857和857142是相同的回路*/ for(k = 0;cycles[i][k] != c && cycles[i][k] != 0;++k);/*在cycles的一个行向 量中寻找等于thiscycle第一个结点的元素*/ if(cycles[i][k]) /*有与之相同的一个元素*/ { for(m = 0;cycles[i][k+m];++m) { temp[m] = cycles[i][k+m]; } for(n = 0;n < k;++n,++m) { 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 28/31 Computer Department 计算机系 temp[m] = cycles[i][n]; /*调整cycles中的当前记录的循环相位并放入temp数组中*/ } if(!StrCompare(temp,thiscycle)) /*与thiscycle比较*/ { return 1; /*完全相等*/ } for(m = 0;m < G.vexnum;++m) { temp[m] = 0; /*清空这个数组 } } }/*for*/ return 0; /*所有现存回路都不与thiscycle完全相等*/ }/*exist_cycle*/ 分析:这个算法的是,在遍历中暂存当前路径,当遇到一个结点已经在路径之中时就表明存在一条回路;扫描路径向量path可以获得这条回路上的所有结点.把结点序列(例如,142857)存入thiscycle中;由于这种算法中,一条回路会被发现好几次,所以必须先判断该回路是否已经在cycles中被记录过,如果没有才能存入cycles的一个行向量中.把cycles的每一个行向量取出来与之比较.由于一条回路可能有多种存储顺序,比如142857等同于285714和571428,所以还要调整行向量的次序,并存入temp数组,例如,thiscycle为142857第一个结点为1,cycles的当前向量为857142,则找到后者中的1,把1后部分提到1前部分前面,最终在temp中得到142857,与thiscycle比较,发现相同,因此142857和857142是同一条回路,不予存储.这个算法太复杂,很难保证细节的准确性,大家理解思路便可.希望有人给出更加简捷的算法. 20、求十字链表结构储存的有向图G的强连通分量。 int visited[MAXSIZE]; int finished[MAXSIZE]; 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 29/31 Computer Department 计算机系 int count; /*count在第一次深度优先遍历中用于指示finished数组的填充位置*/ void Get_SGraph(OLGraph G) { count = 0; for(v = 0;v< G.vexnum; ++v) { visited[v] = 0; } for(v = 0;v< G.vexnum;++v) /*第一次深度优先遍历建立finished数组*/ { if(!visited[v]) { DFS1(G,v); } } for(v = 0;v < G.vexnum;++v) { visited[v] = 0; /*清空visited数组*/ } for(i = G.vexnum-1;i >= 0;--i) /*第二次逆向的深度优先遍历*/ { v = finished(i); if(!visited[v]) 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 30/31 Computer Department 计算机系 { printf("\n"); /*不同的强连通分量在不同的行输出*/ DFS2(G,v); } }/*for*/ }/*Get_SGraph */ void DFS1(OLGraph G,int v)/*第一次深度优先遍历的算法*/ { visited[v] = 1; for(p = G.xlist[v].firstout;p;p = p->tlink) { w = p->headvex; if(!visited[w]) { DFS1(G,w); } }/*for*/ finished[++count] = v; /*在第一次遍历中建立finished数组*/ }/*DFS1*/ void DFS2(OLGraph G,int v)/*第二次逆向的深度优先遍历的算法*/ { visited[v] = 1; printf("%d",v); /*在第二次遍历中输出结点序号*/ 第六章 图 成都东软信息技术学院 段恩泽 2013-04-16 31/31 Computer Department 计算机系 for(p = G.xlist[v].firstin;p;p = p->hlink) { w = p->tailvex; if(!visited[w]) { DFS2(G,w); } }/*for*/ }/*DFS2*/ 分析:求有向图的强连通分量的算法的时间复杂度和深度优先遍历相同 ,也为O(n+e)。