邻接矩阵的深度和广度
时间: 2023-12-11 09:32:41 浏览: 39
邻接矩阵是一种表示图形的方法,其中矩阵的行和列分别表示图形中的节点,而矩阵中的值表示节点之间的边。深度优先搜索和广度优先搜索是两种常见的图形搜索算法,可以用于遍历图形中的节点。
深度优先搜索(DFS)是一种遍历图形的算法,它从一个起始节点开始,沿着一条路径尽可能深入图形,直到无法继续为止,然后返回并探索其他路径。深度优先搜索可以使用递归或堆栈来实现。在邻接矩阵中,深度优先搜索可以通过遍历矩阵的一行来实现。
广度优先搜索(BFS)是一种遍历图形的算法,它从一个起始节点开始,首先访问所有与该节点相邻的节点,然后访问与这些节点相邻的节点,以此类推,直到遍历完整个图形。广度优先搜索可以使用队列来实现。在邻接矩阵中,广度优先搜索可以通过遍历矩阵的一列来实现。
下面是使用Python实现邻接矩阵的深度和广度搜索的示例代码:
```python
# 邻接矩阵
adj_matrix = [[0, 1, 1, 0],
[1, 0, 1,1],
[1, 1, 0, 1],
[0, 1, 1, 0]]
# 深度优先搜索
def dfs(adj_matrix, start, visited):
visited[start] = True
print(start, end=' ')
for i in range(len(adj_matrix)):
if adj_matrix[start][i] == 1 and not visited[i]:
dfs(adj_matrix, i, visited)
# 广度优先搜索
def bfs(adj_matrix, start):
visited = [False] * len(adj_matrix)
queue = [start]
visited[start] = True
while queue:
node = queue.pop(0)
print(node, end=' ')
for i in range(len(adj_matrix)):
if adj_matrix[node][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True
# 测试
visited = [False] * len(adj_matrix)
dfs(adj_matrix, 0, visited)
print()
bfs(adj_matrix, 0)
```