深度优先搜索求联通分量
时间: 2023-12-07 14:37:25 浏览: 32
以下是使用深度优先搜索求联通分量的Python实现:
```python
# 定义一个图类
class Graph:
def __init__(self, vertices):
self.V = vertices
self.adj = [[] for i in range(vertices)]
# 添加边
def addEdge(self, v, w):
self.adj[v].append(w)
self.adj[w].append(v)
# 深度优先搜索
def DFSUtil(self, temp, v, visited):
visited[v] = True
temp.append(v)
for i in self.adj[v]:
if visited[i] == False:
temp = self.DFSUtil(temp, i, visited)
return temp
# 获取联通分量
def connectedComponents(self):
visited = []
cc = []
for i in range(self.V):
visited.append(False)
for v in range(self.V):
if visited[v] == False:
temp = []
cc.append(self.DFSUtil(temp, v, visited))
return cc
# 创建一个图实例
g = Graph(5)
g.addEdge(1, 0)
g.addEdge(2, 3)
g.addEdge(3, 4)
# 获取联通分量
cc = g.connectedComponents()
print("Following are connected components")
print(cc)
```
运行结果如下:
```
Following are connected components
[[0, 1], [2, 3, 4]]
```
上述代码中,我们首先定义了一个图类,包含了添加边、深度优先搜索和获取联通分量等方法。在获取联通分量的方法中,我们使用了深度优先搜索算法,对于每个未被访问过的节点,我们都进行一次深度优先搜索,并将搜索到的节点加入到一个临时列表中。当搜索结束后,我们将这个临时列表加入到联通分量列表中。最终返回联通分量列表。