21.图遍历的演示 【问题描述】 很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演 示在连通的无向图上访问全部结点的操作。 【基本要求】 以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。以 用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边 集。

好的，以下是一个可能的实现方案：

1. 定义邻接多重表的数据结构，包括结点和边的数据结构。

// 结点数据结构
struct Node {
    int data; // 结点编号
    Edge *first_edge; // 指向第一条依附该结点的边
};

// 边数据结构
struct Edge {
    int weight; // 边的权重
    int ivex, jvex; // 顶点ivex和jvex是该边的两个端点
    Edge *ilink, *jlink; // 分别指向ivex和jvex的下一条边
};

2. 读取文件中的图数据，构建邻接多重表。

// 读取文件，构建邻接多重表
void buildGraph(string fileName) {
    // 读取文件，构建邻接多重表
    // ...
}

3. 实现深度优先遍历算法，并输出遍历序列和生成树的边集。

// 深度优先遍历
void DFS(int v, bool visited[], vector<int>& order, vector<Edge*>& tree) {
    visited[v] = true;
    order.push_back(v);
    for (Edge* e = adjList[v].first_edge; e != nullptr; e = (e->ivex == v ? e->ilink : e->jlink)) {
        int w = (e->ivex == v ? e->jvex : e->ivex);
        if (!visited[w]) {
            tree.push_back(e);
            DFS(w, visited, order, tree);
        }
    }
}

// 遍历图并输出遍历序列和生成树的边集
void traverseGraph(int start) {
    bool visited[MAX_SIZE] = {false};
    vector<int> order;
    vector<Edge*> tree;
    DFS(start, visited, order, tree);
    cout << "深度优先遍历序列：";
    for (int v : order) {
        cout << v << " ";
    }
    cout << endl << "深度优先生成树边集：" << endl;
    for (Edge* e : tree) {
        cout << e->ivex << " " << e->jvex << endl;
    }
}

4. 实现广度优先遍历算法，并输出遍历序列和生成树的边集。

// 广度优先遍历
void BFS(int v, bool visited[], vector<int>& order, vector<Edge*>& tree) {
    queue<int> q;
    visited[v] = true;
    q.push(v);
    while (!q.empty()) {
        int w = q.front();
        q.pop();
        order.push_back(w);
        for (Edge* e = adjList[w].first_edge; e != nullptr; e = (e->ivex == w ? e->ilink : e->jlink)) {
            int u = (e->ivex == w ? e->jvex : e->ivex);
            if (!visited[u]) {
                visited[u] = true;
                tree.push_back(e);
                q.push(u);
            }
        }
    }
}

// 遍历图并输出遍历序列和生成树的边集
void traverseGraph(int start) {
    bool visited[MAX_SIZE] = {false};
    vector<int> order;
    vector<Edge*> tree;
    BFS(start, visited, order, tree);
    cout << "广度优先遍历序列：";
    for (int v : order) {
        cout << v << " ";
    }
    cout << endl << "广度优先生成树边集：" << endl;
    for (Edge* e : tree) {
        cout << e->ivex << " " << e->jvex << endl;
    }
}

完整代码可能会比较长，这里只是列出了主要的实现思路。希望对您有所帮助。