C语言实现图的数据结构实验报告

实验目的

了解图的基本概念和性质；
掌握图的存储结构和基本算法；
学会用 C 语言实现图的基本操作。

实验内容

实现图的存储结构，包括邻接矩阵和邻接表；
实现图的基本操作，包括创建图、插入节点、删除节点、插入边、删除边、深度优先遍历和广度优先遍历；
对两种存储结构和基本操作进行比较分析，分析它们各自的优缺点。

实验步骤

1. 实现邻接矩阵存储结构

邻接矩阵是一种简单的表示图的方法，它是一个二维数组，其中每个元素表示两个节点之间是否有边相连。对于无向图来说，矩阵是对称的，对于有向图来说，矩阵不一定是对称的。

2. 实现邻接表存储结构

邻接表是一种更为常用的表示图的方法，它使用链表来存储每个节点的邻接点。对于每个节点，邻接表中存储了一个指向它邻接点链表的指针。

3. 实现图的基本操作

创建图: 根据输入的节点数和边数创建一个空图。
插入节点: 向图中插入一个新的节点。
删除节点: 从图中删除一个节点以及与之相连的边。
插入边: 向图中插入一条边。
删除边: 从图中删除一条边。
深度优先遍历: 从指定节点开始对图进行深度优先遍历。
广度优先遍历: 从指定节点开始对图进行广度优先遍历。

4. 对邻接矩阵和邻接表进行比较分析

邻接矩阵 的优点是简单、直观，方便实现基本操作。但是当图的规模比较大时，矩阵所需的存储空间会很大，对于稀疏图来说，会造成存储空间的浪费。
邻接表 的优点是存储空间效率高，对于稀疏图来说，存储空间的浪费比较小。同时，邻接表也比较容易实现各种基本操作。但是邻接表的缺点是访问邻接点需要遍历链表，对于密集图来说，访问邻接点的效率比较低。

实验结果

经过实验测试，邻接表存储结构在图的存储和基本操作方面表现更优。在稀疏图的情况下，邻接表存储结构的存储空间利用率更高，而且基本操作的效率也比邻接矩阵高。但是，在密集图的情况下，邻接矩阵的效率会比邻接表高一些。

代码实现

以下是邻接表存储结构的 C 语言代码实现（部分代码省略）：

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

typedef struct graph {
    int node_num;
    int edge_num;
    Node** adj_list;
} Graph;

Graph* create_graph(int node_num, int edge_num) {
    Graph* graph = (Graph*) malloc(sizeof(Graph));
    graph->node_num = node_num;
    graph->edge_num = edge_num;
    graph->adj_list = (Node**) malloc(node_num * sizeof(Node*));
    for (int i = 0; i < node_num; i++) {
        graph->adj_list[i] = NULL;
    }
    return graph;
}

void insert_node(Graph* graph, int val) {
    Node* node = (Node*) malloc(sizeof(Node));
    node->val = val;
    node->next = NULL;
    graph->adj_list[val] = node;
}

void delete_node(Graph* graph, int val) {
    Node* node = graph->adj_list[val];
    while (node != NULL) {
        int adj_val = node->val;
        Node* adj_node = graph->adj_list[adj_val];
        while (adj_node->next != NULL && adj_node->next->val != val) {
            adj_node = adj_node->next;
        }
        if (adj_node->next != NULL) {
            Node* tmp = adj_node->next;
            adj_node->next = tmp->next;
            free(tmp);
        }
        node = node->next;
    }
    free(node);
    graph->adj_list[val] = NULL;
}

void insert_edge(Graph* graph, int start, int end) {
    Node* node = (Node*) malloc(sizeof(Node));
    node->val = end;
    node->next = graph->adj_list[start];
    graph->adj_list[start] = node;
}

void delete_edge(Graph* graph, int start, int end) {
    Node* node = graph->adj_list[start];
    Node* prev = NULL;
    while (node != NULL && node->val != end) {
        prev = node;
        node = node->next;
    }
    if (node != NULL) {
        if (prev == NULL) {
            graph->adj_list[start] = node->next;
        } else {
            prev->next = node->next;
        }
        free(node);
    }
}

void dfs_helper(Graph* graph, int node, bool* visited) {
    visited[node] = true;
    printf('%d ', node);
    Node* adj_node = graph->adj_list[node];
    while (adj_node != NULL) {
        int adj_val = adj_node->val;
        if (!visited[adj_val]) {
            dfs_helper(graph, adj_val, visited);
        }
        adj_node = adj_node->next;
    }
}

void dfs(Graph* graph, int start) {
    bool* visited = (bool*) malloc(graph->node_num * sizeof(bool));
    for (int i = 0; i < graph->node_num; i++) {
        visited[i] = false;
    }
    dfs_helper(graph, start, visited);
    free(visited);
}

void bfs(Graph* graph, int start) {
    bool* visited = (bool*) malloc(graph->node_num * sizeof(bool));
    for (int i = 0; i < graph->node_num; i++) {
        visited[i] = false;
    }
    Queue* q = create_queue();
    enqueue(q, start);
    visited[start] = true;
    while (!is_empty(q)) {
        int node = dequeue(q);
        printf('%d ', node);
        Node* adj_node = graph->adj_list[node];
        while (adj_node != NULL) {
            int adj_val = adj_node->val;
            if (!visited[adj_val]) {
                visited[adj_val] = true;
                enqueue(q, adj_val);
            }
            adj_node = adj_node->next;
        }
    }
    free(visited);
}