R6-1 邻接矩阵存储图的深度优先遍历
时间: 2023-12-04 14:40:26 浏览: 47
以下是邻接矩阵存储图的深度优先遍历的Python实现:
```python
def DFS(MGraph, visited, v):
visited[v] = True
print(v, end=' ')
for w in range(MGraph.Nv):
if not visited[w] and MGraph.G[v][w] != 0:
DFS(MGraph, visited, w)
def DFSTraverse(MGraph):
visited = [False] * MGraph.Nv
for v in range(MGraph.Nv):
if not visited[v]:
DFS(MGraph, visited, v)
```
其中,`MGraph`是邻接矩阵存储的图,`visited`是记录每个顶点是否被访问过的数组,`v`是当前访问的顶点。`DFS`函数是深度优先遍历的核心代码,它首先将当前顶点标记为已访问,并输出该顶点的编号。然后遍历该顶点的所有邻接点,如果邻接点未被访问过且与当前顶点有边相连,则递归访问该邻接点。`DFSTraverse`函数是深度优先遍历的入口,它遍历图中的所有连通块,对于每个连通块,从一个未被访问的顶点开始进行深度优先遍历。
相关问题
R6-1 求解矩阵最小路径和问题(动态规划法)
矩阵最小路径和问题可以使用动态规划法来解决。动态规划法的基本思想是将问题分解成若干个子问题,并存储子问题的解,避免重复计算,从而提高算法的效率。
具体来说,对于一个m行n列的矩阵,设dp[i][j]表示从左上角(0,0)到位置(i,j)的最小路径和。则有以下状态转移方程:
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]
其中,dp[0][0] = matrix[0][0],dp[0][j] = dp[0][j-1] + matrix[0][j],dp[i][0] = dp[i-1][0] + matrix[i][0]。
最终答案为dp[m-1][n-1]。
以下是Python代码实现:
def minPathSum(matrix):
m = len(matrix)
n = len(matrix[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = matrix[0][0]
for i in range(1, m):
dp[i][0] = dp[i-1][0] + matrix[i][0]
for j in range(1, n):
dp[0][j] = dp[0][j-1] + matrix[0][j]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]
return dp[m-1][n-1]
r6-2 二叉树的遍历
二叉树的遍历方式有三种:前序遍历、中序遍历和后序遍历。下面分别介绍这三种遍历方式。
1. 前序遍历
前序遍历是指从根节点开始,先输出根节点,然后按照左子树、右子树的顺序遍历每一个节点。具体实现方式如下:
```python
def preorder_traversal(root):
if not root:
return
print(root.val)
preorder_traversal(root.left)
preorder_traversal(root.right)
```
2. 中序遍历
中序遍历是指按照左子树、根节点、右子树的顺序遍历每一个节点。具体实现方式如下:
```python
def inorder_traversal(root):
if not root:
return
inorder_traversal(root.left)
print(root.val)
inorder_traversal(root.right)
```
3. 后序遍历
后序遍历是指按照左子树、右子树、根节点的顺序遍历每一个节点。具体实现方式如下:
```python
def postorder_traversal(root):
if not root:
return
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val)
```
以上三种遍历方式都可以使用递归或非递归的方式实现。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)