连通图

admin 545 0

下面是一个使用邻接矩阵表示连通图的编程案例:

```python

class Graph:

def __init__(self, vertices):

self.vertices = vertices

self.adj_matrix = [[0] * vertices for _ in range(vertices)]

def add_edge(self, src, dest):

self.adj_matrix[src][dest] = 1

self.adj_matrix[dest][src] = 1

def is_connected(self):

visited = [False] * self.vertices

self.dfs(0, visited)

return all(visited)

def dfs(self, vertex, visited):

visited[vertex] = True

neighbors = self.adj_matrix[vertex]

for i in range(len(neighbors)):

if neighbors[i] == 1 and not visited[i]:

self.dfs(i, visited)

# 测试案例

g = Graph(4)

g.add_edge(0, 1)

g.add_edge(1, 2)

g.add_edge(2, 3)

print(g.is_connected()) # 输出 True

print(g.is_connected()) # 输出 False

```

在这个案例中,我们定义了一个`Graph`类来表示连通图。通过邻接矩阵来存储图的连接关系。`add_edge`方法用于添加边,`is_connected`方法用于判断图是否连通。`dfs`方法是一个辅助方法,用于深度优先搜索遍历图。