图的所有演示程序

《图的所有演示程序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图的所有演示程序#include#include#include#defineMaxVertexNum20//最大顶点数设为20#defineMAXCOST32767typedefintVertexType;//顶点类型设为字符型typedefintEdgeType;//边的权值设为整型typedefstruct{VertexTypevexs[MaxVertexNum];//顶点表EdgeTypeedges[MaxVertexNum][MaxVertexNum];//邻接矩阵int

2、n,e;//图中顶点数和边数}MGraph;//邻接矩阵存储的图类型*/typedefstructEdgeNode//图的结点的结构{intadjvex;//邻接点域structEdgeNode*next;//指向下一个邻接点的指针域intw;//info表示边或弧的信息}EdgeNode;typedefstruct//表头（指针数组）分量的信息{VertexTypevertex;//顶点信息intdegree;EdgeNode*firstedge;//边表头指针}VertexNode;typedefVertexNodeAdjList[Max

3、VertexNum];typedefstruct//图的邻接表{AdjListadjlist;intn,e;//顶点数和边数}ALGraph;/*intvisited[MaxVertexNum];voidcreatemgraph(MGraph*&G)//建立图的邻接矩阵{inti,j,k,w,weight;printf("请输入顶点数和边数（输入格式为：顶点数，边数）：");scanf("%d,%d",&G->n,&G->e);printf("请输入顶点信息（输入格式为：顶点号）");for(i=0;in;i++)sc

4、anf("%d",&(G->vexs[i]));for(i=0;in;i++)for(j=0;jn;j++){G->edges[i][j]=MAXCOST;if(i==j)G->edges[i][j]=0;}printf("请输入有向图（1），无向图（0）的信息:");scanf("%d",&w);printf("请输入每条对边的两个顶点的序号及其权值（输入格式为：i,j,weight）:");for(k=0;ke;k++){scanf("%d,%d,%d",&i,&j,&weight);G->edges[i]

5、[j]=weight;if(w!=1)G->edges[j][i]=weight;}}*/voidcreateALGraph(ALGraph*&G){inti,j,w,k,tn,te;EdgeNode*s;inttag;printf("请输入有向图（1）或无向图（0）:");scanf("%d",&tag);printf("请输入顶点数和边数（输入格式为：顶点数，边数）：");scanf("%d,%d",&tn,&te);G->n=tn;G->e=te;printf("请输入顶点信息（顶点信息从0开始。输入格式为：顶点号）")

6、;for(i=0;in;i++)//对表头指针数组进行初始化操作{scanf("%d",&(G->adjlist[i].vertex));G->adjlist[i].firstedge=NULL;//对指向第一条边的指针置NULL}for(i=0;in;i++)G->adjlist[i].degree=0;printf("请输入边的信息（输入格式为,若不带权，则w=0）：i,j,w");for(k=0;ke;k++){scanf("%d,%d,%d",&i,&j,&w);//读入与该边关联的两个顶点s=(EdgeN

7、ode*)malloc(sizeof(EdgeNode));s->adjvex=j;//表首添加法构建链表，将边加入到第i个链表s->w=w;s->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s;G->adjlist[j].degree++;if(tag==0){//若是无向图，还要将此边加入到第j个链表s=(EdgeNode*)malloc(sizeof(EdgeNode));s->adjvex=i;s->w=w;s->next=G->adjlist[j].firstedge;G

8、->adjlist[j].firstedge=s;}}}//建立图的邻接表存储结构结束/*voidDFSAL(ALGraph*G,inti)//遍历图从第i个顶点开