c语言以邻接表的形式创建一个无向图算法分析

创建无向图的邻接表可以用链式存储结构来实现。我们可以定义一个结构体表示图中的一个节点，包括节点值和指向与之相连的节点的指针。然后，我们可以使用一个数组来存储所有节点，并用链表将相邻的节点连接起来。

以下是创建无向图的邻接表的具体步骤：

1. 定义结构体表示图中的节点：

struct Node {
    int val;  // 节点值
    struct Node* next;  // 指向下一个节点的指针
};

2. 定义邻接表的数组，每个元素表示一个节点：

struct Node* adjList[MAX_NODE];  // MAX_NODE 表示节点的最大数量

3. 初始化邻接表数组，将所有指针初始化为空：

for (int i = 0; i < MAX_NODE; i++) {
    adjList[i] = NULL;
}

4. 添加边。对于每条边 (u, v)，我们需要在节点 u 的邻接表中添加一个指向节点 v 的指针，在节点 v 的邻接表中添加一个指向节点 u 的指针。

void addEdge(int u, int v) {
    // 在节点 u 的邻接表中添加指向节点 v 的指针
    struct Node* node1 = (struct Node*)malloc(sizeof(struct Node));
    node1->val = v;
    node1->next = adjList[u];
    adjList[u] = node1;
    
    // 在节点 v 的邻接表中添加指向节点 u 的指针
    struct Node* node2 = (struct Node*)malloc(sizeof(struct Node));
    node2->val = u;
    node2->next = adjList[v];
    adjList[v] = node2;
}

5. 遍历邻接表。我们可以使用一个循环遍历邻接表的数组，对于每个节点，再遍历它的邻接表，即可访问所有与之相连的节点。

for (int i = 0; i < MAX_NODE; i++) {
    printf("Node %d: ", i);
    struct Node* cur = adjList[i];
    while (cur != NULL) {
        printf("%d ", cur->val);
        cur = cur->next;
    }
    printf("\n");
}

完整的代码实现如下：

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

#define MAX_NODE 100

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

struct Node* adjList[MAX_NODE];

void addEdge(int u, int v) {
    struct Node* node1 = (struct Node*)malloc(sizeof(struct Node));
    node1->val = v;
    node1->next = adjList[u];
    adjList[u] = node1;
    
    struct Node* node2 = (struct Node*)malloc(sizeof(struct Node));
    node2->val = u;
    node2->next = adjList[v];
    adjList[v] = node2;
}

int main() {
    // 添加边
    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 2);
    addEdge(2, 3);
    addEdge(3, 4);
    
    // 遍历邻接表
    for (int i = 0; i < MAX_NODE; i++) {
        printf("Node %d: ", i);
        struct Node* cur = adjList[i];
        while (cur != NULL) {
            printf("%d ", cur->val);
            cur = cur->next;
        }
        printf("\n");
    }
    
    return 0;
}