【数据结构】邻接表与邻接矩阵的转换

一.基本思想

1.邻接矩阵转换为邻接表：

先设置一个空的邻接表，然后查找邻接矩阵的值不为零元素，找到后在邻接表的单链表对应位置加入表边节点。

2.邻接表转换为邻接矩阵：

在邻接表上顺序取出每个表边结点，将邻接矩阵对应单元置1.

二.代码实现

邻接矩阵转换为邻接表

template <class T>
VertexNode<T>* change(MGraph<T> v){VertexNode<T>* p;int i,j;struct ArcNode *q;p=new VertexNode<T> [v.vertexNum];for(i=0;i<v.vertexNum;i++){//邻接表赋初值p[i].vertex=i;p[i].firstEdge=NULL;}for(i=0;i<v.vertexNum;i++){for(j=0;i<v.vertexNum;j++){if(v.arc[i][j]){q=new struct ArcNode;q->adjvex=j;q->next=p[i].firstEdge;p[i].firstEdge=q;}}}return p;
}

邻接表转换为邻接矩阵

template <class T>
int** change(ALGraph<T> v){int **p=new int[v.vertexNum][v.vertexNum];int i,j;struct ArcNode *q;for(i=0;i<v.vertexNum;i++){//邻接矩阵赋初值for(j=0;j<v.vertexNum;j++){p[i][j]=0;}}for(i=0;i<v.vertexNum;i++){q=v.adjList[i].firstEdge;while(q){p[i][q->adjvex]=1;q=q->next;}}return p;
}