使用邻接矩阵或者邻接表创建一个图,并对这个图进行深度优先遍历和广度优先遍历。
时间: 2023-12-05 07:09:16 浏览: 44
好的,我可以帮您解答这个问题。
首先,我们需要了解一下邻接矩阵和邻接表。
邻接矩阵是一种表示图的方法,可以用一个二维数组来表示图中各个节点之间的连接关系,其中数组的行和列分别对应着图中的节点,数组元素的值表示相应节点之间的边的数量或权重。
邻接表也是一种表示图的方法,它使用链表来表示图中各个节点之间的连接关系,每个节点都有一个对应的链表,链表中存储着与该节点相连的其他节点的信息。
接下来我们来创建一个无向图,使用邻接矩阵和邻接表来表示这个图。
假设我们要创建如下所示的图:
```
1
/ \
2 3
| |
4 --- 5
```
我们可以用邻接矩阵来表示这个图,其二维数组为:
```
1 2 3 4 5
1 0 1 1 0 0
2 1 0 0 1 0
3 1 0 0 0 1
4 0 1 0 0 1
5 0 0 1 1 0
```
其中,数组元素 1 表示对应节点之间有连接关系,0 表示没有连接关系。
我们也可以用邻接表来表示这个图,其链表为:
```
1 -> 2 -> 3
2 -> 1 -> 4
3 -> 1 -> 5
4 -> 2 -> 5
5 -> 3 -> 4
```
接下来,我们可以使用深度优先遍历和广度优先遍历来遍历这个图。
深度优先遍历的基本思想是从某个节点开始,沿着一条路径不断往下遍历,直到不能再继续往下,然后回溯到前一个节点,继续尝试其他路径,直到所有的节点都被遍历了。
我们可以使用递归来实现深度优先遍历,代码如下:
```python
# 邻接矩阵实现深度优先遍历
def dfs_matrix(matrix, visited, i):
visited[i] = True
print(i, end=' ')
for j in range(len(matrix)):
if matrix[i][j] == 1 and not visited[j]:
dfs_matrix(matrix, visited, j)
# 邻接表实现深度优先遍历
def dfs_list(graph, visited, i):
visited[i] = True
print(i, end=' ')
p = graph[i].next
while p:
if not visited[p.val]:
dfs_list(graph, visited, p.val)
p = p.next
```
广度优先遍历的基本思想是从某个节点开始,先访问其所有相邻节点,然后再依次遍历它们相邻的节点,直到所有的节点都被遍历了。
我们可以使用队列来实现广度优先遍历,代码如下:
```python
# 邻接矩阵实现广度优先遍历
def bfs_matrix(matrix, visited, i):
queue = [i]
visited[i] = True
while queue:
cur = queue.pop(0)
print(cur, end=' ')
for j in range(len(matrix)):
if matrix[cur][j] == 1 and not visited[j]:
queue.append(j)
visited[j] = True
# 邻接表实现广度优先遍历
def bfs_list(graph, visited, i):
queue = [i]
visited[i] = True
while queue:
cur = queue.pop(0)
print(cur, end=' ')
p = graph[cur].next
while p:
if not visited[p.val]:
queue.append(p.val)
visited[p.val] = True
p = p.next
```
至此,我们就完成了对这个图的深度优先遍历和广度优先遍历。