生成代码(建立任意无向图,采用邻接矩阵存储,完成以下操作:对该图进行深度优先遍历,并输出遍历结果;对该图进行广度优先遍历,并输出遍历结果。)
时间: 2024-03-22 21:41:57 浏览: 135
以下是建立任意无向图、深度优先遍历和广度优先遍历的代码,使用邻接矩阵存储:
```python
class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.adj_matrix = [[0 for x in range(vertices)] for y in range(vertices)]
def add_edge(self, v1, v2):
self.adj_matrix[v1][v2] = 1
self.adj_matrix[v2][v1] = 1
def dfs_helper(self, v, visited, result):
visited[v] = True
result.append(v)
for i in range(self.vertices):
if self.adj_matrix[v][i] == 1 and not visited[i]:
self.dfs_helper(i, visited, result)
def dfs(self, start):
visited = [False for x in range(self.vertices)]
result = []
self.dfs_helper(start, visited, result)
return result
def bfs(self, start):
visited = [False for x in range(self.vertices)]
result = []
queue = [start]
visited[start] = True
while queue:
v = queue.pop(0)
result.append(v)
for i in range(self.vertices):
if self.adj_matrix[v][i] == 1 and not visited[i]:
visited[i] = True
queue.append(i)
return result
# Example usage
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
print("DFS traversal:", g.dfs(0))
print("BFS traversal:", g.bfs(0))
```
这里我们先定义了一个 `Graph` 类,其中 `vertices` 表示节点数,`adj_matrix` 为邻接矩阵。我们通过 `add_edge` 方法来添加边。
深度优先遍历使用了递归实现,其中 `dfs_helper` 方法用于递归遍历节点。广度优先遍历使用了队列实现,其中 `bfs` 方法用于循环遍历队列中的节点。
在这个示例中,我们定义了一个包含 5 个节点的无向图,然后分别输出了深度优先遍历和广度优先遍历的结果。
阅读全文