1. 图的创建与遍历 【问题描述】 请基于邻接矩阵存储结构构建带权无向图,输出其深度遍历序列和广度遍历序列。 【输入形式】 输入数据有多行,首行m和n,表示图有m个顶点和n条边;第二行是m个顶点名称,中间空格分隔;之后为n条边,表示形式为:起点名称 终点名称 权值;最后一行为遍历的起点名称。 【输出形式】 输出数据有两行,首行为深度遍历序列,末行为广度遍历序列。 【样例输入】 4 5 A B C D A B 5 A C 2 A D 1 B C 4 C D 6 A 【样例输出】 A B C D A B C D
时间: 2024-02-12 12:09:37 浏览: 58
我知道了,这是一个关于图的创建与遍历的问题。
以下是Python的实现代码:
```python
from queue import Queue
# 邻接矩阵存储图
class Graph:
def __init__(self, m, n, vertexs, edges):
self.m = m
self.n = n
self.vertexs = vertexs
self.edges = edges
self.adjMat = [[float('inf')] * m for _ in range(m)]
for i in range(m):
self.adjMat[i][i] = 0
for i in range(n):
start, end, weight = edges[i]
x = vertexs.index(start)
y = vertexs.index(end)
self.adjMat[x][y] = weight
self.adjMat[y][x] = weight
# 深度优先遍历
def dfs(self, start):
visited = [False] * self.m
result = []
self._dfs(start, visited, result)
return result
def _dfs(self, vertex, visited, result):
visited[vertex] = True
result.append(self.vertexs[vertex])
for i in range(self.m):
if not visited[i] and self.adjMat[vertex][i] != float('inf'):
self._dfs(i, visited, result)
# 广度优先遍历
def bfs(self, start):
visited = [False] * self.m
result = []
q = Queue()
q.put(start)
visited[self.vertexs.index(start)] = True
while not q.empty():
vertex = q.get()
result.append(vertex)
for i in range(self.m):
if not visited[i] and self.adjMat[self.vertexs.index(vertex)][i] != float('inf'):
q.put(self.vertexs[i])
visited[i] = True
return result
# 主函数
if __name__ == '__main__':
m, n = map(int, input().split())
vertexs = input().split()
edges = [input().split() for _ in range(n)]
start = input().strip()
graph = Graph(m, n, vertexs, edges)
print(' '.join(graph.dfs(vertexs.index(start))))
print(' '.join(graph.bfs(start)))
```
输入样例:
```
4 5
A B C D
A B 5
A C 2
A D 1
B C 4
C D 6
A
```
输出样例:
```
A B C D
A B C D
```
阅读全文