资源描述:
《实现图的邻接矩阵和邻接表存储》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、#include#include#defineMAXV100//以下定义邻接矩阵类型typedefstruct{intno;//顶点编号intinfo;//顶点其余的信息}VertexType;typedefstruct{intedges[MAXV][MAXV];//邻接矩阵intn,e;//顶点数,弧数VertexTypevexs[MAXV];//存放顶点信息}MGraph;//一下定义邻接表类型typedefstructANode//弧的节点结构类型{intadjvex;//该弧的终点位置structANode*nextarc;in
2、tinfo;//弧的相关信息}ArcNode;typedefstructVnode//邻接表头结点类型{intdata;//顶点信息ArcNode*firstarc;//指向第一条弧}VNode;typedefVNodeAdjList[MAXV];typedefstruct{AdjListadjlist;intn,e;}ALGraph;voidMatToList(MGraphg,ALGraph*&G)//将邻接矩阵g转换为邻接表G{inti,j,n=g.n;ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i3、++)G->adjlist[i].firstarc=NULL;for(i=0;i=0;j--)if(g.edges[i][j]){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->info=g.edges[i][j];p->nextarc=G->adjlist[i].firstarc;G->adjlist[i].firstarc=p;}G->n=n;G->e=g.e;}voidListToMat(ALGraph*G,MGraph&g)//邻接表G转换为邻接矩阵g{inti,j,n=G-
4、>n;ArcNode*p;for(i=0;iadjlist[i].firstarc;while(p){g.edges[i][p->adjvex]=p->info;p=p->nextarc;}}g.n=n;g.e=G->e;}voidDispMat(MGraphg)//输出邻接矩阵{inti,j;for(i=0;i5、;elseif(i==j)printf("%3d",0);elseprintf("%3s","*");printf("");}}voidDispAdj(ALGraph*G)//输出邻接表{inti;ArcNode*p;for(i=0;in;i++){p=G->adjlist[i].firstarc;if(p)printf("%3d:",i);while(p){printf("%3d",p->adjvex);p=p->nextarc;}printf("");}}intmain(){inti,j;MGraphg,g1;ALGraph*G;intA[MAXV][6
6、]={{0,5,0,7,0,0},{0,0,4,0,0,0},{8,0,0,0,0,9},{0,0,5,0,0,6},{0,0,0,5,0,0},{3,0,0,0,1,0}};g.n=6;g.e=10;for(i=0;i7、dj(G);printf("图G的邻接表转换成邻接矩阵:");ListToMat(G,g1);DispMat(g1);printf("");return0;}