用C语言实现图的邻接矩阵和邻接表的存储

邻接矩阵和邻接表是存储图的两种常见方式，下面是用C语言实现的示例代码：

1. 邻接矩阵存储方式：

#define MAX_VERTICES 100 // 图的最大顶点数

typedef struct {
    int vertex[MAX_VERTICES]; // 存储顶点信息
    int edge[MAX_VERTICES][MAX_VERTICES]; // 存储边的信息
    int num_vertices; // 当前顶点数
    int num_edges; // 当前边数
} Graph;

// 初始化图
void initGraph(Graph* graph) {
    graph->num_vertices = 0;
    graph->num_edges = 0;
    for (int i = 0; i < MAX_VERTICES; i++) {
        graph->vertex[i] = 0;
        for (int j = 0; j < MAX_VERTICES; j++) {
            graph->edge[i][j] = 0;
        }
    }
}

// 添加顶点
void addVertex(Graph* graph, int v) {
    if (graph->num_vertices < MAX_VERTICES) {
        graph->vertex[graph->num_vertices++] = v;
    }
}

// 添加边
void addEdge(Graph* graph, int v1, int v2) {
    if (v1 >= 0 && v1 < graph->num_vertices && v2 >= 0 && v2 < graph->num_vertices) {
        graph->edge[v1][v2] = 1;
        graph->edge[v2][v1] = 1; // 无向图需要对称
        graph->num_edges++;
    }
}

2. 邻接表存储方式：

typedef struct Node {
    int vertex; // 存储顶点信息
    struct Node* next; // 指向下一个邻接点
} Node;

typedef struct {
    Node* head; // 邻接表头节点
} AdjList;

typedef struct {
    AdjList adjList[MAX_VERTICES]; // 存储邻接表的数组
    int num_vertices; // 当前顶点数
    int num_edges; // 当前边数
} Graph;

// 初始化邻接表
void initGraph(Graph* graph) {
    graph->num_vertices = 0;
    graph->num_edges = 0;
    for (int i = 0; i < MAX_VERTICES; i++) {
        graph->adjList[i].head = NULL;
    }
}

// 添加顶点
void addVertex(Graph* graph, int v) {
    if (graph->num_vertices < MAX_VERTICES) {
        graph->num_vertices++;
    }
}

// 添加边
void addEdge(Graph* graph, int v1, int v2) {
    if (v1 >= 0 && v1 < graph->num_vertices && v2 >= 0 && v2 < graph->num_vertices) {
        Node* node = (Node*)malloc(sizeof(Node));
        node->vertex = v2;
        node->next = graph->adjList[v1].head;
        graph->adjList[v1].head = node;
        
        node = (Node*)malloc(sizeof(Node));
        node->vertex = v1;
        node->next = graph->adjList[v2].head;
        graph->adjList[v2].head = node;
        
        graph->num_edges++;
    }
}