定义一个图的数据类型，完成以下操作 (1)用邻接矩阵的方式创建一个图; (2)用邻接表的方式创建一个图; (3)对采用邻接矩阵表示的图进行深度优先遍历; (4)对采用邻接矩阵表示的图进行广度优先遍历; (5)对采用邻接表表示的图进行深度优先遍历; (6)对采用邻接表表示的图进行广度优先遍历;

好的，我会尽力回答你的问题。 首先，定义一个图的数据类型，可以使用以下代码： ```python class Graph: def __init__(self, vertices): self.V = vertices self.graph = [[0] * self.V for _ in range(self.V)] ``` 其中，`V` 表示图中的顶点数，`graph` 表示邻接矩阵。 接下来，我们可以用邻接矩阵的方式创建一个图： ```python g = Graph(5) g.graph = [[0, 1, 0, 1, 0], [1, 0, 1, 1, 1], [0, 1, 0, 1, 0], [1, 1, 1, 0, 1], [0, 1, 0, 1, 0]] ``` 这个图的邻接矩阵表示如下： ``` 0 1 2 3 4 0 0 1 0 1 0 1 1 0 1 1 1 2 0 1 0 1 0 3 1 1 1 0 1 4 0 1 0 1 0 ``` 然后，我们可以用邻接表的方式创建一个图： ```python class AdjNode: def __init__(self, data): self.vertex = data self.next = None class Graph: def __init__(self, vertices): self.V = vertices self.graph = [None] * self.V def add_edge(self, src, dest): node = AdjNode(dest) node.next = self.graph[src] self.graph[src] = node node = AdjNode(src) node.next = self.graph[dest] self.graph[dest] = node ``` 其中，`AdjNode` 表示邻接表中的一个节点，`data` 表示节点所对应的顶点。 我们可以这样创建一个邻接表： ```python g = Graph(5) g.add_edge(0, 1) g.add_edge(0, 3) 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) ``` 这个图的邻接表表示如下： ``` 0: 1 -> 3 1: 0 -> 2 -> 3 -> 4 2: 1 -> 3 3: 0 -> 1 -> 2 -> 4 4: 1 -> 3 ``` 现在，我们可以对采用邻接矩阵表示的图进行深度优先遍历： ```python class Graph: def __init__(self, vertices): self.V = vertices self.graph = [[0] * self.V for _ in range(self.V)] def DFS(self, v, visited): visited[v] = True print(v, end=' ') for i in range(self.V): if self.graph[v][i] == 1 and not visited[i]: self.DFS(i, visited) def DFS_traversal(self, v): visited = [False] * self.V self.DFS(v, visited) ``` 我们可以这样调用方法： ```python g = Graph(5) g.graph = [[0, 1, 0, 1, 0], [1, 0, 1, 1, 1], [0, 1, 0, 1, 0], [1, 1, 1, 0, 1], [0, 1, 0, 1, 0]] g.DFS_traversal(0) ``` 输出结果为： ``` 0 1 2 3 4 ``` 接下来，我们可以对采用邻接矩阵表示的图进行广度优先遍历： ```python from collections import deque class Graph: def __init__(self, vertices): self.V = vertices self.graph = [[0] * self.V for _ in range(self.V)] def BFS(self, v, visited): queue = deque() queue.append(v) visited[v] = True while queue: s = queue.popleft() print(s, end=' ') for i in range(self.V): if self.graph[s][i] == 1 and not visited[i]: queue.append(i) visited[i] = True def BFS_traversal(self, v): visited = [False] * self.V self.BFS(v, visited) ``` 我们可以这样调用方法： ```python g = Graph(5) g.graph = [[0, 1, 0, 1, 0], [1, 0, 1, 1, 1], [0, 1, 0, 1, 0], [1, 1, 1, 0, 1], [0, 1, 0, 1, 0]] g.BFS_traversal(0) ``` 输出结果为： ``` 0 1 3 2 4 ``` 现在，我们可以对采用邻接表表示的图进行深度优先遍历： ```python class AdjNode: def __init__(self, data): self.vertex = data self.next = None class Graph: def __init__(self, vertices): self.V = vertices self.graph = [None] * self.V def add_edge(self, src, dest): node = AdjNode(dest) node.next = self.graph[src] self.graph[src] = node node = AdjNode(src) node.next = self.graph[dest] self.graph[dest] = node def DFS(self, v, visited): visited[v] = True print(v, end=' ') temp = self.graph[v] while temp: if not visited[temp.vertex]: self.DFS(temp.vertex, visited) temp = temp.next def DFS_traversal(self, v): visited = [False] * self.V self.DFS(v, visited) ``` 我们可以这样调用方法： ```python g = Graph(5) g.add_edge(0, 1) g.add_edge(0, 3) 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) g.DFS_traversal(0) ``` 输出结果为： ``` 0 1 2 3 4 ``` 最后，我们可以对采用邻接表表示的图进行广度优先遍历： ```python from collections import deque class AdjNode: def __init__(self, data): self.vertex = data self.next = None class Graph: def __init__(self, vertices): self.V = vertices self.graph = [None] * self.V def add_edge(self, src, dest): node = AdjNode(dest) node.next = self.graph[src] self.graph[src] = node node = AdjNode(src) node.next = self.graph[dest] self.graph[dest] = node def BFS(self, v, visited): queue = deque() queue.append(v) visited[v] = True while queue: s = queue.popleft() print(s, end=' ') temp = self.graph[s] while temp: if not visited[temp.vertex]: queue.append(temp.vertex) visited[temp.vertex] = True temp = temp.next def BFS_traversal(self, v): visited = [False] * self.V self.BFS(v, visited) ``` 我们可以这样调用方法： ```python g = Graph(5) g.add_edge(0, 1) g.add_edge(0, 3) 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) g.BFS_traversal(0) ``` 输出结果为： ``` 0 1 3 2 4 ``` 希望我的回答能够帮助到你！