邻接矩阵存储图的深度优先遍历
时间: 2023-07-24 15:04:40 浏览: 51
邻接矩阵是一种存储图的方法,其中矩阵的行和列分别代表图中的顶点,而矩阵中的元素则代表边的存在情况或者权重。邻接矩阵存储图的深度优先遍历算法如下:
1. 创建一个栈,将起始节点入栈。
2. 标记起始节点已经被访问过。
3. 如果栈不为空,则取出栈顶节点,并访问该节点。
4. 遍历该节点的所有邻居节点,如果邻居节点没有被访问过,则将其入栈,并标记为已访问。
5. 重复步骤3-4,直到栈为空。
邻接矩阵的深度优先遍历算法可以通过以下的 Python 代码实现:
```python
def dfs(adj_matrix, start_node):
n = len(adj_matrix)
visited = [False] * n
stack = [start_node]
visited[start_node] = True
while stack:
node = stack.pop()
print(node)
for neighbor in range(n):
if adj_matrix[node][neighbor] and not visited[neighbor]:
stack.append(neighbor)
visited[neighbor] = True
```
其中,adj_matrix 是邻接矩阵,start_node 是起始节点的索引。在代码中,我们使用了一个 visited 列表来记录节点的访问状态,使用栈来实现深度优先遍历。在遍历邻居节点时,我们判断邻居节点是否存在边,并且是否被访问过,如果满足条件,则将邻居节点入栈并标记为已访问。最后,我们输出访问顺序即可。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)