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

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

广度优先搜索（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)，适用于稠密图。选择哪种方法实现图的广度遍历和深度遍历取决于具体问题的要求和图的类型。

用图的邻接矩阵表示法实现图的深度优先搜索和广度优先搜索

图的邻接矩阵表示法是一种常见的图的表示方法，可以用来实现图的深度优先搜索和广度优先搜索。

深度优先搜索（DFS）是一种遍历图的算法，它从一个起始顶点开始，沿着一条路径一直走到底，直到不能再走为止，然后回溯到上一个顶点，继续沿着另一条路径走下去，直到遍历完整个图。DFS可以用递归或栈来实现。

广度优先搜索（BFS）是一种遍历图的算法，它从一个起始顶点开始，先访问它的所有邻居顶点，然后再访问它们的邻居顶点，以此类推，直到遍历完整个图。BFS可以用队列来实现。

具体实现时，可以先根据图的邻接矩阵表示法构建出图的邻接矩阵，然后根据DFS或BFS的算法思想，遍历整个图。在遍历过程中，可以使用一个数组来记录每个顶点的状态，例如是否已经被访问过等。遍历结束后，可以输出遍历的结果，例如每个顶点的访问顺序等。

需要注意的是，图的邻接矩阵表示法只适用于稠密图，对于稀疏图，应该使用邻接表或邻接多重表来表示。此外，在实际应用中，还需要考虑图的大小和算法的时间复杂度等因素。