1、创建无向图的邻接表存储结构 2、完成图的深度优先遍历 3、完成图的广度优先遍历
时间: 2023-11-29 08:06:48 浏览: 31
1. 创建无向图的邻接表存储结构
邻接表是一种图的表示方法,它用一个数组存储所有的顶点,每个顶点对应一个链表,该链表存储该顶点相邻的顶点。具体实现如下:
```python
class Graph:
def __init__(self, vertices):
self.vertices = vertices # 顶点个数
self.adj_list = {} # 邻接表
# 初始化邻接表
for v in range(vertices):
self.adj_list[v] = []
def add_edge(self, u, v):
self.adj_list[u].append(v)
self.adj_list[v].append(u)
def print_graph(self):
for v in range(self.vertices):
print("顶点", v, "的相邻顶点为:")
for adj_v in self.adj_list[v]:
print(adj_v, end=" ")
print()
```
2. 完成图的深度优先遍历
深度优先遍历是一种遍历图的算法,它从一个起始顶点开始,沿着一条路径一直走到底,直到不能再走为止,然后返回上一个顶点继续走其他路径,直到所有的顶点都被遍历一遍。具体实现如下:
```python
class Graph:
# ...
def dfs(self, v, visited):
visited[v] = True
print(v, end=" ")
for adj_v in self.adj_list[v]:
if not visited[adj_v]:
self.dfs(adj_v, visited)
def dfs_traversal(self, start):
visited = [False for _ in range(self.vertices)]
self.dfs(start, visited)
```
3. 完成图的广度优先遍历
广度优先遍历是一种遍历图的算法,它从一个起始顶点开始,先访问所有与该顶点相邻的顶点,然后再依次访问这些相邻顶点的相邻顶点,直到所有的顶点都被遍历一遍。具体实现如下:
```python
from queue import Queue
class Graph:
# ...
def bfs(self, start, visited):
q = Queue()
q.put(start)
visited[start] = True
while not q.empty():
v = q.get()
print(v, end=" ")
for adj_v in self.adj_list[v]:
if not visited[adj_v]:
q.put(adj_v)
visited[adj_v] = True
def bfs_traversal(self, start):
visited = [False for _ in range(self.vertices)]
self.bfs(start, visited)
```