1、图的基本操作算法汇总B5讲解/图的基本操作算法/1.void CreatGraph (AdjList g) /建立有n个顶点和m 条边的无向图的邻接表存储结构 int n,m; scanf(%d%d,&n,&m); for(i =1,i=n;i+) /输入顶点信息,建立顶点向量 scanf(&gi.vertex); gi.firstarc=null; for(k=1;kadjvex=j; p-next=gi.firstarc; gi.firstarc=p; /将边结点链入 p=(ArcNode *)malloc(sizeof(ArcNode); /无向图双向连接 p-adjvex=i; p-n
2、ext=gj.firstarc; gj.firstarc=p; /算法CreatGraph结束/2.void CreatAdjList(AdjList g) /建立有向图的邻接表存储结构 int n; scanf(%d,&n); for (i=1;iadjvex=j; p-next=gi.firstarc; gi.firstarc=p; scanf(&v1,&v2); /5void InvertAdjList(AdjList gin,gout) /将有向图的出度邻接表改为按入度建立的逆邻接表 for(i=1;i=n;i+) /设有向图有n个顶点,建逆邻接表的顶点向量。 gini.vertex=
3、gouti.vertex; gin.firstarc=null; /逆邻接表 顶点初始化 for(i=1;iadjvex; / 邻接表边结点中的j顶点信息 s=(ArcNode *)malloc(sizeof(ArcNode); /申请逆邻接表的边结点空间 s-adjvex=i; /对逆邻接表的边结点 顶点信息赋值 s-next=ginj.firstarc; /对逆邻接表的边结点 下一边信息赋值 ginj.firstarc=s; / 边结点链入逆邻接表 p=p-next; / 邻接表中找下一个邻接点。 /while /for /6.void AdjListToAdjMatrix(AdjList
4、 gl, AdjMatrix gm) /将图的邻接表表示转换为邻接矩阵表示 for(i=1;i=n;i+) /设图有n个顶点,邻接矩阵初始化。 for(j=1;j=n;j+) gmij=0; for(i=1;iadjvex=1; p=p-next; /下一个邻接点 /for /算法结束/7.void AdjMatrixToAdjList( AdjMatrix gm, AdjList gl ) /图的邻接矩阵表示法转换为邻接表表示法 for(i=1;i=n;i+) /邻接表表头向量初始化。 scanf(&gli.vertex); gli.firstarc=null; for(i=1;i=n;i+
5、) for(j=1;jadjvex=j; /顶点i的邻接点是j p-next=gli.firstarc; /下一个邻接边结点 gli.firstarc=p; /链入顶点i的邻接点链表中 /end/算法讨论 算法中邻接表中顶点在向量表中的下标与其在邻接矩阵中的行号相同。/9.void DeletEdge(AdjList g,int i,j)/在用邻接表方式存储的无向图g中,删除边(i,j) p=gi.firstarc; pre=null; /删顶点i 的边结点(i,j),pre是前驱指针 while(p) if(p-adjvex=j) /找到了要删除的结点 if(pre=null) gi.fir
6、starc=p-next; /要删除的是第一个邻接点,重新设置第一邻接点 else pre-next=p-next; /要删除的不是第一邻接点 重新设置pre后链 跳过p 链上p-next free(p); /释放结点空间。 else pre=p; p=p-next; /没找到,沿链表继续查找 p=gj.firstarc; pre=null; /删顶点j 的边结点(j,i) while(p) if(p-adjvex=i) if(pre=null)gj.firstarc=p-next; else pre-next=p-next; free(p); /释放结点空间。 else pre=p; p=p
7、-next; /沿链表继续查找/ DeletEdge/算法讨论 算法中假定给的i,j 均存在,否则应检查其合法性。若未给顶点编号,而给出顶点信息,/则先用顶点定位函数求出其在邻接表顶点向量中的下标i和j。/10.void DeleteArc(AdjList g,vertype vi,vj)/删除以邻接表存储的有向图g的一条弧,假定顶点vi和vj存在 i=GraphLocateVertex(g,vi); j=GraphLocateVertex(g,vj); /顶点定位 p=gi.firstarc; pre=null; while(p) if(p-adjvex=j) if(pre=null) gi
8、.firstarc=p-next; else pre-next=p-next; free(p); /释放结点空间。 else pre=p; p=p-next; /结束 不用再查找j 比无向图省事/图的遍历算法/12.在有向图的邻接表中,求顶点的出度容易,只要简单在该顶点的邻接点链表中查结点个数即可。/而求顶点的入度,则要遍历整个邻接表。int count (AdjList g , int k )/在n个顶点以邻接表表示的有向图g中,求指定顶点k(1=k=n)的入度。 int count =0; for(i=1;iadjvex=k) count+; p=p-next; /while /if re
9、turn(count); /顶点k的入度./8.在有向图中,判断顶点Vi和顶点Vj间是否有路径,可采用遍历的方法,从顶点Vi出发,/不论是深度优先遍历(dfs)还是宽度优先遍历(bfs),在未退出dfs或bfs前,若访问到Vj,/则说明有通路,否则无通路。设一全程变量flag,初始化为0,若有通路,则flag=1。/算法1:int visited=0; /全局变量,访问数组初始化int dfs(AdjList g , vertype vi ,vj)/以邻接表为存储结构的有向图g,判断顶点Vi到Vj是否有通路,返回1或0表示有或无 visitedvi=1; /visited是访问数组,假设顶点的
10、信息就是顶点编号。 p=gvi.firstarc; /第一个邻接点。 while( p!=null) j=p-adjvex; if (j=vj) flag=1; return(1); /vi 和 vj 有通路。 if (visitedj=0) dfs(g,j,vj); /递归进行深度遍历 p=p-next; /遍历完返回,继续下一边 /while if(!flag) return(0); /最后没有通路 返回0/结束/算法讨论 若顶点vi和vj 不是编号,必须先用顶点定位函数,查出其在邻接表顶点向量中的下标i和j。/下面算法2输出vi 到 vj的路径,其思想是用一个栈存放遍历的顶点,遇到顶点v
11、j时输出路径。/算法2:void dfs(AdjList g , int i,j)/有向图g的顶点vi(编号i)和顶点vj(编号j)间是否有路径,如有,则输出。 int top=0, stack; /stack是存放顶点编号的栈 visitedi=1; /visited 数组在进入dfs前已初始化。 stack+top=i; p=gi.firstarc; /求第一个邻接弧结点. while(p) if(p-adjvex=j) /弧p的顶点即为j,遇到顶点vj 输出路径 stack+top=j; /顶点j入栈 printf( 顶点 vi 和 vj 的路径为:n); for(i=1; iadjve
12、x=0) /弧p的顶点p-adjvex尚未被访问 dfs(g,p-adjvex,j); top-; p=p-next; /递归进行深度遍历出栈 /while/结束算法2/算法3:本题用非递归算法求解。int Connectij (AdjList g , vertype vi , vj )/判断n个顶点以邻接表表示的有向图g中,顶点 Vi 各Vj 是否有路径,有则返回1,否则返回0。 for(i=1;i0) k=stacktop-; p=gk.firstarc; while(p!=null & visitedp-adjvex=1) p=p-next; /查第k个链表中第一个未访问的弧结点。 if
13、(p=null) top-; else i=p-adjvex; if(i=j) return(1);/顶点vi和vj 间有路径。 else visitedi=1; stack+top=i; /else /else /while return(0);/顶点vi和vj 间无通路。/13.有向图判断回路要比无向图复杂。利用深度优先遍历,将顶点分成三类:未访问;/已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用0,1,2表示这三种状态。/前面已提到,若dfs(v)结束前出现顶点u到v的回边,则图中必有包含顶点v和u的回路。/对应程序中v的状态为1,而u是正访问的顶点,若我们找出u的下一邻接点
14、的状态为1,就可以输出回路了。void Print(int v,int start ) /输出从顶点start开始的回路。 for(i=1;i=n;i+) if(gvi!=0 & visitedi=1 ) /若存在边(v,i),且顶点i的状态为1。 printf(%d,v); if(i=start) printf(n); else Print(i,start);/递归 break; /Printvoid dfs(int v) visitedv=1; /0:未访问;1:已访问但其邻接点未访问完; 2:已访问且其邻接点已访问完 for(j=1;j=n;j+ ) if (gvj!=0) /存在边(v
15、,j) if (visitedj!=1) /0:未访问 或 2:已访问且其邻接点已访问完 if(!visitedj) dfs(j); /0:未访问j未访问 深度遍历j else cycle=1; Print(j,j); / 1:已访问且其邻接点未访问完 visitedv=2; /访问v完成 2:已访问且其邻接点已访问完/dfsvoid find_cycle() /判断是否有回路,有则输出邻接矩阵。visited数组为全局变量。 for(i=1;i=n;i+) visitedi=0; for(i=1;iadjvex=0) dfs(p-adjvex); /未访问 递归深度遍历 p=p-next;
16、/while visitedv=0; num-; /恢复顶点v 全局变量重新计数 便于后边遍历/dfsvoid JudgeRoot() /判断有向图是否有根,有根则输出之。 static int i ; for(i=1;iadjvex=0) dfs(p-adjvex); /深度递归访问 p=p-next; /while/ dfsvoid Count() /深度优先遍历求图中连通分量的个数 int k=0; static AdjList g ; /设无向图g有n个结点 for(i=1;iadjvex=0) /第一个邻接点未访问 printf(%3d,p-adjvex); visitedp-adj
17、vex=1; QueueIn(Q,p-adjvex); /if /访问入队 p=p-next; /下一个邻接边结点 即广度优先 /while / while (!QueueEmpty(Q)/bfs void BFSCOM() /广度优先搜索,求无向图的连通分量。 int count=0; /记连通分量个数。 for (i=1;i=n;i+) visitedi=0; for (i=1;i=n;i+) if (visitedi=0) printf(n第%d个连通分量:n,+count); bfs(i); /if/BFSCOM/27.D_搜索类似BFS,只是用栈代替队列,入出队列改为入出栈。/查某顶
18、点的邻接点时,若其邻接点尚未遍历,则遍历之,并将其压入栈中。/当一个顶点的所有邻接点被搜索后,栈顶顶点是下一个搜索出发点。void D_BFS(AdjList g ,vertype v0) / 从v0顶点开始,对以邻接表为存储结构的图g进行D_搜索。 int s, top=0; /栈,栈中元素为顶点,仍假定顶点用编号表示。 for(i=1,i=n;i+) visitedi=0; /图有n个顶点,visited数组为全局变量 初始化 for(i=1,i0) i=stop-; /退栈,准备找邻接点 p=gi.firstarc; /取第一个邻接边结点 while(p!=null) /处理顶点的所有邻
19、接边结点 j=p-adjvex; /邻接点 if(visitedj=0) /未访问的邻接点 visitedj=1; printf( %3d,i); s+top=j; /访问并入栈 p=p-next; /广度优先遍历 /下一个邻接点 /while(top0) /if/D_BFS/20.void Traver(AdjList g,vertype v)/图g以邻接表为存储结构,算法从顶点v开始实现非递归深度优先遍历。 struct arc *stack; visitedv=1; printf(v); /输出顶点v top=0; p=gv.firstarc; stack+top=p; while(top0 | p!=null) while(p) if( p & visitedp-adjvex) p=p-
