建立任意无向图,采用邻接矩阵存储,完成以下操作: //(1)对该图进行深度优先遍历,并输出遍历结果; //(2)对该图进行广度优先遍历,并输出遍历结果。
时间: 2024-04-30 13:20:21 浏览: 146
好的,让我们来实现这个问题。首先,让我们定义一个无向图,并采用邻接矩阵存储它。我们假设这个图有6个节点,如下所示:
```
0 -- 1 -- 2
| |
3 -- 4 -- 5
```
邻接矩阵如下:
```
0 1 2 3 4 5
0 0 1 0 1 0 0
1 1 0 1 0 1 0
2 0 1 0 0 1 0
3 1 0 0 0 1 0
4 0 1 1 1 0 1
5 0 0 0 0 1 0
```
其中,1表示两个节点之间有一条边,0表示没有边。
接下来,我们可以使用深度优先遍历和广度优先遍历来遍历这个图。下面是实现深度优先遍历和广度优先遍历的代码:
```python
class Graph:
def __init__(self, adj_matrix):
self.adj_matrix = adj_matrix
self.num_nodes = len(adj_matrix)
def dfs(self, start):
visited = [False] * self.num_nodes
stack = [start]
result = []
while stack:
node = stack.pop()
if not visited[node]:
visited[node] = True
result.append(node)
for i in range(self.num_nodes-1, -1, -1):
if self.adj_matrix[node][i] == 1 and not visited[i]:
stack.append(i)
return result
def bfs(self, start):
visited = [False] * self.num_nodes
queue = [start]
result = []
while queue:
node = queue.pop(0)
if not visited[node]:
visited[node] = True
result.append(node)
for i in range(self.num_nodes):
if self.adj_matrix[node][i] == 1 and not visited[i]:
queue.append(i)
return result
# test
adj_matrix = [
[0, 1, 0, 1, 0, 0],
[1, 0, 1, 0, 1, 0],
[0, 1, 0, 0, 1, 0],
[1, 0, 0, 0, 1, 0],
[0, 1, 1, 1, 0, 1],
[0, 0, 0, 0, 1, 0]
]
graph = Graph(adj_matrix)
print(graph.dfs(0)) # [0, 1, 2, 4, 3, 5]
print(graph.bfs(0)) # [0, 1, 3, 2, 4, 5]
```
在这个代码中,我们首先定义了一个 `Graph` 类,它的构造函数接受一个邻接矩阵作为输入,并将其存储在一个成员变量 `adj_matrix` 中。然后,我们定义了两个方法 `dfs` 和 `bfs`,分别实现深度优先遍历和广度优先遍历。
在深度优先遍历中,我们使用一个栈来存储待访问的节点。我们从起点开始,将其压入栈中。然后,我们从栈中弹出一个节点,并检查它是否已经被访问过。如果没有被访问过,我们将其标记为已访问,并将其加入遍历结果中。接下来,我们遍历该节点的所有邻居节点,将它们压入栈中。
在广度优先遍历中,我们使用一个队列来存储待访问的节点。我们从起点开始,将其加入队列中。然后,我们从队列中取出一个节点,并检查它是否已经被访问过。如果没有被访问过,我们将其标记为已访问,并将其加入遍历结果中。接下来,我们遍历该节点的所有邻居节点,将它们加入队列中。
最后,我们使用上面定义的图来进行测试,并输出遍历结果。
阅读全文