Given a directed graph. The task is to do Breadth First Traversal of this graph starting from 0.
Note: One can move from node u to node v only if there's an edge from u to v and find the BFS traversal of the graph starting from the 0th vertex, from left to right according to the graph. Also, you should only take nodes directly or indirectly connected from Node 0 in consideration.
Example 1:
Input:
Output: 0 1 2 3 4
Explanation: 
0 is connected to 1 , 2 , 3.
2 is connected to 4.
so starting from 0, it will go to 1 then 2
then 3.After this 2 to 4, thus bfs will be
0 1 2 3 4.
Example 2:
Input:
Output: 0 1 2
Explanation:
0 is connected to 1 , 2.
so starting from 0, it will go to 1 then 2,
thus bfs will be 0 1 2. 
Your task:
You dont need to read input or print anything. Your task is to complete the function bfsOfGraph() which takes the integer V denoting the number of vertices and adjacency list as input parameters and returns  a list containing the BFS traversal of the graph starting from the 0th vertex from left to right.
Expected Time Complexity: O(V + E)
Expected Auxiliary Space: O(V)
Constraints:
1 ≤ V, E ≤ 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Graph algorithms

Graph traversal

Starter code: #User function Template for python3



from typing import List

from queue import Queue

class Solution:

    #Function to return Breadth First Traversal of given graph.

    def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:

        # code here

Solutions:
from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		ans = []
		queue = []
		visited = [0 for i in range(V)]
		queue.append(0)
		visited[0] = 1
		adjacency_list = adj
		while len(queue) != 0:
			k = adjacency_list[queue[0]]
			for i in k:
				if visited[i] != 0:
					pass
				else:
					queue.append(i)
					visited[i] = 1
			ans.append(queue[0])
			queue.pop(0)
		return ans


from collections import deque
from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		visited = []
		q = deque()
		q.append(0)
		visited.append(0)
		while q:
			s = q.popleft()
			for i in adj[s]:
				if i not in visited:
					visited.append(i)
					q.append(i)
		return visited


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		arr = [-1] * V
		out = []
		q = []
		q.append(0)
		while q:
			x = q.pop(0)
			out.append(x)
			arr[x] = 1
			for i in adj[x]:
				if arr[i] == -1:
					q.append(i)
					arr[i] = 1
		return out


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		queue = []
		bfs = []
		visited = [0] * V
		visited[0] = 1
		queue.append(0)
		while queue:
			node = queue.pop(0)
			bfs.append(node)
			for adj_node in adj[node]:
				if not visited[adj_node]:
					queue.append(adj_node)
					visited[adj_node] = 1
		return bfs


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		res = []
		visited = [False for i in range(V)]
		q = [0]
		visited[0] = True
		while len(q) != 0:
			curr = q.pop()
			adjacent = adj[curr]
			for i in adjacent:
				if not visited[i]:
					q.insert(0, i)
					visited[i] = True
			res.append(curr)
		return res


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		visited = []
		q = []
		source = 0
		visited.append(source)
		q.append(source)
		while len(q) > 0:
			x = q.pop(0)
			for y in adj[x]:
				if y not in visited:
					visited.append(y)
					q.append(y)
		return visited


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		vis = []
		s = 0
		q = [s]
		vis.append(0)
		while len(q) > 0:
			x = q.pop(0)
			l = adj[x]
			for y in l:
				if y not in vis:
					vis.append(y)
					q.append(y)
		return vis


