4、图的创建、深度优先遍历、广度优先遍历
时间: 2023-10-09 10:12:37 浏览: 53
1. 图的创建:
图是一种非线性数据结构,它由一组节点和一组连接这些节点的边组成。一个图可以用以下方式表示:
(1)邻接矩阵:用一个二维数组来表示,数组的行和列都代表节点,如果两个节点之间有连接,则数组中对应的元素为1,否则为0。
(2)邻接表:用一个数组来表示,数组的每个元素表示一个节点,每个元素指向一个链表,链表中存储的是与该节点相邻的节点。
2. 深度优先遍历(DFS):
深度优先遍历是一种递归的算法,它从图的某个节点开始遍历,遍历到一个节点时,先访问该节点,然后递归遍历该节点的所有未访问过的邻居节点,直到所有的节点都被访问过。
深度优先遍历的实现可以用递归或栈的方式实现。
3. 广度优先遍历(BFS):
广度优先遍历是一种非递归的算法,它从图的某个节点开始遍历,先访问该节点,然后访问该节点的所有邻居节点,再依次访问邻居节点的邻居节点,直到所有的节点都被访问过。
广度优先遍历的实现可以用队列的方式实现。
相关问题
深度优先遍历 广度优先遍历
深度优先遍历(Depth-First Search,DFS)和广度优先遍历(Breadth-First Search,BFS)是两种常用的图遍历算法。
深度优先遍历是一种通过递归或者栈的方式来遍历图的算法。它从图的某个顶点开始,沿着一条路径一直遍历到最后一个顶点,然后回溯到前一个顶点,再继续遍历其它未遍历的路径。重复这个过程,直到遍历完所有的顶点。
广度优先遍历是一种通过队列的方式来遍历图的算法。它从图的某个顶点开始,首先访问该顶点,然后将其所有未访问过的邻接顶点加入到队列中。之后从队列中取出一个顶点,并访问它的邻接顶点,再将这些邻接顶点加入队列。重复这个过程,直到队列为空。
总结起来,深度优先遍历是先纵向遍历到底再回溯,而广度优先遍历是先横向遍历一层再逐层向下。这两种遍历算法在不同的问题中有不同的应用场景和特点。
深度优先遍历 广度优先遍历的代码示例
下面是深度优先遍历和广度优先遍历的代码示例(以无向图为例):
深度优先遍历的代码示例:
```python
def dfs(graph, start, visited):
visited.add(start)
print(start, end=' ')
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# 以邻接表表示图
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
visited = set()
dfs(graph, 'A', visited)
```
广度优先遍历的代码示例:
```python
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
print(vertex, end=' ')
for neighbor in graph[vertex]:
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)
# 以邻接表表示图
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
bfs(graph, 'A')
```
以上代码示例中,深度优先遍历和广度优先遍历都使用了图的邻接表表示。在深度优先遍历中,使用递归方式实现,通过记录已访问的节点来避免重复访问。在广度优先遍历中,使用队列来存储待访问的节点,并通过记录已访问的节点来避免重复访问。