Find All Connected Components
BFS find all connected components
Complicate the problem: find all components in a graph.
Some hints for you:
- When you’re done with the first component, save it, and start traversing again with some nodes that haven’t been visited yet.
- To split your components, you can use an upgraded
visitedlist: put0if vertex is not visited yet, or putkif vertex is inkth component. - Return tuple of lists of vertex numbers, one list for each component. Create it by using an upgraded
visitedlist.
Oppgave
Swipe to start coding
Implement getComponents() function.
Alt var klart?
Takk for tilbakemeldingene dine!
Seksjon 2. Kapittel 5
class Graph:
def __init__(self, vertices):
# init graph with its vertices
self.graph = {v : [] for v in vertices}
def addEdge(self, u, v):
self.graph[u].append(v)
def __str__(self):
out = ""
for vertex in self.graph:
out += vertex + ":"+self.graph[vertex]
return out
def getComponents(self):
# put your code here
g=Graph([0,1,2,3,4,5])
g.addEdge(0,1)
g.addEdge(2,1)
g.addEdge(1,0)
g.addEdge(3,1)
g.addEdge(0,2)
g.addEdge(0,3)
g.addEdge(4,1)
print(g.getComponents())
