(标签-矩阵|关键词-无向图)

Question

图的存储
时间限制：2s
内存限制：262M
题目描述
给定一个 n个顶点 m条边的无向图。请以邻接矩阵和邻接表的形式输出这一张图。
【输入格式】
第一行输入两个正整数 n和 m，表示图的顶点数和边数。

第二行开始，往后 m行，每行输入两个以空格隔开的正整数u,v，表示u,v顶点之间有一条边直接相连。
【输出格式】
首先输出 n行 n列的矩阵，以空格隔开每一行之间的数表示邻接矩阵。第 i行第 j列的数为 1则表示顶点 i,j之间有一条边直接相连；若为 0则表示没有直接相连的边。

再往后输出 n行。第 i行首先先输出一个整数 d i，表示这个顶点的度数，再按照从小到大的顺序，依次输出与顶点 i直接相连的所有顶点。

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

针对你提出的问题，以下是具体的操作步骤和代码实现建议：

1. 理解题目要求：

   • 题目要求使用邻接矩阵和邻接表两种方式来表示一个无向图。

2. 输入处理：

   • 使用cin来读取顶点数n和边数m。
   • 使用循环读取每条边的两个顶点u和v。

3. 邻接矩阵构建：

   • 声明一个n x n的二维数组matrix，初始化所有元素为0。
   • 遍历每条边，将matrix[u][v]和matrix[v][u]设置为1。

4. 邻接表构建：

   • 声明一个vector<vector<int>>的邻接表adjList，其中每个内部vector表示一个顶点的邻接点列表。
   • 遍历每条边，将v添加到顶点u的邻接点列表中，反之亦然。

5. 度数计算：

   • 对于每个顶点i，遍历其邻接表，计算列表中的元素数量，即为度数。

6. 输出格式：

   • 先输出邻接矩阵，使用嵌套循环遍历matrix，每行输出后换行。
   • 然后输出邻接表，对于每个顶点i，先输出度数，然后按顺序输出邻接点。

7. 代码实现：

   • 使用C++的vector来存储邻接表，使用二维数组或vector<vector<int>>来存储邻接矩阵。

8. 测试验证：

   • 编写测试用例，包括但不限于：
     • 只有一个顶点和一条边的情况。
     • 完全图的情况。
     • 没有边的情况。
     • 顶点数和边数很大的情况。

以下是C++代码实现的示例：

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

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> adjList(n);
    vector<int> degrees(n, 0);
    vector<vector<int>> matrix(n, vector<int>(n, 0));

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u--; v--; // 将顶点编号从1转换为从0开始
        matrix[u][v] = 1;
        matrix[v][u] = 1;
        adjList[u].push_back(v);
        adjList[v].push_back(u);
        degrees[u]++;
        degrees[v]++;
    }

    // 输出邻接矩阵
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }

    // 输出邻接表
    for (int i = 0; i < n; ++i) {
        cout << degrees[i] << " ";
        for (int j : adjList[i]) {
            cout << j + 1 << " "; // 将顶点编号从0转换回1
        }
        cout << endl;
    }

    return 0;
}

请注意，这段代码是一个基本的实现，可能需要根据实际问题进行调整和优化。在实际应用中，还需要考虑错误处理和边界条件。