实现图的邻接矩阵和邻接表存储

《实现图的邻接矩阵和邻接表存储》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#include#include#defineMAXV100//以下定义邻接矩阵类型typedefstruct{intno;//顶点编号intinfo;//顶点其余的信息}VertexType;typedefstruct{intedges[MAXV][MAXV];//邻接矩阵intn,e;//顶点数，弧数VertexTypevexs[MAXV];//存放顶点信息}MGraph;//一下定义邻接表类型typedefstructANode//弧的节点结构类型{intadjvex;//该弧的终点位置structANo

2、de*nextarc;intinfo;//弧的相关信息}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(size

3、of(ALGraph));for(i=0;iadjlist[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(ALGrap

4、h*G,MGraph&g)//邻接表G转换为邻接矩阵g{inti,j,n=G->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;i

5、g.n;j++)if(g.edges[i][j])printf("%3d",g.edges[i][j]);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;}

6、printf("");}}intmain(){inti,j;MGraphg,g1;ALGraph*G;intA[MAXV][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;i

7、Graph*)malloc(sizeof(ALGraph));printf("图G的邻接矩阵转换成邻接表：");MatToList(g,G);DispAdj(G);printf("图G的邻接表转换成邻接矩阵：");ListToMat(G,g1);DispMat(g1);printf("");return0;}