from typing import List
from queue import Queue
from collections import deque

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		vis = [0] * V
		vis[0] = 1
		q = deque([0])
		bfs = []
		while q:
			node = q.popleft()
			bfs.append(node)
			for it in adj[node]:
				if not vis[it]:
					vis[it] = 1
					q.append(it)
		return bfs


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		visited = set()
		queue = Queue()
		result = []
		queue.put(0)
		while not queue.empty():
			node = queue.get()
			if not node in visited:
				result.append(node)
				visited.add(node)
			for neighbor in adj[node]:
				if not neighbor in visited:
					queue.put(neighbor)
		return result


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		queue = []
		discovered = [False] * V
		discovered[0] = True
		queue.append(0)
		idx = 0
		while idx < len(queue):
			current = queue[idx]
			idx += 1
			for node in adj[current]:
				if not discovered[node]:
					discovered[node] = True
					queue.append(node)
		return queue


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		from collections import deque
		que = deque()
		que.append(0)
		visited = [0]
		while que:
			node = que.popleft()
			for x in adj[node]:
				if x not in visited:
					que.append(x)
					visited.append(x)
		return visited


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		visitedNodes = set()
		q = []
		q.append(0)
		ans = []
		while q:
			temp = q.pop(0)
			if temp in visitedNodes:
				continue
			visitedNodes.add(temp)
			q.extend(adj[temp])
			ans.append(temp)
		return ans


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		bfs = []
		visited = [False for i in range(V)]
		queue = []
		queue.append(0)
		visited[0] = True
		while queue:
			node = queue.pop(0)
			bfs.append(node)
			for i in adj[node]:
				if visited[i] == False:
					queue.append(i)
					visited[i] = True
		return bfs


from typing import List
from queue import Queue
from collections import deque

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:

		def h(i):
			ans = []
			que = deque([i])
			s = set()
			while len(que):
				node = que.popleft()
				if node in s:
					continue
				s.add(node)
				ans.append(node)
				for j in adj[node]:
					que.append(j)
			return ans
		return h(0)


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		order = []
		queue = Queue()
		queue.put(0)
		visited = set()
		while queue.empty() is False:
			node = queue.get()
			if node in visited:
				continue
			order.append(node)
			visited.add(node)
			for child in adj[node]:
				queue.put(child)
		return order


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		return BFS(adj, 0)

def BFS(G, s):
	n = len(G)
	d = [0 for _ in range(n)]
	visited = [False for _ in range(n)]
	parent = [None for _ in range(n)]
	vertexes = [s]
	q = Queue()
	q.put(s)
	visited[s] = True
	while not q.empty():
		u = q.get()
		for v in G[u]:
			if not visited[v]:
				vertexes.append(v)
				d[v] = d[u] + 1
				parent[v] = u
				visited[v] = True
				q.put(v)
	return vertexes


from typing import List
from queue import Queue
from collections import deque, defaultdict

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		seen = set()
		graph = defaultdict(list)
		for (idx, val) in enumerate(adj):
			graph[idx].extend(val)
		answer = []
		queue = deque()
		queue.append(0)
		while queue:
			temp = queue.popleft()
			if temp not in seen:
				answer.append(temp)
				seen.add(temp)
				for num in graph[temp]:
					queue.append(num)
		return answer


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		q = [0]
		vis = [0]
		r = []
		while len(q) != 0:
			z = q.pop(0)
			r.append(z)
			for i in adj[z]:
				if i not in vis:
					q.append(i)
					vis.append(i)
		return r


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		visited = []
		q = []
		q.append(0)
		visited.append(0)
		while q:
			cur = q[0]
			q.remove(cur)
			for x in adj[cur]:
				if x not in visited:
					q.append(x)
					visited.append(x)
		return visited


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		dict1 = {i: False for i in range(0, V)}
		list1 = [0]
		q = []
		q.append(0)
		dict1[0] = True
		while q:
			node = q.pop(0)
			for i in adj[node]:
				if dict1[i] == False:
					dict1[i] = True
					q.append(i)
					list1.append(i)
		return list1


from typing import List
from collections import deque

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		vs = [False for _ in range(V)]
		ls = []
		q = deque()
		q.append(0)
		vs[0] = True
		while len(q) > 0:
			rp = q.popleft()
			ls.append(rp)
			for nbr in adj[rp]:
				if vs[nbr] == False:
					q.append(nbr)
					vs[nbr] = True
		return ls


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		visit = []
		q = []
		q.append(0)
		visit.append(0)
		while q:
			s = q.pop(0)
			for i in adj[s]:
				if i not in visit:
					visit.append(i)
					q.append(i)
		return visit


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		bfs_path = []
		visited = [False for i in range(V)]
		qu = Queue(maxsize=V)
		qu.put(0)
		visited[0] = True
		while not qu.empty():
			vertex = qu.get()
			bfs_path.append(vertex)
			neighbour = adj[vertex]
			for n in neighbour:
				if not visited[n]:
					qu.put(n)
					visited[n] = True
		return bfs_path


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		visited = []
		queue = []
		queue.append(0)
		visited.append(0)
		while queue:
			s = queue.pop(0)
			for item in adj[s]:
				if item not in visited:
					visited.append(item)
					queue.append(item)
		return visited


