图的存储结构的实现及其应用c语言

图是一种非常重要的数据结构，在计算机科学中被广泛应用，例如：社交网络、电路设计、路线规划等。一般来说，图可以用多种方式进行存储，例如邻接矩阵、邻接表、十字链表等。下面以邻接矩阵为例，介绍图的存储结构的实现及其应用。

邻接矩阵是一种二维数组，其中数组的行和列分别表示图的顶点，数组中的元素表示两个顶点之间的边的关系。具体来说，如果两个顶点之间存在一条边，则对应的数组元素为1，否则为0。对于无向图，邻接矩阵是一个对称矩阵，因为边是双向的；而对于有向图，则不一定是对称矩阵。

下面是一个简单的代码示例，实现了一个无向图的邻接矩阵存储结构：

#include <stdio.h>

#define MAX_VERTICES 100

typedef struct {
    int n; // 顶点数
    int adj[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
} Graph;

void initGraph(Graph *g, int n) {
    int i, j;
    g->n = n;
    for (i = 0; i < g->n; i++) {
        for (j = 0; j < g->n; j++) {
            g->adj[i][j] = 0; // 初始化邻接矩阵
        }
    }
}

void addEdge(Graph *g, int u, int v) {
    g->adj[u][v] = 1;
    g->adj[v][u] = 1; // 无向图需要添加双向边
}

void printGraph(Graph *g) {
    int i, j;
    for (i = 0; i < g->n; i++) {
        for (j = 0; j < g->n; j++) {
            printf("%d ", g->adj[i][j]);
        }
        printf("\n");
    }
}

int main() {
    Graph g;
    initGraph(&g, 5);
    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 2);
    addEdge(&g, 2, 3);
    addEdge(&g, 3, 4);
    printGraph(&g);
    return 0;
}

上面的代码中，我们定义了一个结构体 `Graph`，包含了顶点数 `n` 和邻接矩阵 `adj`。我们通过 `initGraph()` 函数初始化邻接矩阵，然后通过 `addEdge()` 函数添加边。最后，我们通过 `printGraph()` 函数打印出邻接矩阵。

邻接矩阵存储结构的应用非常广泛，例如：

1. 判断两个顶点之间是否存在边可以在常数时间内完成，即 $O(1)$。
2. 遍历一个顶点的所有邻居可以在 $O(n)$ 时间内完成，其中 $n$ 是顶点数。
3. 计算图的度数可以在 $O(n^2)$ 时间内完成，其中 $n$ 是顶点数。
4. 判断图是否是稠密图（即边数接近于最大边数 $n(n-1)/2$）可以在 $O(n^2)$ 时间内完成。

当然，邻接矩阵存储结构也有一些缺点，例如：

1. 对于稀疏图（即边数远远小于最大边数 $n(n-1)/2$），会浪费大量的空间。
2. 在修改图结构时，需要重新分配空间，因此效率较低。

因此，在实际应用中，需要根据具体情况选择适合的存储结构。