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

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

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

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

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

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

相关问题

图的邻接矩阵表示及搜索

图的邻接矩阵是一种常见的图的表示方法，它是一个二维矩阵，其中每个元素表示图中两个节点之间的关系。对于一个有 $n$ 个节点的无向图，邻接矩阵 $A$ 的大小为 $n \times n$，其中 $A_{i,j}=1$ 表示节点 $i$ 和节点 $j$ 之间有一条边，$A_{i,j}=0$ 表示节点 $i$ 和节点 $j$ 之间没有边。对于一个有向图，则需要使用有向邻接矩阵，其中 $A_{i,j}=1$ 表示从节点 $i$ 到节点 $j$ 有一条有向边。

基于邻接矩阵，可以进行深度优先搜索（DFS）和广度优先搜索（BFS）。DFS 从一个起点出发，尽可能深地搜索图，直到无法再继续下去，然后回退到前一个节点，继续搜索其他未被访问的节点。BFS 则从起点开始，逐层扩展搜索范围，直到找到目标节点或者所有节点都被访问过。

具体实现时，可以使用一个布尔数组来记录节点是否被访问过，以避免重复访问。对于 DFS，需要使用一个栈来存储已经访问过的节点，以便在回溯时能够回到前一个节点。对于 BFS，需要使用一个队列来存储待访问的节点，以便按照层次顺序进行搜索。

邻接矩阵表示法的优点是方便进行图的遍历和搜索，缺点是空间复杂度较高，当图的规模较大时，会占用较多的内存。此外，如果图中边的数量较少，邻接矩阵中很多元素都是 0，会浪费一定的空间。

c语言，使用邻接矩阵创建一个图，并对这个图进行深度优先遍历和广度优先遍历

下面是使用邻接矩阵创建一个图，并对这个图进行深度优先遍历和广度优先遍历的C语言代码示例：

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

#define MAXV 100 // 最大顶点数

int visited[MAXV]; // 标记顶点是否被访问过

// 邻接矩阵表示法
typedef struct {
    int edges[MAXV][MAXV]; // 邻接矩阵
    int n; // 顶点数
} Graph;

// 初始化图
void initGraph(Graph *g, int n) {
    g->n = n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            g->edges[i][j] = 0; // 初始化邻接矩阵
        }
    }
}

// 添加边
void addEdge(Graph *g, int u, int v) {
    g->edges[u][v] = 1;
    g->edges[v][u] = 1; // 无向图
}

// 深度优先遍历
void dfs(Graph *g, int v) {
    visited[v] = 1; // 标记当前顶点已访问
    printf("%d ", v); // 输出当前顶点
    for (int i = 0; i < g->n; i++) {
        if (g->edges[v][i] && !visited[i]) { // 如果与当前顶点相邻且未被访问
            dfs(g, i); // 递归访问相邻顶点
        }
    }
}

// 广度优先遍历
void bfs(Graph *g, int v) {
    int queue[MAXV], front = 0, rear = 0;
    visited[v] = 1; // 标记当前顶点已访问
    printf("%d ", v); // 输出当前顶点
    queue[rear++] = v; // 将当前顶点入队
    while (front < rear) { // 队列不为空
        int u = queue[front++]; // 取出队首顶点
        for (int i = 0; i < g->n; i++) {
            if (g->edges[u][i] && !visited[i]) { // 如果与当前顶点相邻且未被访问
                visited[i] = 1; // 标记相邻顶点已访问
                printf("%d ", i); // 输出相邻顶点
                queue[rear++] = i; // 将相邻顶点入队
            }
        }
    }
}

int main() {
    Graph g;
    int n, e; // 顶点数和边数
    printf("请输入顶点数和边数：");
    scanf("%d%d", &n, &e);
    initGraph(&g, n); // 初始化图
    printf("请输入每条边的两个端点：\n");
    for (int i = 0; i < e; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        addEdge(&g, u, v); // 添加边
    }
    printf("深度优先遍历结果：");
    dfs(&g, 0); // 从顶点0开始深度优先遍历
    printf("\n广度优先遍历结果：");
    for (int i = 0; i < n; i++) {
        visited[i] = 0; // 初始化visited数组
    }
    bfs(&g, 0); // 从顶点0开始广度优先遍历
    printf("\n");
    return 0;
}

在上述代码中，我们使用一个结构体`Graph`来表示一个无向图，其中`n`表示顶点数，`edges`表示邻接矩阵。`visited`数组用来标记顶点是否被访问过。`initGraph`函数用来初始化图，`addEdge`函数用来添加边。`dfs`函数和`bfs`函数分别表示深度优先遍历和广度优先遍历。在主函数中，我们先输入顶点数和边数，然后输入每条边的两个端点，构建出图后，先从顶点0开始深度优先遍历，再从顶点0开始广度优先遍历。