from typing import List
from collections import deque

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:

		def bfs(adj, visit, q, k):
			q.append(k)
			while len(q):
				p = q.popleft()
				visit[p] = 1
				for i in adj[p]:
					if visit[i] == 0:
						res.append(i)
						q.append(i)
						visit[i] = 1
		visit = [0] * V
		res = [0]
		q = deque()
		for i in range(V):
			if visit[i] == 0:
				bfs(adj, visit, q, 0)
		return res


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		visited = [False for i in range(V)]
		new_lst = []
		q = Queue()
		q.put(0)
		visited[0] = True
		while not q.empty():
			curr = q.get()
			new_lst.append(curr)
			for i in adj[curr]:
				if visited[i] is False:
					q.put(i)
					visited[i] = True
		return new_lst


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		bfs = []
		visited_dict = dict()
		q = [0]
		visited_dict[0] = True
		while q:
			node = q.pop(0)
			for i in adj[node]:
				if i not in visited_dict:
					q.append(i)
					visited_dict[i] = True
			bfs.append(node)
		return bfs


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		ans = []
		vis = [0] * V
		q = []
		q.append(0)
		ans.append(0)
		vis[0] = 1
		while q:
			curr = q.pop(0)
			for i in adj[curr]:
				if vis[i] == 0:
					q.append(i)
					ans.append(i)
					vis[i] = 1
		return ans


from typing import List
from queue import Queue
from collections import deque

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		q = deque([0])
		visited = [0 for i in range(V)]
		visited[0] = 1
		res = []
		while len(q) > 0:
			node = q.popleft()
			res.append(node)
			for nei in adj[node]:
				if visited[nei] == 0:
					visited[nei] = 1
					q.append(nei)
		return res


from typing import List
from queue import Queue
from collections import deque

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		visited = [False] * V
		q = deque()
		q.append(0)
		visited[0] = True
		ans = []
		while q:
			v = q.popleft()
			ans.append(v)
			for u in adj[v]:
				if not visited[u]:
					q.append(u)
					visited[u] = True
		return ans


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		visited = [0] * V
		visited[0] = 1
		q = []
		q.append(0)
		a = []
		while q:
			f = q[0]
			a.append(f)
			q.pop(0)
			c = adj[f]
			for i in range(len(c)):
				if visited[c[i]] != 1:
					visited[c[i]] = 1
					q.append(c[i])
		return a


from typing import List
from queue import Queue

class Solution:

	def bfs_iterative(self, V: int, adj: List[List[int]]):
		res = []
		graph = {node: [] for node in range(V)}
		for node in range(V):
			graph[node] = adj[node]
		visited = []
		queue = [0]
		while queue:
			n = queue.pop(0)
			if n not in visited:
				res.append(n)
				visited.append(n)
				for adjNode in graph[n]:
					queue.append(adjNode)
		return res

	def bfsOfGraph(self, V: int, adj: List[List[int]]):
		return self.bfs_iterative(V, adj)


from typing import List
from collections import deque

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		search_queue = deque()
		search_queue.append(0)
		seen = set()
		seen.add(0)
		res = []
		while search_queue:
			cur_node = search_queue.popleft()
			res.append(cur_node)
			for adj_node in adj[cur_node]:
				if adj_node not in seen:
					seen.add(adj_node)
					search_queue.append(adj_node)
		return res


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		isVisited = [1 if i == 0 else 0 for i in range(V)]
		q = Queue()
		q.put(0)
		res = []
		while q.qsize() > 0:
			topNode = q.get()
			res.append(topNode)
			for adjNode in adj[topNode]:
				if not isVisited[adjNode]:
					q.put(adjNode)
					isVisited[adjNode] = 1
		return res


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		visited = [False for i in range(V)]
		res = []
		bfs(0, visited, adj, res)
		return res

