邻接表存储结构广度优先遍历和深度优先遍历时间复杂度详细分析

邻接表是一种常用的图的存储结构，它通过链表来表示每个节点的邻接关系。在使用邻接表存储图时，我们可以使用广度优先遍历和深度优先遍历来访问图中的所有节点。

广度优先遍历(BFS)的时间复杂度为O(V+E)，其中V为图中节点的个数，E为边的个数。具体实现过程中，BFS使用队列来存储待访问节点，每个节点仅会被访问一次。因此，BFS的时间复杂度是线性的。

深度优先遍历(DFS)的时间复杂度也为O(V+E)。DFS使用递归或栈来实现遍历，每个节点仅会被访问一次。在最坏情况下，DFS需要遍历整个图，因此时间复杂度与BFS相同。

相关问题

PTA 邻接表存储图的广度优先遍历（20 分）

### 回答1：
广度优先遍历（BFS）是一种图的遍历算法，以树的层次遍历为基础，从图的某一顶点 v 出发，依次访问 v 的各个未被访问过的邻接点，然后分别从这些邻接点出发再访问它们的邻接点，直到图中所有与 v 有路径相通的顶点都被访问为止。

邻接表是存储图的常用方法，它由一个一维数组和链表组成，数组中每个元素对应一个顶点，链表中存储该顶点的邻接点。具体实现可以参考以下代码：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 10001;
vector<int> adj[MAXN];  // 邻接表
bool vis[MAXN];         // 标记是否已访问

void BFS(int s) {
    queue<int> q;
    q.push(s);
    vis[s] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";  // 访问顶点 u
        for (int i = 0; i < adj[u].size(); i++) {  // 遍历 u 的邻接点
            int v = adj[u][i];
            if (!vis[v]) {  // 如果 v 未被访问
                q.push(v);
                vis[v] = true;
            }
        }
    }
}

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);  // 存储邻接点
        adj[v].push_back(u);
    }
    BFS(s);
    return 0;
}

代码说明：

1. `adj` 是邻接表，其中 `adj[u]` 存储顶点 `u` 的所有邻接点；
2. `vis` 是标记数组，用于标记每个顶点是否已被访问；
3. `BFS` 函数是广度优先遍历函数，其中 `s` 是起点，首先将起点入队，标记为已访问，然后不断从队首取出顶点，访问该顶点，遍历其所有邻接点，如果邻接点未被访问，则加入队列并标记为已访问。

时间复杂度：$O(n+m)$，其中 $n$ 是顶点数，$m$ 是边数。

### 回答2：
广度优先遍历（BFS）是一种图的遍历算法，用于遍历图中的所有节点。PTA 邻接表存储图的广度优先遍历的过程如下：

1. 首先创建一个队列，并将起始节点加入队列中。

2. 创建一个数组来保存已访问的节点，并将起始节点标记为已访问。

3. 当队列非空时，重复以下步骤：

- 从队列中取出一个节点，并访问该节点。

- 遍历该节点的邻接节点，并将未访问过的邻接节点加入队列中。

- 将已访问的节点标记为已访问。

4. 当队列为空时，说明遍历结束，即所有节点都已访问。

PTA 邻接表存储图的广度优先遍历的时间复杂度为 O(V+E)，其中 V 表示图中的节点数，E 表示图中的边数。由于使用了队列来保存节点，因此空间复杂度为 O(V)。

广度优先遍历可以用来解决一些与图结构相关的问题，例如判断两个节点之间是否存在路径、寻找最短路径等。通过广度优先遍历，我们可以遍历图中所有与起始节点相连的节点，并逐层向外扩展，直到遍历完所有与起始节点相连的节点，或者找到满足特定条件的节点。

需要注意的是，广度优先遍历是一种无权图最短路径算法。对于有权图的最短路径问题，需要使用其他算法，例如迪杰斯特拉算法或贝尔曼-福特算法。

### 回答3：
广度优先遍历（BFS）是一种用于图的遍历算法，通过广度的方式逐层遍历图中的节点。在PTA中，可以使用邻接表来存储图，并实现广度优先遍历。

邻接表是一种图的表示形式，它由一个由链表组成的数组构成。数组的大小等于图中节点的数量，每个数组元素对应一个节点，链表中存储了与该节点相邻的节点。

广度优先遍历的基本思想是从图中的某个节点开始，依次访问它的相邻节点，然后再依次访问相邻节点的相邻节点，以此类推，直到所有节点都被访问。为了记录哪些节点已经访问过，可以使用一个辅助数组visited来标记节点的访问状态。

具体实现广度优先遍历的步骤如下：

1. 创建一个空的辅助队列queue，并将起始节点入队，同时标记起始节点为已访问。
2. 当队列不为空时，循环执行以下步骤：
- 从队列中取出一个节点，访问该节点。
- 获取该节点的邻居节点列表。
- 遍历邻居节点列表，对于每个邻居节点：
- 如果邻居节点没有被访问过，则将邻居节点入队，并标记为已访问。
3. 遍历结束后，所有节点都被访问过。

使用邻接表存储图的广度优先遍历可以按照上述步骤进行实现。只需要根据邻接表中节点的关系，依次访问每个节点的邻居节点并进行相应操作即可。遍历结束后，可以得到图中所有节点的遍历顺序。

总之，PTA邻接表存储图的广度优先遍历是一种通过广度方式逐层遍历图中节点的算法。通过使用辅助队列和visited数组，可以实现该算法。

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