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

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

广度优先搜索（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)

相关问题

c语言编程：用邻接表和邻接矩阵实现图的广度遍历和深度遍历

### 回答1：
以下是使用邻接表和邻接矩阵实现图的广度遍历和深度遍历的C语言代码示例。

邻接表实现：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数

// 边结点
typedef struct EdgeNode {
    int adjvex; // 邻接点的下标
    struct EdgeNode* next; // 指向下一个邻接点的指针
} EdgeNode;

// 顶点结点
typedef struct VertexNode {
    int data; // 顶点数据
    EdgeNode* firstedge; // 指向第一个邻接点的指针
} VertexNode, AdjList[MAX_VERTEX_NUM];

// 邻接表
typedef struct {
    AdjList vertices; // 顶点数组
    int vexnum, edgenum; // 顶点数和边数
} ALGraph;

// 初始化邻接表
void InitALGraph(ALGraph* G) {
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->edgenum);
    printf("请输入%d个顶点的数据：", G->vexnum);
    for (int i = 0; i < G->vexnum; i++) {
        scanf("%d", &G->vertices[i].data);
        G->vertices[i].firstedge = NULL;
    }
    printf("请输入%d条边的信息：\n", G->edgenum);
    for (int k = 0; k < G->edgenum; k++) {
        int i, j;
        printf("请输入第%d条边的两个顶点下标：", k + 1);
        scanf("%d%d", &i, &j);
        // 创建新结点
        EdgeNode* e = (EdgeNode*)malloc(sizeof(EdgeNode));
        e->adjvex = j;
        e->next = G->vertices[i].firstedge;
        G->vertices[i].firstedge = e;
        // 无向图还要创建一条反向边
        e = (EdgeNode*)malloc(sizeof(EdgeNode));
        e->adjvex = i;
        e->next = G->vertices[j].firstedge;
        G->vertices[j].firstedge = e;
    }
}

// 广度优先遍历
void BFS(ALGraph* G, int v) {
    bool visited[MAX_VERTEX_NUM] = { false }; // 初始化所有顶点为未访问
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
    visited[v] = true;
    queue[rear++] = v;
    printf("BFS: ");
    while (front < rear) {
        int i = queue[front++];
        printf("%d ", G->vertices[i].data);
        EdgeNode* e = G->vertices[i].firstedge;
        while (e != NULL) {
            int j = e->adjvex;
            if (!visited[j]) {
                visited[j] = true;
                queue[rear++] = j;
            }
            e = e->next;
        }
    }
    printf("\n");
}

// 深度优先遍历（递归版）
void DFS(ALGraph* G, int v, bool visited[]) {
    visited[v] = true;
    printf("%d ", G->vertices[v].data);
    EdgeNode* e = G->vertices[v].firstedge;
    while (e != NULL) {
        int j = e->adjvex;
        if (!visited[j]) {
            DFS(G, j, visited);
        }
        e = e->next;
    }
}

// 深度优先遍历（非递归版）
void DFS2(ALGraph* G, int v) {
    bool visited[MAX_VERTEX_NUM] = { false };
    int stack[MAX_VERTEX_NUM], top = 0;
    visited[v] = true;
    stack[top++] = v;
    printf("DFS: ");
    while (top > 0) {
        int i = stack[--top];
        printf("%d ", G->vertices[i].data);
        EdgeNode* e = G->vertices[i].firstedge;
        while (e != NULL) {
            int j = e->adjvex;
            if (!visited[j]) {
                visited[j] = true;
                stack[top++] = j;
            }
            e = e->next;
        }
    }
    printf("\n");
}

int main() {
    ALGraph G;
    InitALGraph(&G);
    BFS(&G, 0);
    bool visited[MAX_VERTEX_NUM] = { false };
    DFS(&G, 0, visited);
    printf("\n");
    DFS2(&G, 0);
    return 0;
}

邻接矩阵实现：

#include <stdio.h>
#include <stdbool.h>

#define MAX_VERTEX_NUM 100 // 最大顶点数

// 邻接矩阵
typedef struct {
    int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 二维数组表示边
    int vexnum, edgenum; // 顶点数和边数
} MGraph;

// 初始化邻接矩阵
void InitMGraph(MGraph* G) {
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->edgenum);
    printf("请输入%d个顶点的数据：", G->vexnum);
    for (int i = 0; i < G->vexnum; i++) {
        for (int j = 0; j < G->vexnum; j++) {
            G->edges[i][j] = 0; // 初始化所有边为0
        }
    }
    for (int i = 0; i < G->vexnum; i++) {
        int data;
        scanf("%d", &data);
    }
    printf("请输入%d条边的信息：\n", G->edgenum);
    for (int k = 0; k < G->edgenum; k++) {
        int i, j;
        printf("请输入第%d条边的两个顶点下标：", k + 1);
        scanf("%d%d", &i, &j);
        G->edges[i][j] = G->edges[j][i] = 1; // 无向图需要将两个方向的边都设置为1
    }
}