def bfs(sv, visited, adj, res):
	q = Queue()
	visited[sv] = True
	q.put(sv)
	while q.empty() == False:
		u = q.get()
		res.append(u)
		for node in adj[u]:
			if visited[node] == False:
				q.put(node)
				visited[node] = True


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		q = Queue()
		visited = [False] * V
		li = []
		q.put(0)
		visited[0] = True
		while q.empty() == False:
			i = q.get()
			li.append(i)
			for j in range(len(adj[i])):
				if visited[adj[i][j]] == False:
					q.put(adj[i][j])
					visited[adj[i][j]] = True
		return li


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		vis = set()
		q = Queue()
		ret = []

		def BFS():
			while q.qsize() > 0:
				vert = q.get()
				if vert not in vis:
					vis.add(vert)
					ret.append(vert)
					for ee in adj[vert]:
						if ee not in vis:
							q.put(ee)
		q.put(0)
		BFS()
		return ret


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		queue = []
		visited = []
		queue.append(0)
		while queue:
			node = queue.pop(0)
			if node not in visited:
				visited.append(node)
				edges = adj[node]
				for i in edges:
					if i not in visited:
						queue.append(i)
		return visited


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		if not V:
			return []
		queue = [adj[0]]
		visited = {0: True}
		res = [0]
		while len(queue) > 0:
			item = queue.pop(0)
			for node in item:
				if node not in visited:
					visited[node] = True
					res.append(node)
					queue.append(adj[node])
		return res


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		queue = [0]
		visited = set()
		visited.add(0)
		arr = []
		while queue:
			s = queue.pop(0)
			arr.append(s)
			for n in adj[s]:
				if n not in visited:
					visited.add(n)
					queue.append(n)
		return arr


from typing import List
from queue import Queue
from collections import deque

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		queue = deque()
		lst = []
		queue.append(0)
		visited = [0] * V
		while queue:
			tmp = queue.popleft()
			if visited[tmp] == 0:
				lst.append(tmp)
				visited[tmp] = 1
			for i in adj[tmp]:
				if visited[i] == 0:
					queue.append(i)
		return lst


from typing import List
from queue import Queue

class Solution:

	def bfs(self, root, adj, bfs, visited):
		q = []
		q.append(root)
		visited[root] = 1
		while len(q) != 0:
			node = q.pop(0)
			bfs.append(node)
			for nei in adj[node]:
				if visited[nei] == 0:
					q.append(nei)
					visited[nei] = 1

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		bfs = []
		visited = [0] * V
		self.bfs(0, adj, bfs, visited)
		return bfs


from typing import List
from queue import Queue
from collections import deque

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		visited = [None] * V
		result = []
		queue = deque()
		queue.append(0)
		visited[0] = True
		while len(queue) > 0:
			current_vertex = queue.popleft()
			result.append(current_vertex)
			visited[current_vertex] = True
			for i in adj[current_vertex]:
				if not visited[i]:
					queue.append(i)
					visited[i] = True
		return result


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		visited = [False] * V
		bfs_list = []
		for index in range(V):
			if visited[index] == False:
				queue = []
				visited[index] = True
				queue.append(index)
				while len(queue) > 0:
					node = queue.pop(0)
					bfs_list.append(node)
					for index1 in adj[node]:
						if visited[index1] == False:
							visited[index1] = True
							queue.append(index1)
			return bfs_list


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		visited = [0]
		q = []
		q.append(0)
		ans = []
		while len(q) != 0:
			curr = q.pop(0)
			ans.append(curr)
			for n in adj[curr]:
				if n not in visited:
					q.append(n)
					visited.append(n)
		return ans


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		final = []
		visited = [False] * len(adj)
		queue = []
		queue.append(0)
		while len(queue) > 0:
			element = queue.pop(0)
			final.append(element)
			for i in adj[element]:
				if visited[i] == False:
					queue.append(i)
					visited[i] = True
		return final[:len(adj)]


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		ans = []
		q = Queue(maxsize=V)
		q.put(0)
		visited = [False] * V
		visited[0] = True
		while q.empty() == False:
			temp = q.get()
			ans.append(temp)
			for i in adj[temp]:
				if visited[i] == False:
					visited[i] = True
					q.put(i)
		return ans


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		queue = [0]
		visited = [0] * V
		lst = []
		for i in range(0, V):
			if visited[i] != 1:
				visited[i] = 1
				self.bfs(i, adj, visited, queue, lst)
		return lst

	def bfs(self, src, adj, visited, queue, lst):
		while len(queue) != 0:
			node = queue.pop(0)
			lst.append(node)
			for i in adj[node]:
				if visited[i] != 1:
					visited[i] = 1
					queue.append(i)


