有向图的简单路径.doc

#include<stdio.h>
#include<malloc.h>
typedefintInfoType;
#define MAXV100 //最大顶点个数
//以下定义邻接矩阵类型
typedefstruct
{ intno; //顶点编号
InfoTypeinfo; //顶点其他信息
}VertexType; //顶点类型
typedefstruct //图的定义
{ intedges[MAXV][MAXV]; //邻接矩阵
intvexnum,arcnum; //顶点数，弧数
VertexTypevexs[MAXV]; //存放顶点信息
}MGraph; //图的邻接矩阵类型
//以下定义邻接表类型
typedefstructANode //弧的结点结构类型
{ intadjvex; //该弧的终点位置
structANode*nextarc; //指向下一条弧的指针
InfoTypeinfo; //该弧的相关信息,这里用于存放权值
}ArcNode;
typedefintVertex;
typedefstructVnode //邻接表头结点的类型
{ Vertexdata; //顶点信息
ArcNode*firstarc; //指向第一条弧
}VNode;
typedefVNodeAdjList[MAXV]; //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;i<n;i++) //给邻接表中所有头结点的指针域置初值
G->adjlist[i].firstarc=NULL;
for(i=0;i<n;i++) //检查邻接矩阵中每个元素
for(j=n-1;j>=0;j--)
if(g.edges[i][j]!=0) //邻接矩阵的当前元素不为0
{
p=(ArcNode*)malloc(sizeof(ArcNode)); //创建一个结点*p
p->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;i<G->n;i++)
{
p=G->adjlist[i].firstarc;
if(p!=NULL)printf("%3d:",i);
while(p!=NULL)
{
printf("%3d",p->adjvex);
p=p->nextarc;
}
printf("\n");
}
}

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]);
printf("\n");
}
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的长度