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