Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0301· OpenAIAi2 WildChat-4.8M (AI2)

1)分别用邻接矩阵和邻接表存储图,输入一定数量的顶点和边,建立一个图; 2)实现图的深度优先遍历并输出结果; 3)实现图的广度优先遍历并输出结果。(要求全部写出代码)

  1. User

    1)分别用邻接矩阵和邻接表存储图,输入一定数量的顶点和边,建立一个图; 2)实现图的深度优先遍历并输出结果; 3)实现图的广度优先遍历并输出结果。(要求全部写出代码)

  2. 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
    

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.