有向图的简单路径

《有向图的简单路径》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#include#includetypedefintInfoType;#defineMAXV100//最大顶点个数//以下定义邻接矩阵类型typedefstruct{intno;//顶点编号InfoTypeinfo;//顶点其他信息}VertexType;//顶点类型typedefstruct//图的定义{intedges[MAXV][MAXV];//邻接矩阵intvexnum,arcnum;//顶点数，弧数VertexTypevexs[MAXV];//存放顶点信息}MGraph;//图的邻接矩阵类型//以下定义邻接表类型typedefstructANod

2、e//弧的结点结构类型{intadjvex;//该弧的终点位置structANode*nextarc;//指向下一条弧的指针InfoTypeinfo;//该弧的相关信息,这里用于存放权值}ArcNode;typedefintVertex;typedefstructVnode//邻接表头结点的类型{Vertexdata;//顶点信息ArcNode*firstarc;//指向第一条弧}VNode;typedefVNodeAdjList[MAXV];//AdjList是邻接表类型typedefstruct{AdjListadjlist;//邻接表intn,e;//图中顶点数n和边数e}ALGraph

3、;//图的邻接表类型intvisited[MAXV];//全局数组voidMatToList(MGraphg,ALGraph*&G)//将邻接矩阵g转换成邻接表G{inti,j,n=g.vexnum;//n为顶点数ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;iadjlist[i].firstarc=NULL;for(i=0;i=0;j--)if(g.edges[i][j]!=0)//邻接矩阵的当前元素不为0{p

4、=(ArcNode*)malloc(sizeof(ArcNode));//创建一个结点*pp->adjvex=j;p->info=g.edges[i][j];p->nextarc=G->adjlist[i].firstarc;//将*p链到链表后G->adjlist[i].firstarc=p;}G->n=n;G->e=g.arcnum;}voidDispAdj(ALGraph*G)//输出邻接表G{inti;ArcNode*p;for(i=0;in;i++){p=G->adjlist[i].firstarc;if(p!=NULL)printf("%3d:",i);while(p!=N

5、ULL){printf("%3d",p->adjvex);p=p->nextarc;}printf("");}}voidPathAll1(ALGraph*G,intu,intv,intpath[],inti)//输出图G中从顶点u到v的所有简单路径{ArcNode*p;intj,n;visited[u]=1;p=G->adjlist[u].firstarc;//p指向顶点m的第一条弧的弧头结点while(p!=NULL){n=p->adjvex;//n为m的邻接顶点if(n==v){path[i+1]=v;for(j=0;j<=i+1;j++)printf("%3d",path[j]);p

6、rintf("");}elseif(visited[n]==0)//若该顶点未标记访问,则递归访问之{path[i+1]=n;PathAll1(G,n,v,path,i+1);}p=p->nextarc;//找u的下一个邻接顶点}visited[u]=0;}voidPathAll2(ALGraph*G,intu,intv,intl,intpath[],intd)//输出图G中从顶点u到v的长度为l的所有简单路径,d是到当前为止已走过的路径长度,调用时初值为-1{intm,i;ArcNode*p;visited[u]=1;d++;//路径长度增1path[d]=u;//将当前顶点添加到路径中

7、if(u==v&&d==l)//输出一条路径{for(i=0;i<=d;i++)printf("%3d",path[i]);printf("");}p=G->adjlist[u].firstarc;//p指向顶点u的第一条弧的弧头结点while(p!=NULL){m=p->adjvex;//m为u的邻接顶点if(visited[m]==0)//若该顶点未标记访问,则递归访问之PathAll2(