资源描述：
《邻接表邻接矩阵相互转换.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、邻接表,邻接矩阵相互转换#include<stdio.h>#include<malloc.h>#defineINF32767//INF表示∞typedefintInfoType;typedefintVertex;#defineMAXV50//最大顶点个数//以下定义邻接矩阵类型typedefstruct{intnunber;//顶点编号InfoTypeinfo;//顶点其他信息}VertexType;//顶点类型typedefstruct//图的定义{intedges[MAXV][MAXV];//邻接矩阵intn,e;//顶点数，弧数VertexTypev
2、exs[MAXV];//存放顶点信息}MGraph;//图的邻接矩阵类型//以下定义邻接表类型typedefstructANode//弧的结点结构类型{intadjvex;//该弧的终点位置InfoTypeinfo;//该弧的相关信息,这里用于存放权值structANode*nextarc;//指向下一条弧的指针}ArcNode;typedefstructVnode//邻接表头结点的类型{Vertexdata;//顶点信息intcount;//存放顶点入度,只在拓扑排序中用ArcNode*firstarc;//指向第一条弧}VNode;typedefVNodeAdjList[MA
3、XV];//AdjList是邻接表类型typedefstruct{AdjListadjlist;//邻接表intn,e;//图中顶点数n和边数e}ALGraph;//图的邻接表类型//将邻接矩阵g转换成邻接表GvoidMatToList(MGraphg,ALGraph*&G){inti,j,n=g.n;//n为顶点数ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));//for(i=0;i<n;i++)//给邻接表中所有头结点的指针域置初值//G->adjlist[i].firstarc=NULL;for(i=0;i&l
4、t;n;i++)//检查邻接矩阵中每个元素for(j=n-1;j>=0;j--)if(g.edges[i][j]!=0)//邻接矩阵的当前元素不为0{p=(ArcNode*)malloc(sizeof(ArcNode));//创建一个结点*pp->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.e;}voidListToMat(ALGraph*G,MGr
5、aph&g)//将邻接表G转换成邻接矩阵g{inti,n=G->n;ArcNode*p;for(i=0;i<n;i++){p=G->adjlist[i].firstarc;while(p!=NULL){g.edges[i][p->adjvex]=p->info;p=p->nextarc;}}g.n=n;g.e=G->e;}voidDispMat(MGraphg)//输出邻接矩阵g{inti,j;for(i=0;i<g.n;i++){for(j=0;j<g.n;j++)if(g.edges[i][j]==INF)prin
6、tf("%3s","∞");elseprintf("%3d",g.edges[i][j]);printf("");}}voidDispAdj(ALGraph*G)//输出邻接表G{inti;ArcNode*p;for(i=0;i<G->n;i++){p=G->adjlist[i].firstarc;printf("%3d:",i);while(p!=NULL){printf("%3d",p->adjvex);//输出该弧的终点位置p=
7、p->nextarc;}printf("");}}//以下主函数用作调试voidmain(){inti,j;MGraphg,g1;ALGraph*G;intA[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;i<g.n;i++)for(j=0;j<g.n;j++)