// 广度优先遍历
void BFS(MGraph* G, int v) {
    bool visited[MAX_VERTEX_NUM] = { false }; // 初始化所有顶点为未访问
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
    visited[v] = true;
    queue[rear++] = v;
    printf("BFS: ");
    while (front < rear) {
        int i = queue[front++];
        printf("%d ", i);
        for (int j = 0; j < G->vexnum; j++) {
            if (G->edges[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                queue[rear++] = j;
            }
        }
    }
    printf("\n");
}

// 深度优先遍历
void DFS(MGraph* G, int v, bool visited[]) {
    visited[v] = true;
    printf("%d ", v);
    for (int j = 0; j < G->vexnum; j++) {
        if (G->edges[v][j] == 1 && !visited[j]) {
            DFS(G, j, visited);
        }
    }
}

int main() {
    MGraph G;
    InitMGraph(&G);
    BFS(&G, 0);
    bool visited[MAX_VERTEX_NUM] = { false };
    DFS(&G, 0, visited);
    printf("\n");
    return 0;
}

### 回答2：
邻接表和邻接矩阵是两种常见的图的表示方法，可以用于实现图的广度遍历和深度遍历的算法。

邻接表是一种链表的形式，用于表示图的结构。对于每个顶点，将其邻接的顶点用链表链接起来，形成一个邻接表。邻接矩阵则是一个二维矩阵，用于表示图的连接关系。

广度遍历（BFS）是从图的某个节点出发，先访问其所有邻接节点，再按照广度优先的顺序遍历所有未被访问的邻接节点。具体实现方法如下：
1. 创建一个队列，将起始节点入队。
2. 从队列中取出一个节点，访问该节点并标记为已访问。
3. 遍历该节点的邻接节点，将未被访问的节点入队。
4. 重复步骤2和3，直到队列为空。

深度遍历（DFS）是从图的某个节点出发，先访问其一个邻接节点，再依次访问该节点的邻接节点，直到无法继续访问为止，然后回溯到上一个节点，继续访问下一个未被访问的邻接节点。具体实现方法如下：
1. 创建一个栈，将起始节点压栈。
2. 从栈中弹出一个节点，访问该节点并标记为已访问。
3. 遍历该节点的邻接节点，将未被访问的节点压栈。
4. 重复步骤2和3，直到栈为空。

无论使用邻接表还是邻接矩阵都可以实现图的广度遍历和深度遍历。对于邻接表，广度遍历可以通过链表的特性实现邻居节点的访问顺序；深度遍历可以通过递归或者栈的方式实现节点的回溯。对于邻接矩阵，广度遍历可以通过遍历矩阵的行实现邻居节点的访问顺序；深度遍历可以通过递归或者栈的方式实现节点的回溯。

综上所述，无论使用邻接表还是邻接矩阵，我们都可以实现图的广度遍历和深度遍历的算法。

### 回答3：
邻接表和邻接矩阵是两种常用的存储图的方法，它们可以用于实现图的广度遍历和深度遍历。

邻接表是一种链表的数据结构，用于表示图中各个顶点之间的关系。对于每个顶点，邻接表中存储了与之相邻顶点的指针。通过邻接表实现图的广度遍历时，可以使用队列来存储待访问的顶点。首先将起始顶点放入队列中，然后依次访问队列中的顶点，并将其未访问过的相邻顶点放入队列中。直到队列为空时，广度遍历结束。

邻接矩阵是一个二维数组，用于表示图中各个顶点之间的关系。对于顶点i和顶点j，邻接矩阵中的元素A[i][j]表示它们之间的边。通过邻接矩阵实现图的深度遍历时，可以使用递归或栈来存储待访问的顶点。首先将起始顶点放入栈中，然后依次访问栈顶的顶点，并将其未访问过的相邻顶点放入栈中。直到栈为空时，深度遍历结束。

无论使用邻接表还是邻接矩阵，图的广度遍历和深度遍历的时间复杂度都是O(V+E)，其中V为顶点数，E为边数。

邻接表的优点是可以节省空间，适用于稀疏图。而邻接矩阵的优点是查找两个顶点之间是否有边的时间复杂度为O(1)，适用于稠密图。选择哪种方法实现图的广度遍历和深度遍历取决于具体问题的要求和图的类型。

邻接矩阵和邻接表谁更重要

邻接矩阵和邻接表在图的存储和表示方面各有优势，而其重要性取决于具体的应用场景和需求。

邻接矩阵的优点是能够以O(1)的时间复杂度查询两个节点之间是否存在边，适用于需要频繁进行节点连接性查询的场景。此外，邻接矩阵还可以直观地展示整个图的结构，便于可视化和分析。

邻接表的优点是节省空间，在稀疏图（边相对较少）的情况下，可以大大减少存储空间的消耗。同时，邻接表也更适合处理一些图算法，如深度优先搜索（DFS）和广度优先搜索（BFS），因为它直接记录了每个节点的相邻节点信息。

因此，邻接矩阵和邻接表都是重要的图的存储方式，选择哪种方式取决于具体的应用需求。一般来说，在空间有限且图较稀疏的情况下，邻接表更具优势；而在需要频繁进行连接性查询的场景下，邻接矩阵更为方便。