当前位置:文档之家› 作业4图 参考答案

作业4图 参考答案

作业4. 图非编程作业参考答案:1.已知带权无向图如图所示:(1). 根据普里姆(Prim)算法,求它的从顶点a出发的最小生成树(写出过程,即添加顶点、边次序);(2). 根据克鲁斯卡尔(Kruskal)算法,求该图的最小生成树(写出过程,即添加边次序)。

普里姆(Prim)算法:aadaed2aced23acbed1234234克鲁斯卡尔(Kruskal)算法:acbedacbed1acbed12acbed123acbed12342. 已知带权有向图如图所示:(1). 画出该图的邻接矩阵存储结构;(2). 请写出该图的一个拓扑有序序列;(3). 求从顶点a到其余各顶点之间的最短路经及最短路经长度,并给出计算过程。

图G的一个拓扑序列:abdfecgh afbdecghabdfegch afbdegch2421∞∞∞⎢∞∞g02690301050280730∞∞∞∞⎡⎤⎢⎥∞∞∞∞∞⎢⎥⎢⎥∞∞∞∞∞∞⎢⎥∞∞∞∞∞∞⎢⎥⎢⎥∞∞∞∞∞⎢⎥∞∞⎥⎢⎥∞∞∞∞∞⎢⎥∞∞∞∞∞∞⎢⎥⎣⎦a b c d e f g habcdefh从a出发到其它顶点的最短路径及其计算过程:编程作业:请编写一个完整的程序,建立有向图的邻接表存储结构,并判断两顶点间是否有路径存在,要求:(1) 主函数功能:①从键盘读入有向图的顶点数、有向边数,调用函数CreateAdjList()建立邻接表;②在主函数中输出每个顶点的数据域及其所有邻接点;③从键盘读入两个顶点vs 、v t(ts )的数据域,调用函数Path()判断其间是否存在路径;(2) CreateAdjList():建立有向图邻接表。

功能:从键盘接收各顶点数据域及各条有向边所依附的顶点(如:“2,3”代表该边依附的两个顶点在表头数组中的下标为2和3),要求单链表中结点按数据域升序排序;(3) Path(): 判断两顶点间是否存在路径,如果存在,将打印该路径(若存在多条路径,打印其中一条即可)。

例:输入:请输入顶点和边的数目:8,9 //(在main()函数中输入) 请输入各顶点数据域:a b c d e f g h//(在CreateAdjList()中输入) 请输入各条边:1,21,32,43,63,74,85,25,86,7输出:图的邻接表为:a 2 3 //(在main()函数中输出)b 4c 6 7d 8e 2 8f 7gh输入:请输入要查找是否存在路径的顶点:a,h输出:顶点a和d之间存在路径,路经为:a b d h输入:请输入要查找是否存在路径的顶点:a,e输出:顶点a和e之间不存在路径参考答案:#include<stdio.h>#include<malloc.h>#define Max_Vertex_Num 10typedef char VertexType;int visited[Max_Vertex_Num];int visitpath[Max_Vertex_Num];int pathvexnum;int flag;//单链表结点(弧结点)typedef struct Arcnode{ int adjvex; //该弧所指向顶点(在表头数组中)的位置struct Arcnode *nextarc; //指向依附该顶点下一条边或弧} ArcNode;//头结点typedef struct Vnode{ VertexType data; //顶点信息Arcnode *firstarc; //指向第一条依附该顶点的弧 } VNode, AdjList[Max_Vertex_Num];//图的定义typedef struct{ AdjList vertices; // 表头数组int vexnum, arcnum; // 图中顶点及弧的数目} ALGraph;//建立邻接表void CreateAdjList (ALGraph &G){int k,i,j;ArcNode *p,*q,*s;for(k=1;k<=G.vexnum;k++){printf("input data:");fflush(stdin);scanf("%c",&G.vertices[k].data);G.vertices[k].firstarc=NULL;}for(k=0;k<G.arcnum;k++){printf("请输入边的两顶点:");scanf("%d,%d",&i,&j);s=(ArcNode *)malloc(sizeof(ArcNode));s->adjvex=j;s->nextarc=NULL;q=NULL;p=G.vertices[i].firstarc;while((p!=NULL)&&(j>p->adjvex)){q=p; p=p->nextarc;}if(p==NULL&&q==NULL)G.vertices[i].firstarc=s;else if(p==NULL&&q!=NULL)q->nextarc=s;else if(p!=NULL&&q==NULL){G.vertices[i].firstarc=s;s->nextarc=p;}else{q->nextarc=s;s->nextarc=p;}}}//按深度优先判断顶点vx和vy间是否存在路径void DFSPath(ALGraph G, int v, VertexType vy){ ArcNode *w;int i;visitpath[++pathvexnum]=v;visited[v]=1;w=G.vertices[v].firstarc; //顶点v的第一个邻接点while(w!=NULL) //是否存在{i=w->adjvex; //邻接点下标if(G.vertices[i].data==vy){flag=1;return;}else if(flag==0&&visited[i]==0)DFSPath(G,i,vy);w=w->nextarc; //v的下一个邻接点}if(flag==0)pathvexnum--;//从路径上删除V}void Path(ALGraph G, VertexType vx, VertexType vy){int i;for(i=1;i<=Max_Vertex_Num;i++)visited[i]=0;for(i=1;i<=G.vexnum;i++)if(G.vertices[i].data==vx)break;DFSPath(G,i,vy);if(flag==1){printf("顶点%c到顶点%c之间存在路径,路经为:",vx,vy);for(i=1;i<=pathvexnum;i++)printf("%c\t",G.vertices[visitpath[i]].data);printf("%c\n",vy);}elseprintf("顶点%c到顶点%c之间不存在路径\n",vx,vy);}void main(){ALGraph G;int i;VertexType vx,vy;ArcNode *p;printf("请输入顶点和边的数目:");scanf("%d,%d",&G.vexnum,&G.arcnum);CreateAdjList(G);printf("\n图的邻接表为:\n");for(i=1;i<=G.vexnum;i++){printf("%c\t",G.vertices[i].data);p=G.vertices[i].firstarc;while(p){printf("%d\t",p->adjvex);p=p->nextarc;}printf("\n");}printf("请输入需判断是否存在路径的两个顶点:");fflush(stdin);scanf("%c,%c",&vx,&vy);Path(G,vx,vy);}。

相关主题