数据结构图的基本操作用C++写

以下是数据结构图的基本操作的C++代码实现：

1. 创建图

const int MAXN = 100; // 图的最大节点数
vector<int> G[MAXN]; // 使用 vector 存储邻接表
int n; // 图的节点数

void createGraph() {
    cout << "请输入节点数：";
    cin >> n;
    cout << "请输入边数：";
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        cout << "请输入第 " << i+1 << " 条边（起点 终点）：";
        int u, v;
        cin >> u >> v;
        G[u].push_back(v); // 添加一条从 u 到 v 的边
    }
}

2. 遍历图（深度优先遍历）

bool vis[MAXN]; // 标记节点是否被访问过

void dfs(int u) {
    vis[u] = true; // 标记节点 u 被访问过
    cout << u << " "; // 输出节点 u
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!vis[v]) { // 如果节点 v 没有被访问过，就递归访问它
            dfs(v);
        }
    }
}

void traverseGraph() {
    memset(vis, false, sizeof(vis)); // 将 vis 数组初始化为 false
    for (int u = 1; u <= n; u++) {
        if (!vis[u]) { // 如果节点 u 没有被访问过，就从节点 u 开始遍历整个图
            dfs(u);
        }
    }
}

3. 查找图中两个节点之间是否存在路径（广度优先遍历）

bool bfs(int s, int t) {
    queue<int> q;
    bool vis[MAXN] = {0}; // 标记节点是否被访问过
    q.push(s);
    vis[s] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i];
            if (!vis[v]) {
                if (v == t) return true; // 找到了从 s 到 t 的路径
                q.push(v);
                vis[v] = true;
            }
        }
    }
    return false; // 没有找到从 s 到 t 的路径
}

void findPath() {
    cout << "请输入要查找的两个节点（起点 终点）：";
    int s, t;
    cin >> s >> t;
    if (bfs(s, t)) {
        cout << "存在从 " << s << " 到 " << t << " 的路径" << endl;
    } else {
        cout << "不存在从 " << s << " 到 " << t << " 的路径" << endl;
    }
}

注意事项：

1. 在使用 vector 存储邻接表时，不需要预先指定数组大小，因为 vector 会自动扩容。
2. 在使用 memset 函数将一个数组初始化为某个值时，需要先引入头文件 `<cstring>`。
3. 在使用队列时，需要先引入头文件 `<queue>`。