from typing import List
from queue import Queue

class Solution:

	def __init__(self):
		self.ans = []

	def utils(self, graph, node):
		queue = [node]
		while queue:
			node = queue.pop(0)
			if self.visited[node] == False:
				self.visited[node] = True
				self.ans.append(node)
				edges = graph[node]
				if len(edges) > 0:
					queue.extend(edges)
		return

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		self.visited = [False for i in range(V)]
		self.utils(adj, 0)
		return self.ans


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, v: int, adjList: List[List[int]]) -> List[int]:
		res = []
		vis = []
		for i in range(v):
			vis.append(0)
		s = Queue()
		vis[0] = 1
		s.put(0)
		while not s.empty():
			t = s.get()
			res.append(t)
			for i in adjList[t]:
				if vis[i] == 0:
					s.put(i)
					vis[i] = 1
		return res


from collections import deque
from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		ans = []
		q = deque()
		visted = [0]
		q.append(0)
		while q:
			tempAns = q.popleft()
			ans.append(tempAns)
			for i in adj[tempAns]:
				if i not in visted:
					visted.append(i)
					q.append(i)
		return ans


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		visited = []
		queue = []
		visited.append(0)
		queue.append(0)
		result = []
		while queue:
			m = queue.pop(0)
			result.append(m)
			for neighbour in adj[m]:
				if neighbour not in visited:
					visited.append(neighbour)
					queue.append(neighbour)
		return result


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		bfs = []
		visited = [False] * V
		queue = Queue()
		queue.put(0)
		visited[0] = True
		while not queue.empty():
			vertex = queue.get()
			bfs.append(vertex)
			for adj_vertex in adj[vertex]:
				if not visited[adj_vertex]:
					queue.put(adj_vertex)
					visited[adj_vertex] = True
		return bfs


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		queue = [0]
		visited = set()
		visited.add(0)
		res = []
		while queue:
			node = queue.pop(0)
			res.append(node)
			for nei in adj[node]:
				if nei not in visited:
					queue.append(nei)
					visited.add(nei)
		return res


from collections import deque

class Solution:

	def bfsOfGraph(self, V, adj):
		visited = [0] * V
		visited[0] = 1
		queue = deque([0])
		ans = []
		while queue:
			node = queue.popleft()
			ans.append(node)
			for neigh in adj[node]:
				if visited[neigh] == 0:
					queue.append(neigh)
					visited[neigh] = 1
		return ans


from typing import List
from queue import Queue
from collections import deque

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		ans = []
		queue = deque([0])
		visited = set()
		while queue:
			node = queue.popleft()
			if node in visited:
				continue
			visited.add(node)
			ans.append(node)
			for neighbor in adj[node]:
				if neighbor not in visited:
					queue.append(neighbor)
		return ans


from typing import List
from queue import Queue

class Solution:

	def bfsHelper(self, i, adj, visited, ans):
		q = Queue()
		q.put(i)
		while not q.empty():
			i = q.get()
			ans.append(i)
			for elem in adj[i]:
				if not visited[elem]:
					q.put(elem)
					visited[elem] = True

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		visited = [False for i in range(V)]
		ans = []
		visited[0] = True
		self.bfsHelper(0, adj, visited, ans)
		return ans


from typing import List
from queue import Queue
from collections import deque

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		visited = [False for i in range(V + 1)]
		q = deque()
		q.append(0)
		visited[0] = True
		ans = []
		while len(q) > 0:
			pop_val = q.popleft()
			ans.append(pop_val)
			for i in adj[pop_val]:
				if visited[i] == False:
					q.append(i)
					visited[i] = True
		return ans


from typing import List
from queue import deque

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		temp = []
		visited = [False] * V
		q = deque()
		q.append(0)
		visited[0] = True
		while q:
			curr = q.popleft()
			temp.append(curr)
			for i in adj[curr]:
				if visited[i] == False:
					q.append(i)
					visited[i] = True
		return temp


