pta7-2 数据结构实验三 图的广度优先搜索
时间: 2023-07-21 12:06:16 浏览: 178
题目描述
给定一个无向图,求从给定的起始顶点开始,以广度优先遍历方式遍历整个图后所得到的遍历序列。
输入格式
输入文件的第一行包含两个整数 n 和 m,表示图的顶点数和边数。
接下来 m 行,每行包含两个整数 a 和 b,表示存在一条从顶点 a 到顶点 b 的边。
最后一行包含一个整数 s,表示起始顶点编号。
输出格式
输出文件仅一行,即广度优先遍历所得到的遍历序列,每个数字之间用空格隔开。
数据范围
1≤n≤1000,
1≤m≤10000,
1≤a,b≤n,
1≤s≤n
输入样例
4 4
1 2
1 3
2 4
3 4
1
输出样例
1 2 3 4
算法1
(广度优先搜索) $O(m+n)$
时间复杂度
参考文献
python3 代码
C++ 代码
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
相关问题
pta6-2 数据结构实验 根据带虚结点的先序序列创建二叉树
好的,我可以为你解答这个问题。
根据带虚结点的先序序列创建二叉树的步骤如下:
1. 读入先序序列,包括虚结点和实结点。如果当前读入的结点是虚结点,则不需要创建对应的结点,直接跳过。
2. 如果当前读入的结点是实结点,则创建一个新的二叉树结点,将其值设置为当前读入的值。
3. 判断当前结点的父节点是否存在,如果存在,则将当前结点作为父节点的左子节点或右子节点,具体是左子节点还是右子节点取决于先序序列中下一个结点的类型。
4. 将当前结点加入到一个栈中保存,以便后续处理。
5. 如果下一个结点是虚结点,则直接跳过;如果是实结点,则重复步骤2-4,直到先序序列结束。
6. 返回根节点。
下面是一个示例代码,用于根据带虚结点的先序序列创建二叉树:
```c++
#include <iostream>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* createTree(vector<int>& preorder) {
stack<TreeNode*> st;
TreeNode* root = new TreeNode(preorder[0]);
st.push(root);
for (int i = 1; i < preorder.size(); i++) {
if (preorder[i] == -1) {
continue;
}
TreeNode* curr = new TreeNode(preorder[i]);
if (i % 2 == 1) {
st.top()->left = curr;
} else {
st.top()->right = curr;
}
st.push(curr);
while (!st.empty() && st.top()->right != NULL) {
st.pop();
}
}
return root;
}
int main() {
vector<int> preorder = {1, 2, -1, 3, 4, 5, -1, -1, -1, -1, -1};
TreeNode* root = createTree(preorder);
return 0;
}
```
在这个示例代码中,我们使用了一个栈来保存当前处理到的结点,以及其祖先结点。对于每个读入的结点,我们先判断其类型(虚结点还是实结点),然后根据其在先序序列中的位置,将其作为左子节点或右子节点加入到其父节点中。如果当前结点的右子节点已经存在,说明其已经处理完毕,我们可以将其从栈中弹出。最后,我们返回根节点即可。
pta7-2查找书籍
以下是一个解决pta7-2查找书籍问题的Python程序:
```python
n = int(input()) # 输入书籍数量
books = [] # 存储书籍信息的列表
# 循环读取书籍信息
for i in range(n):
book_info = input().split() # 输入格式为“价格 书名”,使用split()函数将其拆分为列表
book_info[0] = float(book_info[0]) # 将价格转换为浮点数
books.append(book_info) # 将书籍信息添加到列表中
# 使用max()和min()函数找到价格最高和最低的书籍
max_book = max(books, key=lambda x: x[0]) # 根据价格进行比较
min_book = min(books, key=lambda x: x[0])
# 输出结果
print("{:.2f}, {}".format(max_book[0], max_book[1]))
print("{:.2f}, {}".format(min_book[0], min_book[1]))
```