图的邻接矩阵存储的时间和空间复杂度

图的邻接矩阵存储可以用一个二维数组来表示，其中数组的行和列分别表示图中的每个节点，数组中的值表示对应节点之间的边的权重或者是否有边相连。时间和空间复杂度如下：

时间复杂度：
- 添加一条边：O(1)
- 删除一条边：O(1)
- 查询两个节点之间是否有边：O(1)

空间复杂度：
- 对于无向图，邻接矩阵是对称的，因此需要存储n(n-1)/2个元素，空间复杂度为O(n^2)
- 对于有向图，需要存储n^2个元素，空间复杂度为O(n^2)

由于邻接矩阵存储方式需要预先分配足够的空间来存储整个图，因此对于稀疏图来说，邻接矩阵的空间效率不够高，而对于密集图来说，邻接矩阵的时间效率比邻接表高。

相关问题

邻接矩阵和邻接表 广度深度搜索时间复杂度

邻接矩阵和邻接表是用于表示图的两种常见方式。邻接矩阵是一个二维数组，其中数组的行和列分别代表图中的节点，而数组中每个元素表示相应节点之间的边的权重或是否连通。邻接表则是由一个数组和一组链表组成，数组中的每个元素对应一个节点，而链表中存储与该节点直接相连的其他节点。

广度优先搜索（BFS）和深度优先搜索（DFS）是常见的图搜索算法。BFS是从起始节点开始，逐层扩展搜索范围，直到找到目标节点或搜索完所有可达节点为止；DFS则是从起始节点开始沿着一条路径一直深入，直到找到目标节点或搜索到无路可走为止。

邻接矩阵和邻接表的时间复杂度如下：
- 邻接矩阵：
- 存储空间：O(n^2)，其中n为节点数
- 搜索复杂度：BFS和DFS都为O(n^2)
- 邻接表：
- 存储空间：O(n+e)，其中e为边数
- 搜索复杂度：BFS为O(n+e)，DFS为O(n+e)

自定义图的邻接矩阵和邻接表两种存储结构。以下两项任选其一： (1)创建图的邻接矩阵，设计算法自动生成邻接表，或： (2)创建图的邻接表，设计算法自动生成邻接矩阵。 要求能够打印图的邻接矩阵和邻接表，进行验证。 用C语言实现 并给出时间复杂度与空间复杂度

我们选择第一种方式，即创建图的邻接矩阵，设计算法自动生成邻接表。

假设我们的图有n个节点，邻接矩阵可以用一个n*n的二维数组来表示，其中matrix[i][j]表示节点i到节点j之间是否有边。

我们可以通过遍历邻接矩阵，来生成邻接表。具体步骤如下：

1. 创建一个长度为n的数组adj_list，用于存储邻接表。
2. 遍历邻接矩阵，对于每个matrix[i][j]为1的节点i和节点j，将j加入i的邻接表中。
3. 打印邻接表。

以下是C语言实现的代码：

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

#define MAX_VERTEX_NUM 100

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

typedef struct adj_list {
    node* head;
}adj_list;

void print_adj_matrix(int n, int matrix[][MAX_VERTEX_NUM]) {
    printf("邻接矩阵：\n");
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

void print_adj_list(int n, adj_list* adj_list) {
    printf("邻接表：\n");
    for(int i = 0; i < n; i++) {
        printf("%d: ", i);
        node* current = adj_list[i].head;
        while (current != NULL) {
            printf("%d ", current->vertex);
            current = current->next;
        }
        printf("\n");
    }
}

void matrix_to_list(int n, int matrix[][MAX_VERTEX_NUM], adj_list* adj_list) {
    for(int i = 0; i < n; i++) {
        adj_list[i].head = NULL;
        for(int j = 0; j < n; j++) {
            if(matrix[i][j] == 1) {
                node* new_node = (node*)malloc(sizeof(node));
                new_node->vertex = j;
                new_node->next = adj_list[i].head;
                adj_list[i].head = new_node;
            }
        }
    }
}

int main() {
    int n = 5;
    int matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM] = {
        {0, 1, 0, 1, 0},
        {1, 0, 1, 1, 1},
        {0, 1, 0, 0, 1},
        {1, 1, 0, 0, 1},
        {0, 1, 1, 1, 0}
    };
    adj_list adj_list[MAX_VERTEX_NUM];
    print_adj_matrix(n, matrix);
    matrix_to_list(n, matrix, adj_list);
    print_adj_list(n, adj_list);
    return 0;
}

时间复杂度：O(n^2)，空间复杂度：O(n^2)（邻接矩阵）+ O(n^2)（邻接表）。