编写函数实现此图的深度优先搜索遍历
时间: 2023-07-28 11:10:38 浏览: 56
好的,以下是一个使用 Python 编写的深度优先搜索遍历算法:
```python
# 定义一个邻接矩阵表示图,0表示不相邻,1表示相邻
graph = [
[0, 1, 1, 0, 0, 0],
[1, 0, 0, 1, 1, 0],
[1, 0, 0, 0, 1, 0],
[0, 1, 0, 0, 1, 1],
[0, 1, 1, 1, 0, 1],
[0, 0, 0, 1, 1, 0]
]
# 定义一个数组存储节点是否已经被访问过
visited = [False] * len(graph)
# 定义一个递归函数实现深度优先搜索遍历
def dfs(node):
# 标记当前节点已经被访问过
visited[node] = True
print(node, end=' ')
# 遍历当前节点的所有邻居节点
for i in range(len(graph[node])):
if graph[node][i] == 1 and not visited[i]:
dfs(i)
# 从节点0开始进行深度优先搜索遍历
dfs(0)
```
这段代码会输出以下结果:
```
0 1 3 4 2 5
```
其中,数字表示节点的编号,按照深度优先搜索的顺序依次输出。您可以根据自己的实际需要修改代码中的邻接矩阵来实现对不同图的遍历。
相关问题
编写函数实现此图的深度优先搜索遍历。
好的,以下是一个示例代码,可以实现该图的深度优先搜索遍历:
```python
def dfs(graph, start, visited=None):
# 初始化visited
if visited is None:
visited = set()
# 将当前节点标记为已访问
visited.add(start)
print(start, end=' ')
# 递归访问未访问过的相邻节点
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
```
以上代码中,dfs函数接受三个参数:图的邻接表表示,起点start和已访问节点的集合visited。在每次访问一个节点时,将其标记为已访问,并输出其编号。然后递归访问其未访问过的相邻节点,直到遍历完所有节点。
以下是调用示例:
```python
# 创建图
graph = [[1, 2], [0, 3, 4], [0, 4], [1, 5], [1, 2, 5], [3, 4]]
# 从节点0开始深度优先遍历
dfs(graph, 0)
```
输出结果为:
```
0 1 3 5 4 2
```
即从节点0开始,依次遍历节点0、1、3、5、4、2。
c++ 编写程序实现对图的深度优先遍历
深度优先遍历(Depth First Search,DFS)是图论中的经典算法。其基本思想是从图中某个顶点v出发,遍历与之相邻且未被访问的顶点,然后从该顶点出发继续遍历与之相邻的未被访问的顶点,直到图中所有与v有路径相通的顶点都被访问到。具体实现可以使用递归或栈来实现。以下是使用递归实现深度优先遍历的代码:
```c++
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 100; // 最大顶点数
vector<int> G[MAXN]; // 图的邻接表表示
bool vis[MAXN]; // 标记数组,记录每个顶点是否被访问过
// 深度优先遍历
void dfs(int u) {
vis[u] = true; // 标记当前顶点已被访问
cout << u << " "; // 输出当前顶点
for (int i = 0; i < G[u].size(); i++) { // 遍历与u相邻的顶点
int v = G[u][i];
if (!vis[v]) { // 如果v未被访问,则以v为起点继续深度优先遍历
dfs(v);
}
}
}
int main() {
int n, m;
cin >> n >> m; // 输入顶点数n和边数m
memset(vis, false, sizeof(vis)); // 初始化标记数组
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v; // 输入一条边的两个端点u和v
G[u].push_back(v); // 添加边(u,v)到邻接表中
G[v].push_back(u); // 添加边(v,u)到邻接表中(无向图需要双向添加)
}
dfs(1); // 从顶点1开始深度优先遍历
return 0;
}
```
上述代码中,G数组是邻接表表示的图,vis数组是标记数组,记录每个顶点是否被访问过。dfs函数是递归实现的深度优先遍历函数,参数u表示当前遍历到的顶点。在dfs函数中,首先将当前顶点u标记为已访问,然后输出该顶点,最后遍历与u相邻的未被访问的顶点v,并以v为起点继续深度优先遍历。在主函数中,首先输入顶点数n和边数m,然后读入m条边的信息并添加到邻接表中,最后从顶点1开始进行深度优先遍历。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.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)