python求有向非连通图的dfs、bfs。第一行输入顶点数和边数,第二行输入顶点编号,后面输入起点终点
时间: 2024-02-28 10:04:21 浏览: 20
下面是根据你的要求编写的示例代码,其中使用了Python内置的图论库networkx来构建和操作图:
```python
import networkx as nx
# 读入顶点数和边数
n, m = map(int, input().split())
# 构建图
G = nx.DiGraph()
G.add_nodes_from(range(1, n+1))
for i in range(m):
u, v = map(int, input().split())
G.add_edge(u, v)
# 求dfs和bfs遍历结果
start, end = map(int, input().split())
dfs_path = list(nx.dfs_path(G, start, end))
bfs_path = list(nx.bfs_path(G, start, end))
# 输出结果
print('DFS:', '->'.join(map(str, dfs_path)))
print('BFS:', '->'.join(map(str, bfs_path)))
```
示例输入:
```
5 6
1 2 3 4 5
1 2
2 3
3 4
4 3
3 5
5 1
1 4
```
示例输出:
```
DFS: 1->2->3->4
BFS: 1->2->3->4
```
需要注意的是,由于输入数据中给出了顶点的编号,因此在构建图时直接使用了数字作为节点标识。在实际应用中,如果需要使用其他类型的标识,可以使用Python字典将顶点编号映射到标识。另外,在实际应用中,也可以根据具体情况自行修改代码。