将邻接矩阵转化为邻接表

解决方法

邻接表是一种图的表示方式，可以通过链表来表示每个顶点的邻接点集合。将邻接矩阵转化为邻接表，可以先创建一个顶点数组，然后对于每个顶点，将其对应的行或列中非零元素的列或行号（表示相邻的其他顶点）存储到该顶点的链表中。

代码实现

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 50

// 邻接表中的边结构体
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 vertexNum;  // 顶点数
    int edgeNum;  // 边数
}Graph;

// 将邻接矩阵转化为邻接表
void createGraph(Graph *G, int matrix[][MAX_VERTEX_NUM])
{
    int i, j;
    for (i = 0; i < G->vertexNum; i++) {
        G->adjList[i].data = i;  // 顶点的数据为下标
        G->adjList[i].firstedge = NULL;  // 初始化指向第一个邻接点的指针为空
        for (j = 0; j < G->vertexNum; j++) {
            if (matrix[i][j] != 0) {  // 邻接矩阵中元素不为0，表示有边
                // 创建一个邻接点结构体
                EdgeNode *edge = (EdgeNode*)malloc(sizeof(EdgeNode));
                edge->adjvex = j;
                edge->next = G->adjList[i].firstedge;  // 将新创建的邻接点插入到该顶点的链表头
                G->adjList[i].firstedge = edge;  // 更新该顶点的链表头指针
            }
        }
    }
}

int main()
{
    int matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM] = {  // 邻接矩阵
        {0, 1, 1, 0},
        {1, 0, 0, 1},
        {1, 0, 0, 1},
        {0, 1, 1, 0}
    };
    Graph G;
    G.vertexNum = 4;
    createGraph(&G, matrix);
    // 输出邻接表
    for (int i = 0; i < G.vertexNum; i++) {
        printf("%d: ", G.adjList[i].data);
        EdgeNode *p = G.adjList[i].firstedge;
        while (p) {
            printf("%d ", p->adjvex);
            p = p->next;
        }
        printf("\n");
    }
    return 0;
}