Componentes conectados em Python
Estou escrevendo uma funçãoget_connected_components
para uma aulaGraph
:
<code>def get_connected_components(self): path=[] for i in self.graph.keys(): q=self.graph[i] while q: print(q) v=q.pop(0) if not v in path: path=path+[v] return path </code>
Meu gráfico é:
<code>{0: [(0, 1), (0, 2), (0, 3)], 1: [], 2: [(2, 1)], 3: [(3, 4), (3, 5)], \ 4: [(4, 3), (4, 5)], 5: [(5, 3), (5, 4), (5, 7)], 6: [(6, 8)], 7: [], \ 8: [(8, 9)], 9: []} </code>
onde as chaves são os nós e os valores são a borda. Minha função me dá esse componente conectado:
<code>[(0, 1), (0, 2), (0, 3), (2, 1), (3, 4), (3, 5), (4, 3), (4, 5), (5, 3), \ (5, 4), (5, 7), (6, 8), (8, 9)] </code>
Mas eu teria dois componentes conectados diferentes, como:
<code>[[(0, 1), (0, 2), (0, 3), (2, 1), (3, 4), (3, 5), (4, 3), (4, 5), \ (5, 3), (5, 4), (5, 7)],[(6, 8), (8, 9)]] </code>
Eu não entendo onde cometi o erro. Alguém pode me ajudar?