5、对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，利用队列的基本运算实现图的广度优先遍历；利用栈的基本运算实现图的深度优先遍历；从键盘输入初始出发的顶点的序号，要求在遍历过程中输出访问过的结点序号。
对给定图进行邻接表表示，并利用队列和栈实现广度优先遍历和深度优先遍历的Python代码实现。同时，程序还支持从键盘输入初始出发的顶点序号，并在遍历过程中输出访问过的结点序号
from collections import defaultdict, deque
class Graph:
def __init__(self, vertices):
self.graph = defaultdict(list)
self.vertices = vertices
def add_edge(self, u, v):
self.graph[u].append(v)
def print_graph(self):
for vertex in self.graph:
print(vertex, "->", " -> ".join(str(i) for i in self.graph[vertex]))
def bfs(self, start_vertex):
visited = [False] * self.vertices
queue = deque()
visited[start_vertex] = True
queue.append(start_vertex)
while queue:
start_vertex = queue.popleft()
print(start_vertex, end=" ")
for vertex in self.graph[start_vertex]:
if not visited[vertex]:
visited[vertex] = True
queue.append(vertex)
def dfs(self, start_vertex):
visited = [False] * self.vertices
stack = []
visited[start_vertex] = True
stack.append(start_vertex)
while stack:
start_vertex = stack.pop()
print(start_vertex, end=" ")
for vertex in self.graph[start_vertex]:
if not visited[vertex]:
visited[vertex] = True
stack.append(vertex)
def traverse(self):
start_vertex = int(input("Enter the starting vertex: "))
print("BFS traversal: ")
self.bfs(start_vertex)
print("\nDFS traversal: ")
self.dfs(start_vertex)
# Create a sample graph
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)
# Print the graph
g.print_graph()
# Traverse the graph
g.traverse()
输出
0 -> 1 -> 4
1 -> 2 -> 3 -> 4
2 -> 3
3 -> 4
Enter the starting vertex: 0
BFS traversal:
0 1 4 2 3
DFS traversal:
0 4 1 3 2
该回答引用ChatGPT
建立邻接表
邻接表是表示图的一种常用数据结构，它用链表存储每个顶点的所有邻接点，因此对于一个有n个顶点，m条边的无向图来说，邻接表需要存储n个链表，每个链表的长度为其对应的顶点的度数（即相邻的节点数），因此邻接表的空间复杂度为O(n+m)。
广度优先遍历
广度优先遍历是一种基于队列实现的遍历算法，从起点开始，先遍历所有与起点相邻的节点，再依次遍历与这些节点相邻的节点，直到遍历完所有节点。
深度优先遍历
深度优先遍历是一种基于栈实现的遍历算法，从起点开始，先遍历一个相邻节点，再遍历这个相邻节点的一个相邻节点，直到访问到无法再往下遍历的节点，然后回溯到上一个节点继续遍历相邻节点。