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，则新建一个边节点，并将该节点插入到顶点的邻接表中。

最后，我们利用两层循环打印邻接表。