邻接矩阵存储方式实现图的深度遍历和广度遍历

邻接矩阵是一种常见的图的存储方式，可以用来实现图的深度遍历和广度遍历。下面是C++实现邻接矩阵存储方式实现图的深度遍历和广度遍历的示例代码：

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

#define MaxVertexNum 100 // 最大顶点数设为100
#define INFINITY 65535   // 用65535来代表∞

typedef int Vertex; // 用顶点下标表示顶点，为整型
typedef int WeightType; // 边的权值设为整型
typedef char DataType; // 顶点存储的数据类型设为字符型

// 边的定义
typedef struct ENode *PtrToENode;
struct ENode {
    Vertex V1, V2;      // 有向边<V1, V2>
    WeightType Weight;  // 权重
};
typedef PtrToENode Edge;

// 图的定义
typedef struct GNode *PtrToGNode;
struct GNode {
    int Nv; // 顶点数
    int Ne; // 边数
    WeightType G[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
    DataType Data[MaxVertexNum]; // 存顶点的数据
};
typedef PtrToGNode MGraph;

// 初始化一个有VertexNum个顶点但没有边的图
Graph CreateGraph(int VertexNum)
{
    MGraph Graph = new GNode;
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    // 初始化邻接矩阵
    for (Vertex V = 0; V < Graph->Nv; V++)
        for (Vertex W = 0; W < Graph->Nv; W++)
            Graph->G[V][W] = INFINITY;
    return Graph;
}

// 插入边
void InsertEdge(MGraph Graph, Edge E)
{
    Graph->G[E->V1][E->V2] = E->Weight;
    // 若是无向图，还要插入边<V2, V1>
    Graph->G[E->V2][E->V1] = E->Weight;
}

// 深度优先遍历DFS
bool Visited[MaxVertexNum] = { false }; // 访问标志数组
void DFS(MGraph Graph, Vertex V, void (*Visit)(Vertex))
{
    // 访问顶点V
    Visit(V);
    Visited[V] = true;
    // 对V的每个邻接点W递归调用DFS
    for (Vertex W = 0; W < Graph->Nv; W++)
        if (Graph->G[V][W] != INFINITY && !Visited[W])
            DFS(Graph, W, Visit);
}

// 广度优先遍历BFS
void BFS(MGraph Graph, Vertex S, void (*Visit)(Vertex))
{
    queue<Vertex> Q;
    Visit(S);
    Visited[S] = true;
    Q.push(S);
    while (!Q.empty()) {
        Vertex V = Q.front(); Q.pop();
        for (Vertex W = 0; W < Graph->Nv; W++)
            if (Graph->G[V][W] != INFINITY && !Visited[W]) {
                Visit(W);
                Visited[W] = true;
                Q.push(W);
            }
    }
}

// 访问顶点，输出顶点的下标
void Visit(Vertex V)
{
    cout << V << " ";
}

int main()
{
    MGraph Graph = CreateGraph(5);
    Edge E = new ENode;
    E->V1 = 0; E->V2 = 1; E->Weight = 1; InsertEdge(Graph, E);
    E->V1 = 0; E->V2 = 2; E->Weight = 1; InsertEdge(Graph, E);
    E->V1 = 1; E->V2 = 2; E->Weight = 1; InsertEdge(Graph, E);
    E->V1 = 1; E->V2 = 3; E->Weight = 1; InsertEdge(Graph, E);
    E->V1 = 2; E->V2 = 4; E->Weight = 1; InsertEdge(Graph, E);
    E->V1 = 3; E->V2 = 4; E->Weight = 1; InsertEdge(Graph, E);

    cout << "DFS: ";
    DFS(Graph, 0, Visit);
    cout << endl;

    for (Vertex V = 0; V < Graph->Nv; V++)
        Visited[V] = false; // 重置访问标志

    cout << "BFS: ";
    BFS(Graph, 0, Visit);
    cout << endl;

    return 0;
}