C++创建图采用深度优先遍历算法和广度优先遍历算法进行遍历

C++创建图可以使用邻接矩阵或邻接表两种方式。接下来我会简单介绍一下使用邻接矩阵和邻接表创建图，并使用深度优先遍历算法和广度优先遍历算法进行遍历。

1. 邻接矩阵创建图

邻接矩阵是一个二维数组，其中每个元素表示两个顶点之间是否有边相连。如果有，则为1，否则为0。

首先需要定义一个图类，其中包含一个邻接矩阵和图的顶点数。

#define MAX_VERTEX_NUM 100
typedef char VertexType;
typedef int EdgeType;

class Graph {
public:
    Graph(int vertexNum); // 构造函数
    ~Graph(); // 析构函数
    void addEdge(int v1, int v2); // 添加边
    void DFS(int start); // 深度优先遍历
    void BFS(int start); // 广度优先遍历
private:
    int vertexNum; // 图的顶点数
    VertexType vertex[MAX_VERTEX_NUM]; // 顶点集合
    EdgeType edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    bool visited[MAX_VERTEX_NUM]; // 记录节点是否被遍历过
};

接下来实现构造函数和添加边的函数。

Graph::Graph(int vertexNum) {
    this->vertexNum = vertexNum;
    for(int i = 0; i < vertexNum; i++) {
        for(int j = 0; j < vertexNum; j++) {
            edge[i][j] = 0; // 初始化邻接矩阵
        }
    }
}

Graph::~Graph() {}

void Graph::addEdge(int v1, int v2) {
    edge[v1][v2] = 1;
    edge[v2][v1] = 1; // 因为是无向图，所以需要对称存储
}

接下来实现深度优先遍历和广度优先遍历。这里使用递归实现深度优先遍历，使用队列实现广度优先遍历。

void Graph::DFS(int start) {
    visited[start] = true; // 标记节点为已遍历
    cout << vertex[start] << " "; // 输出节点
    for(int i = 0; i < vertexNum; i++) {
        if(edge[start][i] == 1 && !visited[i]) { // 如果与当前节点相邻的节点未被遍历过，则递归遍历这个节点
            DFS(i);
        }
    }
}

void Graph::BFS(int start) {
    queue<int> q;
    visited[start] = true; // 标记节点为已遍历
    q.push(start); // 将节点加入队列
    while(!q.empty()) {
        int cur = q.front(); // 取出队列首节点
        q.pop();
        cout << vertex[cur] << " "; // 输出节点
        for(int i = 0; i < vertexNum; i++) {
            if(edge[cur][i] == 1 && !visited[i]) { // 如果与当前节点相邻的节点未被遍历过，则将其标记为已遍历，并加入队列
                visited[i] = true;
                q.push(i);
            }
        }
    }
}

2. 邻接表创建图

邻接表是一个链表数组，其中每个链表表示一个顶点的邻接点。链表中的每个节点存储了一个邻接点的编号和指向下一个节点的指针。

同样需要定义一个图类，其中包含一个邻接表和图的顶点数。

typedef struct ArcNode {
    int adjvex; // 邻接点编号
    struct ArcNode* next; // 指向下一个邻接点的指针
} ArcNode;

typedef struct VNode {
    VertexType data; // 顶点数据
    ArcNode* firstArc; // 指向第一个邻接点的指针
} VNode;

class Graph {
public:
    Graph(int vertexNum); // 构造函数
    ~Graph(); // 析构函数
    void addEdge(int v1, int v2); // 添加边
    void DFS(int start); // 深度优先遍历
    void BFS(int start); // 广度优先遍历
private:
    int vertexNum; // 图的顶点数
    VNode vertex[MAX_VERTEX_NUM]; // 顶点集合
    bool visited[MAX_VERTEX_NUM]; // 记录节点是否被遍历过
};

接下来实现构造函数和添加边的函数。

Graph::Graph(int vertexNum) {
    this->vertexNum = vertexNum;
    for(int i = 0; i < vertexNum; i++) {
        vertex[i].data = 'A' + i; // 初始化顶点数据
        vertex[i].firstArc = NULL; // 初始化邻接表
    }
}

Graph::~Graph() {}

void Graph::addEdge(int v1, int v2) {
    ArcNode* node1 = new ArcNode;
    node1->adjvex = v2;
    node1->next = vertex[v1].firstArc;
    vertex[v1].firstArc = node1; // 将v2加入v1的邻接表

    ArcNode* node2 = new ArcNode;
    node2->adjvex = v1;
    node2->next = vertex[v2].firstArc;
    vertex[v2].firstArc = node2; // 将v1加入v2的邻接表
}

接下来实现深度优先遍历和广度优先遍历。这里同样使用递归实现深度优先遍历，使用队列实现广度优先遍历。

void Graph::DFS(int start) {
    visited[start] = true; // 标记节点为已遍历
    cout << vertex[start].data << " "; // 输出节点
    for(ArcNode* node = vertex[start].firstArc; node != NULL; node = node->next) {
        if(!visited[node->adjvex]) { // 如果与当前节点相邻的节点未被遍历过，则递归遍历这个节点
            DFS(node->adjvex);
        }
    }
}

void Graph::BFS(int start) {
    queue<int> q;
    visited[start] = true; // 标记节点为已遍历
    q.push(start); // 将节点加入队列
    while(!q.empty()) {
        int cur = q.front(); // 取出队列首节点
        q.pop();
        cout << vertex[cur].data << " "; // 输出节点
        for(ArcNode* node = vertex[cur].firstArc; node != NULL; node = node->next) {
            if(!visited[node->adjvex]) { // 如果与当前节点相邻的节点未被遍历过，则将其标记为已遍历，并加入队列
                visited[node->adjvex] = true;
                q.push(node->adjvex);
            }
        }
    }
}