Check if is One Component
BFS: check if graph is one-component
In the previous method, we considered that the graph is one-component. That’s because if you start traversing at some node, you’ll visit only nodes from the same component.
If there are some other components, you should start from vertices of another component.
Task
Swipe to start coding
Think about Implementation of method hasOneComponent(). which returns True if it is only one component in graph.
Modify your g graph by adding nodes in that way, so there are miltiple components, and check how function works.
Solution
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 hasOneComponent(self):
q = [] # queue
start = 1 # first vertice
visited = [False for v in self.graph.keys()]
q.append(start)
visited[start] = True
while len(q)>0:
# pop node from queue
node = q.pop(0)
for vertex in self.graph[node]: # iterate neighbors
if !visited[vertex]:
q.append(vertex)
visited[vertex] = True
print(vertex, "appended")
return visited.count(False) == 0
Everything was clear?
Thanks for your feedback!
Section 2. Chapter 2
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 hasOneComponent(self):
# do the bft() here, and check the visited array
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)
g.bft(0)
