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

精品文档图的邻接矩阵和邻接表相互转换图的邻接矩阵存储方法具有如下几个特征：1)无向图的邻接矩阵一定是一个对称矩阵。2）对于无向图的邻接矩阵的第i行非零元素的个数正好是第i个顶点的度。3）对于有向图，邻接矩阵的第i行非零元素的个数正好是第i个顶点的出度（或入度）。4）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所发费得时间代价大。邻接表是图的一种顺序存储与链式存储相结合的存储方法。若无向图中有n个顶点、e条边，则它的邻接表需n个头结点和2e个表结点。显然，在边稀疏的情况下，用邻接表表示图比邻接矩阵存储空间。在无向图的邻接表中，顶点的度恰好是第i个链表中的结点数，而在有向图中，第i个链表中结点个数是顶点的出度。在建立邻接表或邻逆接表时，若输入的顶点信息即为顶点的编号，则建立临接表的时间复杂度是；否则，需要通过查找才能得到顶点在图中位置，则时间复杂度为。在邻接表上容易找到任意一顶点的第一个邻接点和下一个邻接点，但要判断任意两个顶点之间是否有边或弧，则需要搜索第i个或第j个链表，因此，不及邻接矩阵方便。邻接矩阵和邻接表相互转换程序代码如下：#include#define MAX 20/图的邻接表存储表示typedef struct ArcNodeint adjvex; /弧的邻接定点char info; /邻接点值struct ArcNode *nextarc; /指向下一条弧的指针ArcNode;typedef struct Vnode /节点信息char data;ArcNode *link;Vnode,AdjListMAX;typedef struct AdjList vertices; int vexnum; /节点数int arcnum; /边数ALGraph;/图的邻接矩阵存储表示typedef struct int n; /顶点个数char vexsMAX; /定点信息int arcsMAXMAX; /边信息矩阵AdjMatrix;/*_*/函数名：AdjListToMatrix(AdjList g1,AdjListMatrix &gm,int n)/参数：（传入）AdjList g1图的邻接表,（传入）int n顶点个数，（传出）AdjMatrix gm图的邻接矩阵/功能：把图的邻接表表示转换成图的邻接矩阵表示void AdjListToAdjMatrix(ALGraph gl,AdjMatrix &gm)int i,j,k;ArcNode *p;gm.n=gl.vexnum;for(k=0;kgl.vexnum;k+)gm.vexsk=gl.verticesk.data;for(i=0;iMAX;i+)for(j=0;jMAX;j+)gm.arcsij=0; for(i=0;iadjvex=1;p=p-nextarc; /*_*/函数名：AdjMatrixToAdjListvoid AdjMatrixToAdjList(AdjMatrix gm,ALGraph &gl)int i,j,k,choice;ArcNode *p;k=0;gl.vexnum=gm.n;coutchoice;for(i=0;igm.n;i+)gl.verticesi.data=gm.vexsi;gl.verticesi.link=NULL;for(i=0;igm.n;i+)for(j=0;jadjvex=j;p-info=gm.vexsj;p-nextarc=gl.verticesi.link;gl.verticesi.link=p; if(choice=1)k=k/2;gl.arcnum=k;void CreateAdjList(ALGraph &G)int i,s,d,choice;ArcNode *p;coutchoice;cout请输入节点数和边数：G.vexnumG.arcnum;for(i=0;iG.vexnum;i+)cout第iG.verticesi.data;G.verticesi.link=NULL;if(choice=1)for(i=0;i2*(G.vexnum);i+)coutsd;p=new ArcNode;p-adjvex=d;p-info=G.verticesd.data;p-nextarc=G.verticess.link;G.verticess.link=p;elsefor(i=0;iG.vexnum;i+)coutsd;p=new ArcNode;p-adjvex=d;p-info=G.verticesd.data;p-nextarc=G.verticess.link;G.verticess.link=p;void CreateAdjMatrix(AdjMatrix &M)int i,j,k,choice;coutM.n; cout请输入如顶点信息:endl;for(k=0;kM.vexsk;coutchoice;cout请输入边信息：endl;for(i=0;iM.n;i+)for(j=0;jM.n;j+)M.arcsij=0;switch(choice)case 1:for(k=0;kij;M.arcsij=M.arcsji=1; ;break;case 2:for(k=0;kij;M.arcsij=1; ;break;void OutPutAdjList(ALGraph &G)int i;ArcNode *p;cout图的邻接表如下：endl;for(i=0;iG.vexnum;i+)coutG.verticesi.data;p=G.verticesi.link;while(p!=NULL)cout(adjvex infonextarc;coutendl;void OutPutAdjMatrix(AdjMatrix gm)cout图的邻接矩阵如下：endl;for(int i=0;igm.n;i+)for(int j=0;jgm.n;j+)coutgm.arcsij;coutendl;void main()ALGraph gl1,gl2;AdjMatrix gm1,gm2;CreateAdjList(gl1);AdjListToAdjMatrix(gl1,gm1);OutPutAdjList(gl1);OutPutAdjMatrix(gm1);Creat