用邻接矩阵或邻接表创建图然后进行DFS和BFS操作
时间: 2024-05-14 17:17:53 浏览: 131
好的,我可以为你介绍一下邻接矩阵和邻接表的创建方法以及DFS和BFS操作的实现。
## 邻接矩阵
邻接矩阵是一种创建图的方式,它使用一个二维数组来表示图中各个节点之间的关系。如果图中有N个节点,那么邻接矩阵就是一个N*N的矩阵。其中,如果节点i和节点j之间有边相连,则邻接矩阵中第i行第j列的值为1,否则为0。
邻接矩阵的创建方法如下:
```python
# 创建邻接矩阵
def create_adj_matrix(graph, n):
adj_matrix = [[0] * n for _ in range(n)] # 初始化邻接矩阵,全部为0
for i in range(n):
for j in range(n):
if graph[i][j] == 1:
adj_matrix[i][j] = 1
return adj_matrix
```
其中,graph是一个二维数组,表示原始的图,n表示节点的个数。
接下来,我们可以使用DFS和BFS算法来遍历邻接矩阵表示的图。
## DFS
DFS(深度优先搜索)是一种递归的搜索算法,它从一个起始点开始,沿着一条路径一直到达最深处,直到无法继续下去时,返回上一个节点,然后选择另一条路径继续搜索,直到遍历完整个图。
DFS的实现方法如下:
```python
# DFS遍历邻接矩阵
def dfs(adj_matrix, visited, n, start):
visited[start] = True
print(start, end=' ')
for i in range(n):
if adj_matrix[start][i] == 1 and not visited[i]:
dfs(adj_matrix, visited, n, i)
```
其中,adj_matrix是邻接矩阵,visited是一个数组,用于记录节点是否被访问过,n表示节点的个数,start表示起始节点。
## BFS
BFS(广度优先搜索)是一种非递归的搜索算法,它从一个起始点开始,先访问它的所有邻居节点,然后访问邻居节点的邻居节点,以此类推,直到遍历完整个图。
BFS的实现方法如下:
```python
# BFS遍历邻接矩阵
def bfs(adj_matrix, visited, n, start):
queue = []
visited[start] = True
queue.append(start)
while queue:
node = queue.pop(0)
print(node, end=' ')
for i in range(n):
if adj_matrix[node][i] == 1 and not visited[i]:
visited[i] = True
queue.append(i)
```
其中,adj_matrix是邻接矩阵,visited是一个数组,用于记录节点是否被访问过,n表示节点的个数,start表示起始节点。queue是一个队列,用于存储待访问的节点。
## 邻接表
邻接表是另一种创建图的方式,它使用一个数组来表示图中各个节点,每个节点对应一个链表,链表中存储该节点所连接的其他节点。
邻接表的创建方法如下:
```python
# 创建邻接表
def create_adj_list(graph, n):
adj_list = [[] for _ in range(n)] # 初始化邻接表
for i in range(n):
for j in range(n):
if graph[i][j] == 1:
adj_list[i].append(j)
return adj_list
```
其中,graph是一个二维数组,表示原始的图,n表示节点的个数。
接下来,我们可以使用DFS和BFS算法来遍历邻接表表示的图。
## DFS
DFS(深度优先搜索)是一种递归的搜索算法,它从一个起始点开始,沿着一条路径一直到达最深处,直到无法继续下去时,返回上一个节点,然后选择另一条路径继续搜索,直到遍历完整个图。
DFS的实现方法如下:
```python
# DFS遍历邻接表
def dfs(adj_list, visited, start):
visited[start] = True
print(start, end=' ')
for i in adj_list[start]:
if not visited[i]:
dfs(adj_list, visited, i)
```
其中,adj_list是邻接表,visited是一个数组,用于记录节点是否被访问过,start表示起始节点。
## BFS
BFS(广度优先搜索)是一种非递归的搜索算法,它从一个起始点开始,先访问它的所有邻居节点,然后访问邻居节点的邻居节点,以此类推,直到遍历完整个图。
BFS的实现方法如下:
```python
# BFS遍历邻接表
def bfs(adj_list, visited, start):
queue = []
visited[start] = True
queue.append(start)
while queue:
node = queue.pop(0)
print(node, end=' ')
for i in adj_list[node]:
if not visited[i]:
visited[i] = True
queue.append(i)
```
其中,adj_list是邻接表,visited是一个数组,用于记录节点是否被访问过,start表示起始节点。queue是一个队列,用于存储待访问的节点。
希望这些代码可以帮助你更好地理解邻接矩阵和邻接表的创建方法以及DFS和BFS算法的实现。
阅读全文