图上移动 题目描述 小 A 有一张包含 n 个结点与 m 条边的无向图，结点以 1,2,…,n 标号。小 A 会从图上选择一个结点作为起点，每一步移动到某个与当前小 A 所在结点相邻的结点。对于每个结点 i（1≤i≤n），小 A 想知道从结点 i 出发恰好移动 1,2,…,k 步之后，小 A 可能位于哪些结点。由于满足条件的结点可能有很多，你只需要求出这些结点的数量。 输入格式 第一行，三个正整数 n,m,k，分别表示无向图的结点数与边数，最多移动的步数。 接下来 m 行，每行两个正整数 ui,vi，表示图中的一条连接结点 ui 与 vi 的无向边。 输出格式 共 n 行，第 i 行（1≤i≤n）包含 k 个整数，第 j 个整数（1≤j≤k）表示从结点 i 出发恰好移动 j 步之后可能位于的结点数量。 样例 输入样例 1 4 4 3 1 2 1 3 2 3 3 4 输出样例 1 2 4 4 2 4 4 3 3 4 1 3 3 数据范围 对于 20% 的测试点，保证 k=1。 对于另外 20% 的测试点，保证 1≤n≤50，1≤m≤50。 对于所有测试点，保证 1≤n≤500，1≤m≤500，1≤k≤20，1≤ui,vi≤n。 我要c++代码

### C++ 实现无向图上的 BFS 和 DFS 以下是基于邻接矩阵和邻接表两种方式实现的无向图 BFS 和 DFS 的代码示例。 #### 基于邻接矩阵的 BFS 和 DFS ```cpp #include <iostream> #include <vector> #include <queue> using namespace std; void dfs(int v, vector<vector<int>> &adjMatrix, vector<bool> &visited) { cout << char('A' + v) << " "; // 打印当前访问的节点 visited[v] = true; // 标记已访问 for (int i = 0; i < adjMatrix.size(); ++i) { // 遍历所有可能的邻居 if (!visited[i] && adjMatrix[v][i]) { // 如果未访问且存在边 dfs(i, adjMatrix, visited); // 继续深搜 } } } void bfs(int start, vector<vector<int>> &adjMatrix, vector<bool> &visited) { queue<int> q; q.push(start); visited[start] = true; // 起始点标记为已访问 while (!q.empty()) { int current = q.front(); q.pop(); cout << char('A' + current) << " "; // 打印当前访问的节点 for (int i = 0; i < adjMatrix.size(); ++i) { // 遍历所有可能的邻居 if (!visited[i] && adjMatrix[current][i]) { // 如果未访问且存在边 q.push(i); visited[i] = true; // 标记为已访问 } } } } int main() { int n, m; cin >> n >> m; // 输入顶点数和边数 vector<char> vertices(n); for (int i = 0; i < n; ++i) { cin >> vertices[i]; // 输入顶点信息 } vector<vector<int>> adjMatrix(n, vector<int>(n, 0)); // 初始化邻接矩阵 for (int i = 0; i < m; ++i) { char u, v; cin >> u >> v; // 输入边的信息 int idx_u = u - 'A'; int idx_v = v - 'A'; adjMatrix[idx_u][idx_v] = adjMatrix[idx_v][idx_u] = 1; // 设置无向边 } vector<bool> visited(n, false); cout << "DFS Traversal: "; dfs(0, adjMatrix, visited); // 从第一个顶点开始深搜 cout << endl; fill(visited.begin(), visited.end(), false); // 重置访问状态 cout << "BFS Traversal: "; bfs(0, adjMatrix, visited); // 从第一个顶点开始广搜 cout << endl; return 0; } ``` --- #### 基于邻接表的 BFS 和 DFS ```cpp #include <iostream> #include <vector> #include <queue> #include <list> using namespace std; // 定义邻接表结构 struct Graph { int V; // 顶点数量 list<int> *adjList; // 邻接列表数组 Graph(int V) : V(V), adjList(new list<int>[V]) {} // 构造函数初始化邻接表 ~Graph() { delete[] adjList; } // 析构函数释放内存 void addEdge(int u, int v) { adjList[u].push_back(v); // 添加无向边 adjList[v].push_back(u); } }; void dfs(Graph &graph, int v, vector<bool> &visited) { cout << char('A' + v) << " "; // 打印当前访问的节点 visited[v] = true; // 标记已访问 for (auto neighbor : graph.adjList[v]) { // 遍历当前节点的所有邻居 if (!visited[neighbor]) { // 如果邻居未被访问过 dfs(graph, neighbor, visited); // 对其进行递归深搜 } } } void bfs(Graph &graph, int start, vector<bool> &visited) { queue<int> q; q.push(start); visited[start] = true; // 将起始点标记为已访问 while (!q.empty()) { int current = q.front(); q.pop(); cout << char('A' + current) << " "; // 打印当前访问的节点 for (auto neighbor : graph.adjList[current]) { // 遍历当前节点的所有邻居 if (!visited[neighbor]) { // 如果邻居未被访问过 q.push(neighbor); visited[neighbor] = true; // 标记为已访问 } } } } int main() { int n, m; cin >> n >> m; // 输入顶点数和边数 Graph g(n); vector<char> vertices(n); for (int i = 0; i < n; ++i) { cin >> vertices[i]; // 输入顶点信息 } for (int i = 0; i < m; ++i) { char u, v; cin >> u >> v; // 输入边的信息 int idx_u = u - 'A'; int idx_v = v - 'A'; g.addEdge(idx_u, idx_v); // 添加无向边到邻接表中 } vector<bool> visited(n, false); cout << "DFS Traversal: "; dfs(g, 0, visited); // 从第一个顶点开始深搜 cout << endl; fill(visited.begin(), visited.end(), false); // 重置访问状态 cout << "BFS Traversal: "; bfs(g, 0, visited); // 从第一个顶点开始广搜 cout << endl; return 0; } ``` 上述两段代码分别实现了基于 **邻接矩阵** 和 **邻接表** 的无向图 BFS 和 DFS 算法[^1]^。通过这两种不同的存储方式，可以灵活应对不同规模的数据集需求。 --- ### 关于矩阵乘法的应用 在某些情况下，可以通过邻接矩阵的幂运算来计算两点间的最短路径长度。具体而言，如果 $ A^n[i][j] \neq 0 $，则说明从顶点 $ i $ 到顶点 $ j $ 存在长度为 $ n $ 的路径[^2]^。这种方法通常用于稠密图或者理论分析场景下。 ---