邻接矩阵的深度广度遍历
时间: 2024-07-10 22:00:57 浏览: 71
邻接矩阵是图的一种表示方法,其中用一个二维数组来存储图中顶点之间的连接关系。深度优先搜索(DFS)和广度优先搜索(BFS)是两种常用的图遍历算法,它们可以帮助我们探索图的结构。
**深度优先遍历(DFS)**:
- 它从起点开始,尽可能深地探索分支,直到到达一个无法访问的节点为止,然后返回并探索其他分支。
- DFS通常使用递归或栈来实现。从起点开始,将当前节点标记为已访问,然后对每个相邻未访问的节点递归执行DFS。
- 优点:内存占用相对较小,可以找到最短路径到某个节点(如果图是有向无环图,且所有边权值为1)。
-
相关问题
邻接矩阵深度优先遍历和广度优先遍历
邻接矩阵是一种图的存储结构,它可以用来表示有限个顶点之间的关系。邻接矩阵的深度优先遍历和广度优先遍历是图的两种基本遍历方式。
邻接矩阵的深度优先遍历(Depth First Search,DFS):
深度优先遍历是一种用于遍历或搜索树或图的算法。在这个算法中,首先访问根节点,然后递归地访问每个子节点。当访问一个节点时,将其标记为已访问,以避免重复访问。深度优先遍历使用栈来实现,因此它是一种先进后出(Last In First Out,LIFO)的算法。
下面是邻接矩阵的深度优先遍历的Python代码示例:
```python
def DFS(graph, start):
visited = set() # 用集合来存储已经访问过的节点
stack = [start] # 用列表来模拟栈
while stack:
vertex = stack.pop() # 取出栈顶元素
if vertex not in visited:
visited.add(vertex) # 标记为已访问
print(vertex, end=' ')
# 将未访问的邻居节点入栈
stack.extend([i for i in range(len(graph[vertex])) if graph[vertex][i] and i not in visited])
# 示例
graph = [[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 1],
[0, 1, 1, 0]]
DFS(graph, 0) # 输出:0 1 3 2
```
邻接矩阵的广度优先遍历(Breadth First Search,BFS):
广度优先遍历是一种用于遍历或搜索树或图的算法。在这个算法中,首先访问根节点,然后逐层访问每个子节点。当访问一个节点时,将其标记为已访问,以避免重复访问。广度优先遍历使用队列来实现,因此它是一种先进先出(First In First Out,FIFO)的算法。
下面是邻接矩阵的广度优先遍历的Python代码示例:
```python
from collections import deque
def BFS(graph, start):
visited = set() # 用集合来存储已经访问过的节点
queue = deque([start]) # 用双端队列来模拟队列
while queue:
vertex = queue.popleft() # 取出队首元素
if vertex not in visited:
visited.add(vertex) # 标记为已访问
print(vertex, end=' ')
# 将未访问的邻居节点入队
queue.extend([i for i in range(len(graph[vertex])) if graph[vertex][i] and i not in visited])
# 示例
graph = [[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 1],
[0, 1, 1, 0]]
BFS(graph, 0) # 输出:0 1 2 3
```
邻接矩阵广度优先遍历
邻接矩阵广度优先遍历是一种图的遍历算法,用于遍历图中所有节点。具体步骤如下:
1. 创建一个队列,将起始节点放入队列中。
2. 创建一个visited数组,用于记录每个节点是否被访问过,将起始节点标记为已访问。
3. 当队列不为空时,执行以下操作:
- 从队列中取出一个节点,访问该节点。
- 遍历该节点的所有邻居节点,如果邻居节点未被访问过,则将其标记为已访问,并将其加入队列中。
4. 重复步骤3,直到队列为空。
下面是一个Python实现的邻接矩阵广度优先遍历的例子:
```python
def BFSTraverse(graph, start):
queue = [] # 创建一个队列
visited = [False] * len(graph) # 创建一个visited数组,初始值为False
queue.append(start) # 将起始节点放入队列中
visited[start] = True # 标记起始节点为已访问
while queue:
node = queue.pop(0) # 从队列中取出一个节点
print(node, end=' ') # 访问该节点
for i in range(len(graph)):
if graph[node][i] != 0 and not visited[i]: # 遍历该节点的所有邻居节点
visited[i] = True # 标记邻居节点为已访问
queue.append(i) # 将邻居节点加入队列中
# 示例代码
graph = [[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 1],
[0, 1, 1, 0]]
BFSTraverse(graph, 0) # 从节点0开始遍历
```