输出景点深度遍历和广度遍历的结果
时间: 2023-09-01 13:08:11 浏览: 40
好的,以下是景点深度遍历和广度遍历的结果:
假设有如下的景点图:
```
A -> B, C, D
B -> E, F
C -> G, H
D -> I, J
```
其中 A, B, C, D, E, F, G, H, I, J 分别表示不同的景点,箭头表示两个景点之间存在道路相连。
深度遍历的结果为:A -> B -> E -> F -> C -> G -> H -> D -> I -> J
广度遍历的结果为:A -> B -> C -> D -> E -> F -> G -> H -> I -> J
希望这个回答对你有所帮助。
相关问题
创建邻接矩阵并输出深度遍历和广度遍历
邻接矩阵是一种表示图的数据结构,可以用来表示无向图或有向图。在邻接矩阵中,矩阵的行和列分别表示图中的节点,对应位置的元素表示两个节点之间是否存在边。
下面是创建邻接矩阵并输出深度遍历和广度遍历的基本步骤:
1. 创建一个二维数组,其大小为节点数 * 节点数。
2. 根据图中的边信息,将邻接矩阵中对应位置的元素赋值为1或0。
3. 深度遍历:
- 从起始节点开始,遍历所有与其直接相连的节点,标记这些节点为已访问。
- 对于每一个已访问的节点,递归地进行深度遍历。
4. 广度遍历:
- 创建一个队列,并将起始节点入队。
- 从队列中取出一个节点,并将所有与其直接相连的未访问节点入队。
- 对于每一个入队的节点,标记为已访问,并将其出队并输出。
下面是一个简单的 Python 代码示例:
```
# 创建邻接矩阵
adj_matrix = [
[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 1],
[0, 1, 1, 0]
]
# 深度遍历
visited = [False] * len(adj_matrix)
def dfs(node):
visited[node] = True
print(node)
for i in range(len(adj_matrix)):
if adj_matrix[node][i] == 1 and not visited[i]:
dfs(i)
dfs(0)
# 广度遍历
visited = [False] * len(adj_matrix)
queue =
visited = True
while queue:
node = queue.pop(0)
print(node)
for i in range(len(adj_matrix)):
if adj_matrix[node][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True
```
二叉树的深度遍历和广度遍历代码
好的,以下是二叉树的深度遍历和广度遍历的代码:
深度遍历(前序、中序、后序遍历)代码:
```python
# 定义二叉树节点类
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 递归前序遍历
def preorder_traversal(root):
if not root:
return
print(root.val) # 先输出根节点的值
preorder_traversal(root.left) # 遍历左子树
preorder_traversal(root.right) # 遍历右子树
# 递归中序遍历
def inorder_traversal(root):
if not root:
return
inorder_traversal(root.left) # 遍历左子树
print(root.val) # 先输出根节点的值
inorder_traversal(root.right) # 遍历右子树
# 递归后序遍历
def postorder_traversal(root):
if not root:
return
postorder_traversal(root.left) # 遍历左子树
postorder_traversal(root.right) # 遍历右子树
print(root.val) # 先输出根节点的值
```
广度遍历(层次遍历)代码:
```python
from collections import deque
# 广度遍历(层次遍历)
def levelorder_traversal(root):
if not root:
return
q = deque()
q.append(root)
while q:
n = len(q)
for i in range(n):
node = q.popleft()
print(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
```
希望能够帮到你!