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