本文共 1584 字，大约阅读时间需要 5 分钟。

数据结构中对于图的存储主要有三种方式，其中邻接矩阵和邻接表是最常用的。以下将以C++语言为例，介绍如何使用邻接矩阵存储图并实现广度优先搜索遍历。

使用邻接矩阵存储图

邻接矩阵是一种二维数组，其中graph[u][v]用于存储从顶点u到顶点v的边信息。在无向图中，需要标记graph[u][v]和graph[v][u]为1，表示顶点u与顶点v相连。在有权图中，邻接矩阵中的值可以存储边的权重。对于有向有权图，邻接矩阵的操作更加方便，只需在输入数据时记录起点和终点对应的权重即可。

实现广度优先搜索

广度优先搜索（BFS）是一种图遍历算法，常用于寻找最短路径。实现过程如下：

图的具体实现

以下是基于邻接矩阵的图存储和BFS实现代码示例：

#include 
   
    
#include 
    
     
using namespace std;
#define maxSize 1000
#define INF 100000000
bool inq[maxSize] = {false};
int n, edges, G[maxSize][maxSize];
void bfs(int u) {
    queue
     
       q;
    q.push(u);
    inq[u] = true;
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        for (int v = 0; v < n; v++) {
            if (!inq[v] && G[current][v] != INF) {
                q.push(v);
                inq[v] = true;
            }
        }
    }
}
int main() {
    cout << "输入图中的顶点数: ";
    cin >> n;
    // 初始化邻接矩阵为无穷大
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            G[i][j] = INF;
        }
    }
    cout << endl;
    cout << "输入图中的边数: ";
    cin >> edges;
    cout << endl;
    // 读取边信息并填充邻接矩阵
    int u, v, weight;
    for (int i = 0; i < edges; i++) {
        cin >> u >> v >> weight;
        G[u][v] = weight;
    }
    bfs(0); // 从顶点0开始广度优先搜索
    return 0;
}
     
    
   

代码解释

通过上述方法，可以实现图的存储和广度优先搜索遍历。代码结构清晰，易于理解和修改，适合用于图的基本操作研究。