有向图的简单路径下载_Word模板_9

is_882336

暂无简介

有向图的简单路径有向图的简单路径 #include #include typedef int InfoType; #define MAXV 100 //最大顶点个数 //以下定义邻接矩阵类型 typedef struct { int no; //顶点编号 InfoType info; //顶点其他信息 } VertexType; //顶点类型 typedef struct //图的定义 { int edges[MAXV][MAXV]; //邻接矩阵 int vexnum,arcnum; //顶点数，弧数 Verte...

有向图的简单路径 #include #include typedef int InfoType; #define MAXV 100 //最大顶点个数 //以下定义邻接矩阵类型 typedef struct { int no; //顶点编号 InfoType info; //顶点其他信息 } VertexType; //顶点类型 typedef struct //图的定义 { int edges[MAXV][MAXV]; //邻接矩阵 int vexnum,arcnum; //顶点数，弧数 VertexType vexs[MAXV]; //存放顶点信息 } MGraph; //图的邻接矩阵类型 //以下定义邻接

表

关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf 视力表打印pdf 用图表说话 pdf

类型 typedef struct ANode //弧的结点结构类型 { int adjvex; //该弧的终点位置 struct ANode *nextarc; //指向下一条弧的指针 InfoType info; //该弧的相关信息,这里用于存放权值 } ArcNode; typedef int Vertex; typedef struct Vnode //邻接表头结点的类型 { Vertex data; //顶点信息 ArcNode *firstarc; //指向第一条弧 } VNode; typedef VNode AdjList[MAXV]; //AdjList是邻接表类型 typedef struct { AdjList adjlist; //邻接表 int n,e; //图中顶点数n和边数e } ALGraph; //图的邻接表类型 int visited[MAXV]; //全局数组 void MatToList(MGraph g,ALGraph *&G) //将邻接矩阵g转换成邻接表G { int i,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=(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; } void DispAdj(ALGraph *G) //输出邻接表G { int i; 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("\n"); } } void PathAll1(ALGraph *G,int u,int v,int path[],int i) //输出图G中从顶点u到v的所有简单路径 { ArcNode *p; int j,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"); } else if (visited[n]==0 ) //若该顶点未标记访问,则递归访问之 { path[i+1]=n; PathAll1(G,n,v,path,i+1); } p=p->nextarc; //找u的下一个邻接顶点 } visited[u]=0; } void PathAll2(ALGraph *G,int u,int v,int l,int path[],int d) //输出图G中从顶点u到v的长度为l的所有简单路径,d是到当前为止已走过的路径长度, 调用时初值为-1 { int m,i; ArcNode *p; visited[u]=1; d++; //路径长度增1 path[d]=u; //将当前顶点添加到路径中 if (u==v && d==l) //输出一条路径 { for (i=0;i<=d;i++) printf("%3d",path[i]); printf("\n"); } p=G->adjlist[u].firstarc; //p指向顶点u的第一条弧的弧头结点 while (p!=NULL) { m=p->adjvex; //m为u的邻接顶点 if (visited[m]==0) //若该顶点未标记访问,则递归访问之 PathAll2(G,m,v,l,path,d); p=p->nextarc; //找u的下一个邻接顶点 } visited[u]=0; //取消访问标记,以使该顶点可重新使用 d--; //回退时路径长度减1 } int ShortPath(ALGraph *G,int u,int v,int path[]) //求顶点u到顶点v(u?v)的最短路径 { struct { int vno; //当前顶点编号 int level; //当前顶点的层次 int parent; //当前顶点的当一个结点编号 } qu[MAXV]; //定义顺序非循环队列 int front=-1,rear=-1,k,lev,i,j; ArcNode *p; visited[u]=1; rear++; //顶点u已访问,将其入队 qu[rear].vno=u; qu[rear].level=0; qu[rear].parent=-1; while (frontadjlist[k].firstarc; //取k的边表头指针 while (p!=NULL) //依次搜索巧的邻接点 { if (visited[p->adjvex]==0) //若未访问过 { visited[p->adjvex]=1; rear++; qu[rear].vno=p->adjvex; //访问过的邻接点入队 qu[rear].level=lev+1; qu[rear].parent=front; } p=p->nextarc; //找顶点i的下一邻接点 } } return 0; //如果未找到顶点j,返回一特殊值0 } void main() { int i,j; int u=5,v=2,d=3; int path[MAXV]; MGraph g; ALGraph *G; int A[MAXV][6]={ {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;i

本文档为【有向图的简单路径】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。

历史搜索

清空历史搜索

有向图的简单路径

热门搜索

历史搜索