编程要求 输入 多组数据,每组m+2数据行。第一行有两个数字n和m,代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个整数h和k,代表边依附的两个顶点。第m+2行有一个整数d,代表从d开始遍历。当n和m都等于0时,输入结束。 输出 每组数据输出一行,为深度优先搜索的遍历结果。每两个数字之间用空格隔开。
时间: 2024-03-01 09:52:27 浏览: 104
好的,这是一个深度优先搜索(DFS)遍历图的问题,以下是代码实现:
```python
def dfs(cur, visited, graph, res):
visited[cur] = True
res.append(cur)
for next_node in graph[cur]:
if not visited[next_node]:
dfs(next_node, visited, graph, res)
while True:
n, m = map(int, input().split())
if n == 0 and m == 0:
break
graph = [[] for _ in range(n+1)]
for i in range(m):
h, k = map(int, input().split())
graph[h].append(k)
graph[k].append(h)
d = int(input())
visited = [False] * (n+1)
res = []
dfs(d, visited, graph, res)
print(" ".join(str(x) for x in res))
```
以上代码中,dfs函数接收当前节点cur,已经访问过的节点列表visited,节点之间的关系图graph和遍历结果列表res作为参数。将当前节点cur标记为已经访问过,将其加入遍历结果列表res。然后,遍历当前节点cur所能到达的所有节点,如果这些节点中存在一个未被访问过的节点next_node,则递归调用dfs函数以遍历next_node节点。最后,将遍历结果列表res中的元素按顺序输出。
在主程序中,首先读入顶点个数n和边数m,如果n和m均为0,则退出循环。接下来,对于每条边,读入边依附的两个顶点h和k,并在关系图graph中将节点h和节点k相连接。最后,读入起始遍历节点d,将已经访问过的节点列表visited初始化为全False,将遍历结果列表res初始化为空列表,调用dfs函数以遍历从起点d开始能够到达的所有节点,并将遍历结果输出。
阅读全文