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

邻接矩阵转换为邻接表需要以下步骤：

1. 定义邻接表结构体，包含顶点数量和指向每个顶点邻居的指针数组。

struct Graph {
    int V; // 顶点数量
    struct Node** adjList; // 指向邻居的指针数组
};

struct Node {
    int dest;
    struct Node* next;
};

2. 根据邻接矩阵创建邻接表。遍历邻接矩阵的每一个元素，如果该元素的值为1，就在邻接表中加入该边。

struct Graph* createGraph(int V, int** edges, int E) {
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;
    graph->adjList = (struct Node**) malloc(V * sizeof(struct Node*));

    // 初始化邻接表为空
    for (int i = 0; i < V; i++) {
        graph->adjList[i] = NULL;
    }

    // 添加边到邻接表
    for (int i = 0; i < E; i++) {
        int src = edges[i][0];
        int dest = edges[i][1];

        // 添加从 src 到 dest 的边
        struct Node* newNode = createNode(dest);
        newNode->next = graph->adjList[src];
        graph->adjList[src] = newNode;

        // 添加从 dest 到 src 的边
        newNode = createNode(src);
        newNode->next = graph->adjList[dest];
        graph->adjList[dest] = newNode;
    }

    return graph;
}

3. 定义创建邻接表节点的函数。

struct Node* createNode(int dest) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

完整代码如下：

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

struct Graph {
    int V; // 顶点数量
    struct Node** adjList; // 指向邻居的指针数组
};

struct Node {
    int dest;
    struct Node* next;
};

struct Graph* createGraph(int V, int** edges, int E);
struct Node* createNode(int dest);

int main() {
    int V = 5;
    int E = 7;

    int edges[][2] = {
        { 0, 1 }, { 0, 4 }, { 1, 2 }, { 1, 3 },
        { 1, 4 }, { 2, 3 }, { 3, 4 }
    };

    struct Graph* graph = createGraph(V, edges, E);

    for (int i = 0; i < V; i++) {
        printf("顶点 %d 的邻居: ", i);
        struct Node* temp = graph->adjList[i];
        while (temp) {
            printf("%d -> ", temp->dest);
            temp = temp->next;
        }
        printf("NULL\n");
    }

    return 0;
}

struct Graph* createGraph(int V, int** edges, int E) {
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;
    graph->adjList = (struct Node**) malloc(V * sizeof(struct Node*));

    // 初始化邻接表为空
    for (int i = 0; i < V; i++) {
        graph->adjList[i] = NULL;
    }

    // 添加边到邻接表
    for (int i = 0; i < E; i++) {
        int src = edges[i][0];
        int dest = edges[i][1];

        // 添加从 src 到 dest 的边
        struct Node* newNode = createNode(dest);
        newNode->next = graph->adjList[src];
        graph->adjList[src] = newNode;

        // 添加从 dest 到 src 的边
        newNode = createNode(src);
        newNode->next = graph->adjList[dest];
        graph->adjList[dest] = newNode;
    }

    return graph;
}

struct Node* createNode(int dest) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}