C++邻接矩阵存储无向图的实现 说明：实现类模板MGraph，基本操作包括构造函数、深度优先遍历、广度优先遍历，并验证。

邻接矩阵存储无向图的实现是一种将无向图存储为矩阵的方法。它使用二维数组来表示图中顶点之间的边，其中数组中的每个元素表示从一个顶点到另一个顶点的距离。这种实现方法的优点是，可以通过两个顶点的索引快速查找他们之间是否有边，以及距离。在构造函数中，可以从文件中读取图的信息，并将其存储到矩阵中。深度优先遍历和广度优先遍历都可以使用邻接矩阵来实现，区别在于深度优先遍历和广度优先遍历使用的顶点搜索顺序不同。实现完成后，可以通过验证所构造的图和矩阵是否正确来检查是否按要求实现了图的存储。

相关问题

⑴ 建立无向图的邻接矩阵存储； ⑵ 对建立的无向图，进行深度优先遍历； 3. 实现提示 定义邻接矩阵存储的无向图结构体MGraph，在其基础上实现题目要求的图建立、深度优先遍历等基本操作。

下面是基于邻接矩阵存储的无向图结构体MGraph的定义和相应的操作实现：

#define MAX_VERTEX_NUM 100

typedef char DataType;

typedef struct {
    DataType vertex[MAX_VERTEX_NUM];    // 顶点信息
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];    // 邻接矩阵
    int vertexNum, edgeNum;    // 顶点数和边数
} MGraph;

int visited[MAX_VERTEX_NUM];    // 全局数组visited[]，初始化为0

// 创建无向图的邻接矩阵存储
void CreatGraph(MGraph *G, DataType a[], int n, int e) {
    int i, j, k;
    G->vertexNum = n;
    G->edgeNum = e;
    for (i = 0; i < G->vertexNum; i++)     // 存储顶点信息
        G->vertex[i] = a[i];
    for (i = 0; i < G->vertexNum; i++)     // 初始化邻接矩阵
        for (j = 0; j < G->vertexNum; j++)
            G->edge[i][j] = 0;
    for (k = 0; k < G->edgeNum; k++)      // 依次输入每一条边
    {
        scanf("%d%d", &i, &j);            // 输入边依附的顶点编号
        G->edge[i][j] = 1;
        G->edge[j][i] = 1;                // 置有边标志
    }
}

// 深度优先遍历
void DFraverse(MGraph *G, int v) {
    printf("%c ", G->vertex[v]);
    visited[v] = 1;
    for (int j = 0; j < G->vertexNum; j++)
        if (G->edge[v][j] == 1 && visited[j] == 0)
            DFraverse(G, j);
}

int main() {
    MGraph G;
    DataType vertex[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};
    int n = 8, e = 9;
    CreatGraph(&G, vertex, n, e);
    printf("深度优先遍历序列：");
    for (int i = 0; i < G.vertexNum; i++)
        visited[i] = 0;
    for (int i = 0; i < G.vertexNum; i++)
        if (visited[i] == 0)
            DFraverse(&G, i);
    printf("\n");
    return 0;
}

在实现中，我们先定义了一个结构体MGraph来存储无向图的邻接矩阵。然后通过CreatGraph()函数来创建无向图，该函数接受一个MGraph结构体指针，一个顶点信息数组，顶点数和边数，然后按照输入的边的信息，初始化邻接矩阵。在实现深度优先遍历的DFraverse()函数中，我们使用了递归的方式遍历所有未被访问的节点，并使用visited[]数组来标记已经访问的节点，以避免重复访问。最后，在main()函数中，我们创建了一个无向图，并通过DFraverse()函数来进行深度优先遍历，输出遍历序列。

邻接矩阵存储实现图的深度优先遍历和广度优先遍历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);
                    }
                }
            }
        }
    }
}