gpt-3.5-turbo-0301· OpenAI
WildChat-4.8M (AI2)
1)分别用邻接矩阵和邻接表存储图,输入一定数量的顶点和边,建立一个图; 2)实现图的深度优先遍历并输出结果; 3)实现图的广度优先遍历并输出结果。(要求全部写出代码)
- User
1)分别用邻接矩阵和邻接表存储图,输入一定数量的顶点和边,建立一个图; 2)实现图的深度优先遍历并输出结果; 3)实现图的广度优先遍历并输出结果。(要求全部写出代码)
- Assistant
邻接矩阵存储图:
class GraphMatrix: def __init__(self, nodes): self.nodes = nodes self.num_nodes = len(nodes) self.adj_mat = [[0] * self.num_nodes for _ in range(self.num_nodes)] def add_edge(self, u, v): i = self.nodes.index(u) j = self.nodes.index(v) self.adj_mat[i][j] = 1 self.adj_mat[j][i] = 1 def depth_first_search(self, start): visited = [False] * self.num_nodes result = [] stack = [self.nodes.index(start)] visited[stack[-1]] = True while stack: current_node = stack.pop() result.append(self.nodes[current_node]) for i in range(self.num_nodes): if self.adj_mat[current_node][i] == 1 and not visited[i]: stack.append(i) visited[i] = True return result def breadth_first_search(self, start): visited = [False] * self.num_nodes result = [] queue = [self.nodes.index(start)] visited[queue[0]] = True while queue: current_node = queue.pop(0) result.append(self.nodes[current_node]) for i in range(self.num_nodes): if self.adj_mat[current_node][i] == 1 and not visited[i]: queue.append(i) visited[i] = True return result邻接表存储图:
class GraphList: def __init__(self, nodes): self.nodes = nodes self.num_nodes = len(nodes) self.adj_list = {} for node in self.nodes: self.adj_list[node] = [] def add_edge(self, u, v): self.adj_list[u].append(v) self.adj_list[v].append(u) def depth_first_search(self, start): visited = {node: False for node in self.nodes} result = [] stack = [start] visited[start] = True while stack: current_node = stack.pop() result.append(current_node) for neighbor in self.adj_list[current_node]: if not visited[neighbor]: stack.append(neighbor) visited[neighbor] = True return result def breadth_first_search(self, start): visited = {node: False for node in self.nodes} result = [] queue = [start] visited[start] = True while queue: current_node = queue.pop(0) result.append(current_node) for neighbor in self.adj_list[current_node]: if not visited[neighbor]: queue.append(neighbor) visited[neighbor] = True return result
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.