C语言 邻接矩阵转换为邻接表

邻接矩阵和邻接表是表示图的两种常见方式，其中邻接矩阵是通过二维数组来表示图的，而邻接表则是通过链表来表示图的。邻接表通常用于稀疏图的表示，而邻接矩阵则适用于稠密图的表示。
下面是将邻接矩阵转换为邻接表的C语言实现代码：
#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 100 // 最大顶点数

typedef struct EdgeNode{
int adjvex; // 邻接点的位置
struct EdgeNode *next; // 指向下一个邻接点的指针
}EdgeNode;

typedef struct VertexNode{
int data; // 顶点的数据
EdgeNode *firstedge; // 指向第一个邻接点的指针
}VertexNode, AdjList[MAX_VERTEX_NUM];

typedef struct{
AdjList adjList;
int numVertexes, numEdges; // 顶点数和边数
}GraphAdjList;

void CreateALGraph(GraphAdjList *G, int **matrix, int row, int col){
G->numVertexes = row;
G->numEdges = 0;

for(int i = 0; i < G->numVertexes; i++){
G->adjList[i].data = i; // 顶点数据
G->adjList[i].firstedge = NULL; // 初始化邻接表的头指针
for(int j = 0; j < G->numVertexes; j++){
if(matrix[i][j] != 0){
EdgeNode *e = (EdgeNode*)malloc(sizeof(EdgeNode));
e->adjvex = j;
e->next = G->adjList[i].firstedge;
G->adjList[i].firstedge = e; // 将新建的边节点插入到邻接表中
G->numEdges++; // 边数加一
}
}
}
}

int main(){
int matrix[5][5] = {
{0, 1, 0, 1, 1},
{1, 0, 1, 1, 0},
{0, 1, 0, 1, 0},
{1, 1, 1, 0, 1},
{1, 0, 0, 1, 0}
};
GraphAdjList G;
CreateALGraph(&G, (int**)matrix, 5, 5);

// 打印邻接表
for(int i = 0; i < G.numVertexes; i++){
printf("%d: ", G.adjList[i].data);
EdgeNode *e = G.adjList[i].firstedge;
while(e != NULL){
printf("%d ", e->adjvex);
e = e->next;
}
printf("\n");
}

return 0;
}

上述代码中，CreateALGraph函数用于将邻接矩阵转换为邻接表，其中邻接表通过AdjList数组来表示，每个AdjList数组元素包括一个顶点的数据和一个指向第一个邻接点的指针。具体实现中，我们遍历邻接矩阵，如果矩阵元素不为0，则新建一个边节点，并将该节点插入到顶点的邻接表中。
最后，我们利用两层循环打印邻接表。