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

图的邻接矩阵和邻接表相互转换 图的邻接矩阵存储方法具有如下几个特征：1)无向图的邻接矩阵一定是一个对称矩阵。2）对于无向图的邻接矩阵的第i行非零元素的个数正好是第i个顶点的度。3）对于有向图，邻接矩阵的第i行非零元素的个数正好是第i个顶点的出度（或入度）。4）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所发费得时间代价大。 邻接表是图的一种顺序存储与链式存储相结合的存储方法。若无向图中有n个顶点、e条边，则它的邻接表需n个头结点和2e个表结点。显然，在边稀疏的情况下，用邻接表表示图比邻接矩阵存储空间。在无向图的邻接表中，顶点的度恰好是第i个链表中的结点数，而在有向图中，第i个链表中结点个数是顶点的出度。 在建立邻接表或邻逆接表时，若输入的顶点信息即为顶点的编号，则建立临接表的时间复杂度是；否则，需要通过查找才能得到顶点在图中位置，则时间复杂度为。在邻接表上容易找到任意一顶点的第一个邻接点和下一个邻接点，但要判断任意两个顶点之间是否有边或弧，则需要有哪些信誉好的足球投注网站第i个或第j个链表，因此，不及邻接矩阵方便。 邻接矩阵和邻接表相互转换程序代码如下： #includeiostream.h #define MAX 20 //图的邻接表存储表示 typedef struct ArcNode{ int adjvex; //弧的邻接定点 char info; //邻接点值 struct ArcNode *nextarc; //指向下一条弧的指针 }ArcNode; typedef struct Vnode{ //节点信息 char data; ArcNode *link; }Vnode,AdjList[MAX]; typedef struct{ AdjList vertices; int vexnum; //节点数 int arcnum; //边数 }ALGraph; //图的邻接矩阵存储表示 typedef struct{ int n; //顶点个数 char vexs[MAX]; //定点信息 int arcs[MAX][MAX]; //边信息矩阵 }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.vexs[k]=gl.vertices[k].data; for(i=0;iMAX;i++) for(j=0;jMAX;j++) gm.arcs[i][j]=0; for(i=0;igl.vexnum;i++){ p=gl.vertices[i].link; //取第一个邻接顶点 while(p!=NULL){ //取下一个邻接顶点 gm.arcs[i][p-adjvex]=1; p=p-nextarc; } } } /***________________________________________________***/ //函数名：AdjMatrixToAdjList void AdjMatrixToAdjList(AdjMatrix gm,ALGraph gl){ int i,j,k,choice; ArcNode *p; k=0; gl.vexnum=gm.n; cout请选择所建立的图形是无向图或是有向图：; cinchoice; for(i=0;igm.n;i++){ gl.vertices[i].data=gm.vexs[i]; gl.vertices[i].link=NULL; } for(i=0;igm.n;i++) for(j=0;jgm.n;j++) if(gm.arcs[i][j]==1){ k