用DEVC++写一个程序，依次从有向图中的每个顶点广度优先搜索遍历操作；邻接矩阵作为存储结构。算法思想： (1) 定义图的顺序存储结构； (2) 创建有向图，采用邻接矩阵表示（调用CreateUDG函数实现），具体实现如下： 输入图的顶点数和边数； 依次输入顶点的信息存入顶点表中； 初始化邻接矩阵，使每个权值初始化为0； 构造邻接矩阵；（需调用LocateVex函数获取顶点在顶点表中的下标） (3) 依次从每个顶点进行广度优先搜索，并输出访问序列（调用BFSTraverse函数实现，借助队列实现；另需调用相关函数实现获取第一个和下一个邻接点的操作）。 输入说明： 第一行输入图的顶点数n和边数m； 第二行依次输入n个顶点的数据； 接下来m行的每行输入一条边的信息。 输出说明： 输出n行，每行输出从第i(0≤i＜n)个顶点广度优先搜索的访问序列，序列中的连通分量用{}括起来，无空格间隔，{}为英文半角的符号。

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

#define MAXVEX 100

// 定义图的邻接矩阵存储结构
typedef struct {
    char vexs[MAXVEX];      // 存储顶点信息
    int arc[MAXVEX][MAXVEX]; // 邻接矩阵
    int numVertexes, numEdges;  // 图中当前的顶点数和边数
} MGraph;

// 获取顶点在顶点表中的下标
int LocateVex(MGraph G, char ch) {
    for (int i = 0; i < G.numVertexes; ++i) {
        if (G.vexs[i] == ch) {
            return i;
        }
    }
    return -1;
}

// 创建有向图，采用邻接矩阵表示
void CreateDG(MGraph &G) {
    cout << "请输入顶点数和边数：";
    cin >> G.numVertexes >> G.numEdges;
    cout << "请输入顶点信息：";
    for (int i = 0; i < G.numVertexes; ++i) {
        cin >> G.vexs[i];
    }
    // 初始化邻接矩阵，使每个权值初始化为0
    for (int i = 0; i < G.numVertexes; ++i) {
        for (int j = 0; j < G.numVertexes; ++j) {
            G.arc[i][j] = 0;
        }
    }
    // 构造邻接矩阵
    for (int k = 0; k < G.numEdges; ++k) {
        char start, end;
        cout << "请输入边（vi, vj）的顶点序号和权重：" << endl;
        cin >> start >> end;
        int i = LocateVex(G, start);
        int j = LocateVex(G, end);
        G.arc[i][j] = 1;
    }
}

// 获取第一个邻接点
int FirstAdjVex(MGraph G, int v) {
    for (int i = 0; i < G.numVertexes; ++i) {
        if (G.arc[v][i] == 1) {
            return i;
        }
    }
    return -1;
}

// 获取下一个邻接点
int NextAdjVex(MGraph G, int v, int w) {
    for (int i = w + 1; i < G.numVertexes; ++i) {
        if (G.arc[v][i] == 1) {
            return i;
        }
    }
    return -1;
}

// 广度优先搜索遍历操作
void BFS(MGraph G, int i, bool* visited) {
    queue<int> Q;
    cout << "{";
    visited[i] = true;
    cout << G.vexs[i];
    Q.push(i);
    while (!Q.empty()) {
        int j = Q.front();
        Q.pop();
        for (int k = FirstAdjVex(G, j); k >= 0; k = NextAdjVex(G, j, k)) {
            if (!visited[k]) {
                visited[k] = true;
                cout << G.vexs[k];
                Q.push(k);
            }
        }
    }
    cout << "}" << endl;
}

// 依次从每个顶点进行广度优先搜索，并输出访问序列
void BFSTraverse(MGraph G) {
    bool visited[MAXVEX] = {false};
    for (int i = 0; i < G.numVertexes; ++i) {
        if (!visited[i]) {
            BFS(G, i, visited);
        }
    }
}

int main() {
    MGraph G;
    CreateDG(G);
    BFSTraverse(G);
    return 0;
}