有向图的简单路径.doc

#include #include typedef int InfoType;#defineMAXV 100/最大顶点个数/以下定义邻接矩阵类型typedef struct int no;/顶点编号InfoType info;/顶点其他信息 VertexType;/顶点类型typedef struct /图的定义 int edgesMAXVMAXV; /邻接矩阵int vexnum,arcnum; /顶点数，弧数VertexType vexsMAXV;/存放顶点信息 MGraph;/图的邻接矩阵类型/以下定义邻接表类型typedef struct ANode /弧的结点结构类型int adjvex; /该弧的终点位置struct ANode *nextarc; /指向下一条弧的指针InfoType info; /该弧的相关信息,这里用于存放权值 ArcNode;typedef int Vertex;typedef struct Vnode /邻接表头结点的类型Vertex data; /顶点信息ArcNode *firstarc; /指向第一条弧 VNode;typedef VNode AdjListMAXV;/AdjList是邻接表类型typedef struct AdjList adjlist; /邻接表int n,e; /图中顶点数n和边数e ALGraph; /图的邻接表类型int visitedMAXV;/全局数组void MatToList(MGraph g,ALGraph *&G)/将邻接矩阵g转换成邻接表Gint i,j,n=g.vexnum;/n为顶点数ArcNode *p;G=(ALGraph *)malloc(sizeof(ALGraph);for (i=0;iadjlisti.firstarc=NULL;for (i=0;i=0;j-)if (g.edgesij!=0)/邻接矩阵的当前元素不为0 p=(ArcNode *)malloc(sizeof(ArcNode);/创建一个结点*pp-adjvex=j;p-info=g.edgesij;p-nextarc=G-adjlisti.firstarc;/将*p链到链表后G-adjlisti.firstarc=p;G-n=n;G-e=g.arcnum;void DispAdj(ALGraph *G)/输出邻接表Gint i;ArcNode *p;for (i=0;in;i+)p=G-adjlisti.firstarc;if (p!=NULL) printf(%3d: ,i);while (p!=NULL)printf(%3d,p-adjvex);p=p-nextarc;printf(n);void PathAll1(ALGraph *G,int u,int v,int path,int i)/输出图G中从顶点u到v的所有简单路径ArcNode *p;int j,n;visitedu=1;p=G-adjlistu.firstarc; /p指向顶点m的第一条弧的弧头结点while (p!=NULL)n=p-adjvex;/n为m的邻接顶点if (n=v)pathi+1=v;for (j=0;jnextarc;/找u的下一个邻接顶点visitedu=0;void PathAll2(ALGraph *G,int u,int v,int l,int path,int d)/输出图G中从顶点u到v的长度为l的所有简单路径,d是到当前为止已走过的路径长度,调用时初值为-1int m,i;ArcNode *p;visitedu=1;d+;/路径长度增1pathd=u;/将当前顶点添加到路径中if (u=v & d=l)/输出一条路径for (i=0;iadjlistu.firstarc; /p指向顶点u的第一条弧的弧头结点while (p!=NULL)m=p-adjvex;/m为u的邻接顶点if (visitedm=0)/若该顶点未标记访问,则递归访问之PathAll2(G,m,v,l,path,d);p=p-nextarc;/找u的下一个邻接顶点visitedu=0;/取消访问标记,以使该顶点可重新使用d-;/回退时路径长度减1int ShortPath(ALGraph *G,int u,int v,int path)/求顶点u到顶点v(uv)的最短路径struct int vno;/当前顶点编号int level;/当前顶点的层次int parent;/当前顶点的当一个结点编号 quMAXV;/定义顺序非循环队列int front=-1,rear=-1,k,lev,i,j;ArcNode *p;visitedu=1;rear+;/顶点u已访问,将其入队qurear.vno=u;qurear.level=0;qurear.parent=-1;while (frontadjlistk.firstarc;/取k的边表头指针 while (p!=NULL) /依次搜索巧的邻接点if (visitedp-adjvex=0) /若未访问过visitedp-adjvex=1;rear+;qurear.vno=p-adjvex;/访问过的邻接点入队qurear.level=lev+1;qurear.parent=front;p=p-nextarc;/找顶点i的下一邻接点return 0; /如果未找到顶点j,返回一特殊值0void main() int i,j;int u=5,v=2,d=3;int pathMAXV;MGraph g;ALGraph *G;int AMAXV6=0,1,0,1,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,1,0,0,1,0,0,0,1,0,0,1,1,0,1,1,0;g.vexnum=6;g.arcnum=10;for (i=0;ig.vexnum;i+)/建立图9.6的邻接矩阵for (j=0;jg.vexnum;j+)g.edgesij=Aij;G=(ALGraph *)malloc(sizeof(ALGraph);MatToList(g,G);/图G的邻接矩阵转换成邻接表printf(图G的邻接表:n);DispAdj(G);printf(n);for (i=0;ig.vexnum;i+) visitedi=0;printf(从%d到%d的所有路径:n,u,v);path0=u;visitedu=1;PathAll1(G,u,v,path,0);printf(n);printf(从%d到%d的所有长度为%d路径:n,u,v,d);PathAll2(G,u,v,d,path,-1);printf(n);for (i=0;ig.vex