from typing import List
from queue import Queue
from collections import deque

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:

		def bfs(node, adj, vis):
			nonlocal traversal
			vis[node] = 1
			q = deque()
			q.append(node)
			while q:
				z = q.popleft()
				traversal.append(z)
				for adj_node in adj[z]:
					if vis[adj_node] == -1:
						vis[adj_node] = 1
						q.append(adj_node)
		vis = [-1] * V
		traversal = []
		bfs(0, adj, vis)
		return traversal


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		queue = Queue()
		visited = [False] * V
		result = []
		queue.put(0)
		visited[0] = True
		while not queue.empty():
			current = queue.get()
			result.append(current)
			for neighbor in adj[current]:
				if not visited[neighbor]:
					queue.put(neighbor)
					visited[neighbor] = True
		return result


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		visited = [0 for i in range(V)]
		visited[0] = 1
		que = [0]
		ans = []
		while len(que) != 0:
			elem = que[0]
			ans.append(elem)
			for elem in adj[elem]:
				if visited[elem] == 0:
					visited[elem] = 1
					que.append(elem)
			que.pop(0)
		return ans


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		q = Queue()
		q.put(0)
		visited = [0]
		while not q.empty():
			i = q.get()
			for j in adj[i]:
				if j not in visited:
					q.put(j)
					visited.append(j)
		return visited


from collections import deque
from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		visited = [False] * V
		queue = deque()
		bfsTraversal = []
		queue.append(0)
		visited[0] = True
		while queue:
			vertex = queue.popleft()
			bfsTraversal.append(vertex)
			for i in adj[vertex]:
				if visited[i] == False:
					queue.append(i)
					visited[i] = True
		return bfsTraversal


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		queue = [0]
		res = []
		visited = [-1] * V
		while len(queue) > 0:
			node = queue.pop(0)
			if visited[node] == -1:
				res.append(node)
				visited[node] = 1
			for neighbour in adj[node]:
				if visited[neighbour] == -1:
					queue.append(neighbour)
		return res


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		visit = []
		q = []
		bfs = []
		q.append(0)
		visit.append(0)
		while q:
			node = q.pop(0)
			bfs.append(node)
			for n in adj[node]:
				if n not in visit:
					q.append(n)
					visit.append(n)
		return bfs


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		que = []
		visited = [False for i in range(V)]
		ret = []
		que.append(0)
		while len(que) != 0:
			u = que[0]
			que.pop(0)
			visited[u] = True
			ret.append(u)
			for v in adj[u]:
				if not visited[v]:
					que.append(v)
					visited[v] = True
		return ret


from typing import List
from collections import deque

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		node = 0
		visited = [0] * V
		l = list()
		q = deque()
		l = self.solve(V, adj, node, visited, l, q)
		return l

	def solve(self, V, adj, node, visited, l, q):
		visited[node] = 1
		q.append(node)
		while len(q) != 0:
			node = q.popleft()
			l.append(node)
			for i in range(0, len(adj[node])):
				neigh = adj[node][i]
				if visited[neigh] == 0:
					visited[neigh] = 1
					q.append(neigh)
		return l


from typing import List
from collections import deque

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		(bfs, vis) = ([], [None] * V)
		q = deque([0])
		vis[0] = True
		while q:
			node = q.popleft()
			bfs.append(node)
			for it in adj[node]:
				if not vis[it]:
					vis[it] = True
					q.append(it)
		return bfs


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		q = [0]
		res = []
		visit = set()
		visit.add(0)
		while q:
			for _ in range(len(q)):
				node = q.pop(0)
				res.append(node)
				for nei in adj[node]:
					if nei not in visit:
						visit.add(nei)
						q.append(nei)
		return res


from typing import List
from queue import Queue

class Solution:

	def bfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		q = []
		cache = [0 for _ in range(V)]
		cache[0] = 1
		bfs = []
		q.append(0)
		while len(q):
			node = q.pop(0)
			bfs.append(node)
			for neighbour in adj[node]:
				if not cache[neighbour]:
					q.append(neighbour)
					cache[neighbour] = 1
		return bfs