欢迎来到天天文库
浏览记录
ID:15849782
大小:46.00 KB
页数:5页
时间:2018-08-06
《有向图的简单路径》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、#include#includetypedefintInfoType;#defineMAXV100//最大顶点个数//以下定义邻接矩阵类型typedefstruct{intno;//顶点编号InfoTypeinfo;//顶点其他信息}VertexType;//顶点类型typedefstruct//图的定义{intedges[MAXV][MAXV];//邻接矩阵intvexnum,arcnum;//顶点数,弧数VertexTypevexs[MAXV];//存放顶点信息}MGrap
2、h;//图的邻接矩阵类型//以下定义邻接表类型typedefstructANode//弧的结点结构类型{intadjvex;//该弧的终点位置structANode*nextarc;//指向下一条弧的指针InfoTypeinfo;//该弧的相关信息,这里用于存放权值}ArcNode;typedefintVertex;typedefstructVnode//邻接表头结点的类型{Vertexdata;//顶点信息ArcNode*firstarc;//指向第一条弧}VNode;typedefVNodeAdjList[MA
3、XV];//AdjList是邻接表类型typedefstruct{AdjListadjlist;//邻接表intn,e;//图中顶点数n和边数e}ALGraph;//图的邻接表类型intvisited[MAXV];//全局数组voidMatToList(MGraphg,ALGraph*&G)//将邻接矩阵g转换成邻接表G{inti,j,n=g.vexnum;//n为顶点数ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i4、点的指针域置初值G->adjlist[i].firstarc=NULL;for(i=0;i=0;j--)if(g.edges[i][j]!=0)//邻接矩阵的当前元素不为0{p=(ArcNode*)malloc(sizeof(ArcNode));//创建一个结点*pp->adjvex=j;p->info=g.edges[i][j];p->nextarc=G->adjlist[i].firstarc;//将*p链到链表后G->adjlist[i].fir5、starc=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!=NULL){printf("%3d",p->adjvex);p=p->nextarc;}printf("");}}voidPathAll1(ALGraph*G,intu,intv,intpath[]6、,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]);printf("");}elseif(visited[n]==0)//若该顶点未标记访问,则递归访问之{path[i+7、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;//将当前顶点添加到路径中if(u==v&&d==l)//输出一条8、路径{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(
4、点的指针域置初值G->adjlist[i].firstarc=NULL;for(i=0;i=0;j--)if(g.edges[i][j]!=0)//邻接矩阵的当前元素不为0{p=(ArcNode*)malloc(sizeof(ArcNode));//创建一个结点*pp->adjvex=j;p->info=g.edges[i][j];p->nextarc=G->adjlist[i].firstarc;//将*p链到链表后G->adjlist[i].fir
5、starc=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!=NULL){printf("%3d",p->adjvex);p=p->nextarc;}printf("");}}voidPathAll1(ALGraph*G,intu,intv,intpath[]
6、,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]);printf("");}elseif(visited[n]==0)//若该顶点未标记访问,则递归访问之{path[i+
7、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;//将当前顶点添加到路径中if(u==v&&d==l)//输出一条
8、路径{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(
此文档下载收益归作者所有