邻接矩阵存储实现图的深度优先遍历和广度优先遍历c语言

以下是C++实现图的邻接矩阵存储和深度优先遍历以及广度优先遍历的代码示例：

1. 邻接矩阵存储

#define MAXVEX 100 // 最大顶点数
#define INFINITY 65535 // 用65535来代表无穷大

typedef struct {
    int vexs[MAXVEX]; // 存储顶点的数组
    int arc[MAXVEX][MAXVEX]; // 存储边的二维数组
    int numVertexes, numEdges; // 图中当前的顶点数和边数
} MGraph;

// 创建邻接矩阵图
void CreateMGraph(MGraph *G) {
    int i, j, k, w;
    printf("请输入顶点数和边数：\n");
    scanf("%d,%d", &G->numVertexes, &G->numEdges);
    for (i = 0; i < G->numVertexes; i++) {
        printf("请输入第%d个顶点：", i + 1);
        scanf("%d", &G->vexs[i]);
    }
    for (i = 0; i < G->numVertexes; i++) {
        for (j = 0; j < G->numVertexes; j++) {
            G->arc[i][j] = INFINITY; // 初始化邻接矩阵
        }
    }
    for (k = 0; k < G->numEdges; k++) {
        printf("请输入边（vi，vj）的下标i，下标j和权值w：\n");
        scanf("%d,%d,%d", &i, &j, &w);
        G->arc[i][j] = w;
        G->arc[j][i] = G->arc[i][j]; // 无向图对称
    }
}

2. 深度优先遍历

bool visited[MAXVEX]; // 记录顶点是否被访问过

// 邻接矩阵的深度优先递归算法
void DFS(MGraph G, int i) {
    int j;
    visited[i] = true;
    printf("%d ", G.vexs[i]);
    for (j = 0; j < G.numVertexes; j++) {
        if (G.arc[i][j] != INFINITY && !visited[j]) {
            DFS(G, j);
        }
    }
}

// 邻接矩阵的深度遍历操作
void DFSTraverse(MGraph G) {
    int i;
    for (i = 0; i < G.numVertexes; i++) {
        visited[i] = false;
    }
    for (i = 0; i < G.numVertexes; i++) {
        if (!visited[i]) {
            DFS(G, i);
        }
    }
}

3. 广度优先遍历

// 邻接矩阵的广度遍历算法
void BFSTraverse(MGraph G) {
    int i, j;
    queue<int> Q;
    for (i = 0; i < G.numVertexes; i++) {
        visited[i] = false;
    }
    for (i = 0; i < G.numVertexes; i++) {
        if (!visited[i]) {
            visited[i] = true;
            printf("%d ", G.vexs[i]);
            Q.push(i);
            while (!Q.empty()) {
                int k = Q.front();
                Q.pop();
                for (j = 0; j < G.numVertexes; j++) {
                    if (G.arc[k][j] != INFINITY && !visited[j]) {
                        visited[j] = true;
                        printf("%d ", G.vexs[j]);
                        Q.push(j);
                    }
                }
            }
        }
    }
}