图的邻接矩阵和邻接表相互转换.docx

《图的邻接矩阵和邻接表相互转换.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、精品文档图的邻接矩阵和邻接表相互转换图的邻接矩阵存储方法具有如下几个特征：1)无向图的邻接矩阵一定是一个对称矩阵。2）对于无向图的邻接矩阵的第i行非零元素的个数正好是第i个顶点的度TDvi。3）对于有向图，邻接矩阵的第i行非零元素的个数正好是第i个顶点的出度ODvi（或入度IDvi）。4）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所发费得时间代价大。邻接表是图的一种顺序存储与链式存储相结合的存储方法。若无向图中有n个顶点、e条边，则它的邻接表需n个头结点和2e个表结点。显然，

2、在边稀疏的情况下，用邻接表表示图比邻接矩阵存储空间。在无向图的邻接表中，顶点vi的度恰好是第i个链表中的结点数，而在有向图中，第i个链表中结点个数是顶点vi的出度。在建立邻接表或邻逆接表时，若输入的顶点信息即为顶点的编号，则建立临接表的时间复杂度是O(ne)；否则，需要通过查找才能得到顶点在图中位置，则时间复杂度为O(n*e)。在邻接表上容易找到任意一顶点的第一个邻接点和下一个邻接点，但要判断任意两个顶点之间是否有边或弧，则需要搜索第i个或第j个链表，因此，不及邻接矩阵方便。邻接矩阵和邻接表相互转换程序代码如下：#include#defi

3、neMAX20//图的邻接表存储表示typedefstructArcNode{intadjvex;//弧的邻接定点charinfo;//邻接点值structArcNode*nextarc;//指向下一条弧的指针}ArcNode;typedefstructVnode{//节点信息chardata;ArcNode*link;}Vnode,AdjList[MAX];typedefstruct{AdjListvertices;intvexnum;//节点数intarcnum;//边数。1欢迎下载精品文档}ALGraph;//图的邻接矩阵存储表示typedefstruct

4、{intn;//顶点个数charvexs[MAX];//定点信息intarcs[MAX][MAX];//边信息矩阵}AdjMatrix;/***_____________________________________________________***///函数名：AdjListToMatrix(AdjListg1,AdjListMatrix&gm,intn)//参数：（传入）AdjListg1图的邻接表,（传入）intn顶点个数，（传出）AdjMatrixgm图的邻接矩阵//功能：把图的邻接表表示转换成图的邻接矩阵表示voidAdjListToAdjMat

5、rix(ALGraphgl,AdjMatrix&gm){inti,j,k;ArcNode*p;gm.n=gl.vexnum;for(k=0;kadjvex]=1;p=p->next

6、arc;}}}/***________________________________________________***///函数名：AdjMatrixToAdjListvoidAdjMatrixToAdjList(AdjMatrixgm,ALGraph&gl){inti,j,k,choice;ArcNode*p;k=0;gl.vexnum=gm.n;cout<<"请选择所建立的图形是无向图或是有向图：";cin>>choice;for(i=0;i

7、ertices[i].link=NULL;}for(i=0;iadjvex=j;p->info=gm.vexs[j];p->nextarc=gl.vertices[i].link;gl.vertices[i].link=p;}if(choice==1)k=k/2;gl.arcnum=k;}voidCreateAdjList(ALGraph&G){inti,s,d,choice;ArcNode*p;cout<<"请选择所建立的

8、图形是有向图或是无向图：