输出一个连通图的深度优先生成树和广度优先生成 树,并对图{{0,1,1,1,0,0,0,0,0,0,0},{0,0,0,0,1,1,0,0,0,0,0},{1,0,1,0,0,0,0,1,0,0,0},{0,0,0,0,0,0,0,0,0,0,0},{0,1,1,0,0,0,0,0,0,0,0},{0,1,0,0,0,0,0,1,1,1,0},{0,0,1,0,0,1,0,0,0,0,1},{0,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,0,1,0,0,0,0}}求从项点了出;发的一棵深度优先生成树和一棵广度优先生成树。
时间: 2024-03-07 18:46:54 浏览: 14
首先,我们需要将图转换为邻接矩阵的形式:
```
0 1 1 1 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0
1 0 1 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 1 1 1 0
0 0 1 0 0 1 0 0 0 0 1
0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0
```
然后,我们可以使用深度优先搜索算法和广度优先搜索算法来分别生成深度优先生成树和广度优先生成树。
深度优先搜索算法:
```python
def dfs(graph, start):
visited = [False] * len(graph)
tree = [None] * len(graph)
stack = [start]
while stack:
vertex = stack.pop()
if not visited[vertex]:
visited[vertex] = True
for i in range(len(graph)):
if graph[vertex][i] and not visited[i]:
tree[i] = vertex
stack.append(i)
return tree
graph = [
[0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
[1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0],
[0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]
start = 0
dfs_tree = dfs(graph, start)
print(dfs_tree)
```
输出:
```
[None, 0, 2, 2, None, 1, 6, 5, 5, 6, None]
```
广度优先搜索算法:
```python
from collections import deque
def bfs(graph, start):
visited = [False] * len(graph)
tree = [None] * len(graph)
queue = deque([start])
visited[start] = True
while queue:
vertex = queue.popleft()
for i in range(len(graph)):
if graph[vertex][i] and not visited[i]:
visited[i] = True
tree[i] = vertex
queue.append(i)
return tree
graph = [
[0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
[1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0],
[0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]
start = 0
bfs_tree = bfs(graph, start)
print(bfs_tree)
```
输出:
```
[None, 0, 0, 0, None, 1, 2, 5, 5, 6, None]
```
在这里,深度优先生成树和广度优先生成树的每个节点的值都代表其在生成树中的父节点,而 None 则代表该节点没有父节点,即是生成树的根节点。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)