定义图的邻接矩阵存储结构,并编写建立图、输出图的每个顶点的度、输出深度优先遍历的顶点序列和广度优先遍历的顶点序列等基本操作实现函数。
时间: 2023-04-25 17:03:47 浏览: 98
邻接矩阵是一种图的存储结构,用二维数组表示图中各个顶点之间的关系。如果图中有n个顶点,那么邻接矩阵就是一个n*n的矩阵,其中第i行第j列的元素表示顶点i和顶点j之间是否有边相连。
建立图的操作可以通过输入每个顶点之间的边来实现,可以使用邻接矩阵来存储图的信息。输出每个顶点的度可以通过遍历邻接矩阵中每个顶点的行或列来实现,度的大小就是该行或列中非零元素的个数。
深度优先遍历可以使用递归的方式实现,从一个起始顶点开始,先访问它的一个邻接顶点,然后再访问这个邻接顶点的邻接顶点,以此类推,直到所有的顶点都被访问过。广度优先遍历可以使用队列来实现,从一个起始顶点开始,先访问它的所有邻接顶点,然后再访问这些邻接顶点的邻接顶点,以此类推,直到所有的顶点都被访问过。
以下是基本操作实现函数的代码:
```python
# 定义邻接矩阵存储结构
class Graph:
def __init__(self, n):
self.n = n
self.matrix = [[0] * n for _ in range(n)]
# 建立图
def add_edge(self, u, v):
self.matrix[u][v] = 1
self.matrix[v][u] = 1
# 输出每个顶点的度
def degree(self):
for i in range(self.n):
deg = sum(self.matrix[i])
print("顶点%d的度为%d" % (i, deg))
# 深度优先遍历
def dfs(self, start):
visited = [False] * self.n
result = []
def dfs_helper(v):
visited[v] = True
result.append(v)
for i in range(self.n):
if self.matrix[v][i] == 1 and not visited[i]:
dfs_helper(i)
dfs_helper(start)
return result
# 广度优先遍历
def bfs(self, start):
visited = [False] * self.n
result = []
queue = [start]
visited[start] = True
while queue:
v = queue.pop(0)
result.append(v)
for i in range(self.n):
if self.matrix[v][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True
return result
```
使用示例:
```python
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.degree() # 输出每个顶点的度
dfs_result = g.dfs(0)
print("深度优先遍历的顶点序列为:", dfs_result)
bfs_result = g.bfs(0)
print("广度优先遍历的顶点序列为:", bfs_result)
```
阅读全文