用邻接矩阵存储无向图和用邻接表存储无向图对二者的说明以及分析二者的优缺点

邻接矩阵是一种二维数组，其中的元素表示两个顶点之间是否有边连接。对于无向图，邻接矩阵是对称的，即 $A_{ij}=A_{ji}$。当 $A_{ij}=1$ 时，表示顶点 $i$ 和 $j$ 之间有边连接，否则表示它们之间没有边连接。邻接矩阵可以通过下标快速访问两个顶点之间是否有边连接，时间复杂度为 $O(1)$，但是它需要 $O(n^2)$ 的空间复杂度，其中 $n$ 表示顶点数。

邻接表是一种链表的数组，其中每个链表表示一个顶点的邻居节点。对于无向图，每个无向边都会在两个顶点的邻接表中各出现一次。邻接表可以动态的添加和删除边，而且它的空间复杂度取决于边的数量，即 $O(m)$，其中 $m$ 表示边数。但是，访问两个顶点之间是否有边连接的时间复杂度为 $O(k)$，其中 $k$ 表示一个顶点的平均邻居数量。

对于稠密图（即边数与顶点数的比值接近于 1），邻接矩阵比邻接表更适用，因为它的访问时间复杂度为 $O(1)$，并且它的空间复杂度为 $O(n^2)$，与边数无关。而对于稀疏图（即边数与顶点数的比值远小于 1），邻接表比邻接矩阵更适用，因为它的空间复杂度为 $O(m)$，与顶点数无关，而且它的访问时间复杂度为 $O(k)$，与边数成正比，比邻接矩阵更高效。

相关问题

说明邻接矩阵存储无向图和邻接表存储无向图以及分析二者的优缺点

邻接矩阵和邻接表都是存储无向图的数据结构。

邻接矩阵是一个二维数组，其中 $matrix[i][j]$ 表示节点 $i$ 和节点 $j$ 是否相连。对于无向图来说，邻接矩阵是一个对称的矩阵。

邻接表则是使用链表来表示每个节点的邻居节点。每个节点有一个链表，链表中存储了该节点的所有邻居节点。

邻接矩阵和邻接表在存储无向图时，各有其优缺点：

邻接矩阵的优点：

- 查找两个节点之间是否有边的时间复杂度为 $O(1)$。
- 方便计算度数和邻居节点。
- 对于稠密图（边数接近于节点数的平方），邻接矩阵更加节省空间。

邻接矩阵的缺点：

- 对于稀疏图（边数远小于节点数的平方），邻接矩阵会浪费大量的空间。
- 添加或删除节点或边的时间复杂度为 $O(n^2)$。

邻接表的优点：

- 对于稀疏图，邻接表可以节约空间。
- 添加或删除节点或边的时间复杂度为 $O(1)$。

邻接表的缺点：

- 查找两个节点之间是否有边的时间复杂度为 $O(k)$，其中 $k$ 是节点的度数。
- 计算度数和邻居节点可能需要遍历整个链表，时间复杂度为 $O(n)$。

用C语言编写无向图的邻接矩阵存储向邻接表存储转换并打印

好的，下面是用 C 语言实现将无向图的邻接矩阵存储方式转换为邻接表存储方式，并打印出转换后的邻接表的代码：

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

// 定义邻接表中的边结构体
typedef struct Edge {
    int dest;  // 目标顶点
    struct Edge* next;  // 指向下一个边的指针
} Edge;

// 定义邻接表中的顶点结构体
typedef struct Vertex {
    Edge* head;  // 指向第一条边的指针
} Vertex;

// 将邻接矩阵转换为邻接表
void adjMatrixToAdjList(int** adjMatrix, int n, Vertex* adjList) {
    int i, j;
    for (i = 0; i < n; i++) {
        // 初始化每个顶点的边链表
        adjList[i].head = NULL;
        for (j = 0; j < n; j++) {
            if (adjMatrix[i][j] != 0) {
                // 如果邻接矩阵中 (i, j) 位置的值不为 0，则说明顶点 i 和 j 之间有一条边
                // 创建一个新的边结构体，连接到目标顶点 j
                Edge* newEdge = (Edge*)malloc(sizeof(Edge));
                newEdge->dest = j;
                newEdge->next = NULL;
                // 将新建的边插入到当前顶点 i 对应的边链表的头部
                newEdge->next = adjList[i].head;
                adjList[i].head = newEdge;
            }
        }
    }
}

// 打印邻接表
void printAdjList(Vertex* adjList, int n) {
    int i;
    for (i = 0; i < n; i++) {
        printf("%d: ", i);
        Edge* cur = adjList[i].head;
        while (cur != NULL) {
            printf("%d ", cur->dest);
            cur = cur->next;
        }
        printf("\n");
    }
}

int main() {
    // 定义一个 5 个顶点的无向图的邻接矩阵
    int adjMatrix[5][5] = {
        {0, 1, 1, 0, 1},
        {1, 0, 1, 1, 0},
        {1, 1, 0, 1, 0},
        {0, 1, 1, 0, 1},
        {1, 0, 0, 1, 0}
    };
    // 定义一个数组来存储邻接表
    Vertex adjList[5];
    // 将邻接矩阵转换为邻接表
    adjMatrixToAdjList((int**)adjMatrix, 5, adjList);
    // 打印邻接表
    printAdjList(adjList, 5);
    return 0;
}

这段代码中，我们首先定义了邻接表中的边和顶点结构体。在 `adjMatrixToAdjList` 函数中，我们遍历邻接矩阵中的每个元素，如果发现当前位置的值不为 0，则说明该位置对应的两个顶点之间有一条边。我们创建一个新的边结构体，将目标顶点的编号赋值给 `dest` 字段，并将新建的边插入到当前顶点对应的边链表的头部。最后，通过调用 `printAdjList` 函数，我们可以打印出转换后的邻接表。

希望这个回答能够帮到你！