【数据结构】图的存储结构

图是一种非常重要的数据结构，用于描述各种复杂的关系和网络。在计算机科学中，图的存储结构对于图算法的设计和实现至关重要。本文将深入探讨图的两种常见存储结构——邻接矩阵和邻接表，并提供C语言代码示例，演示如何在程序中实现这两种存储结构，并讨论它们的优缺点以及适用场景。

1. 邻接矩阵（Adjacency Matrix）

邻接矩阵是一种二维数组，用于表示图中节点和边的关系。如果图中的顶点数量为 n，则邻接矩阵的大小为 n × n。矩阵中的每个元素表示两个顶点之间是否存在边，通常用 0 或 1 表示。

优点：

直观简单：邻接矩阵直观地表示了图的连接关系，易于理解和实现。
方便查找：可以快速查找任意两个顶点之间是否存在边，时间复杂度为 O(1)。

缺点：

空间复杂度高：对于稀疏图（边数远小于顶点数），邻接矩阵会浪费大量空间。
添加和删除顶点困难：当需要添加或删除顶点时，需要重新分配内存并复制数据，效率较低。

2. 邻接表（Adjacency List）

邻接表是一种链表数组，用于表示图中节点和边的关系。每个顶点都有一个链表，存储与其相连的所有顶点。

优点：

空间效率高：对于稀疏图，邻接表可以节省大量空间，只存储实际存在的边。
添加和删除顶点方便：添加或删除顶点时，只需修改相应链表，效率较高。

缺点：

查找边的效率较低：查找任意两个顶点之间是否存在边的时间复杂度为 O(V)，其中 V 是顶点数。
不直观：相比邻接矩阵，邻接表的结构相对复杂，不够直观。

下面分别通过C语言代码示例，演示如何在程序中实现邻接矩阵和邻接表，并讨论它们的适用场景：

// 邻接矩阵示例
#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

typedef struct {
    int numVertices;
    int matrix[MAX_VERTICES][MAX_VERTICES];
} Graph;

Graph* createGraph(int numVertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = numVertices;
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            graph->matrix[i][j] = 0;
        }
    }
    return graph;
}

void addEdge(Graph* graph, int src, int dest) {
    graph->matrix[src][dest] = 1;
    // 对于无向图，还需设置 matrix[dest][src] = 1;
}

void printGraph(Graph* graph) {
    printf("图的邻接矩阵表示：\n");
    for (int i = 0; i < graph->numVertices; i++) {
        for (int j = 0; j < graph->numVertices; j++) {
            printf("%d ", graph->matrix[i][j]);
        }
        printf("\n");
    }
}

// 邻接表示例
#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

typedef struct Node {
    int vertex;
    struct Node* next;
}

 Node;

typedef struct {
    int numVertices;
    Node* adjList[MAX_VERTICES];
} Graph;

Graph* createGraph(int numVertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = numVertices;
    for (int i = 0; i < numVertices; i++) {
        graph->adjList[i] = NULL;
    }
    return graph;
}

void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;

    // 对于无向图，还需反向添加边
    newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = src;
    newNode->next = graph->adjList[dest];
    graph->adjList[dest] = newNode;
}

void printGraph(Graph* graph) {
    printf("图的邻接表表示：\n");
    for (int i = 0; i < graph->numVertices; i++) {
        Node* temp = graph->adjList[i];
        printf("顶点 %d 的邻接表：", i);
        while (temp) {
            printf(" -> %d", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}

int main() {
    // 邻接矩阵示例
    Graph* graph1 = createGraph(5);
    addEdge(graph1, 0, 1);
    addEdge(graph1, 0, 2);
    addEdge(graph1, 1, 2);
    addEdge(graph1, 1, 3);
    addEdge(graph1, 2, 3);
    addEdge(graph1, 3, 4);
    printGraph(graph1);

    // 邻接表示例
    Graph* graph2 = createGraph(5);
    addEdge(graph2, 0, 1);
    addEdge(graph2, 0, 2);
    addEdge(graph2, 1, 2);
    addEdge(graph2, 1, 3);
    addEdge(graph2, 2, 3);
    addEdge(graph2, 3, 4);
    printGraph(graph2);

    return 0;
}