用C++写邻接矩阵或邻接表创建图然后进行DFS和BFS操作的一个程序

下面是一个使用邻接表创建图并进行DFS和BFS操作的C++程序：

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

// 定义图的结构体
struct Graph {
    int V;  // 图的顶点数
    vector<int> *adj;  // 指向邻接表的指针
};

// 创建一个新的图
Graph* createGraph(int V) {
    Graph* graph = new Graph;
    graph->V = V;
    graph->adj = new vector<int>[V];
    return graph;
}

// 增加一条边到图中
void addEdge(Graph* graph, int src, int dest) {
    graph->adj[src].push_back(dest);  // 添加 dest 到 src 的邻接表
    graph->adj[dest].push_back(src);  // 添加 src 到 dest 的邻接表
}

// 深度优先搜索
void DFS(Graph* graph, int v, bool visited[]) {
    visited[v] = true;  // 标记当前节点为已访问
    cout << v << " ";  // 输出当前节点

    // 遍历所有邻居节点
    for (auto i = graph->adj[v].begin(); i != graph->adj[v].end(); ++i) {
        if (!visited[*i]) {
            DFS(graph, *i, visited);  // 递归遍历邻居节点
        }
    }
}

// 广度优先搜索
void BFS(Graph* graph, int v, bool visited[]) {
    queue<int> q;  // 创建一个队列用于存储待访问的节点
    visited[v] = true;  // 标记当前节点为已访问
    q.push(v);  // 将当前节点加入队列

    while (!q.empty()) {
        v = q.front();  // 取出队列中的头节点
        cout << v << " ";  // 输出头节点
        q.pop();  // 弹出头节点

        // 遍历所有邻居节点
        for (auto i = graph->adj[v].begin(); i != graph->adj[v].end(); ++i) {
            if (!visited[*i]) {
                visited[*i] = true;  // 标记当前邻居节点为已访问
                q.push(*i);  // 将当前邻居节点加入队列
            }
        }
    }
}

int main() {
    Graph* graph = createGraph(6);  // 创建一个6个节点的图
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);
    addEdge(graph, 3, 5);

    bool visited[6] = {false};  // 创建一个布尔类型的数组用于标记节点是否已访问

    cout << "DFS: ";
    DFS(graph, 0, visited);
    cout << endl;

    for (int i = 0; i < 6; ++i) {
        visited[i] = false;  // 重置visited数组
    }

    cout << "BFS: ";
    BFS(graph, 0, visited);
    cout << endl;

    return 0;
}

该程序使用邻接表创建了一个6个节点的图，并且实现了DFS和BFS操作。在DFS和BFS操作中，我们使用了一个布尔类型的数组`visited`来标记每个节点是否已经被访问过。这个数组在每次遍历之前都会被重置。