






from __future__ import annotations

from typing import Any


class     __SCREAMING_SNAKE_CASE					:






						def __init__(	self     ,						_UpperCamelCase   ):






												"""simple docstring"""
												lowerCAmelCase__    						=						num_of_nodes
												lowerCAmelCase__    						=						[]
												lowerCAmelCase__    						=						{}






						def       UpperCamelCase__      (	self     ,						_UpperCamelCase     ,						_UpperCamelCase     ,						_UpperCamelCase   ):






												"""simple docstring"""
												self.m_edges.append([u_node, v_node, weight]   )






						def       UpperCamelCase__      (	self     ,						_UpperCamelCase   ):






												"""simple docstring"""

												if self.m_component[u_node] == u_node:
																		return u_node
												return self.find_component(self.m_component[u_node]   )






						def       UpperCamelCase__      (	self     ,						_UpperCamelCase   ):






												"""simple docstring"""

												if self.m_component[u_node] != u_node:
																		for k in self.m_component:
																								lowerCAmelCase__    						=						self.find_component(_UpperCamelCase   )






						def       UpperCamelCase__      (	self     ,						_UpperCamelCase     ,						_UpperCamelCase     ,						_UpperCamelCase   ):






												"""simple docstring"""

												if component_size[u_node] <= component_size[v_node]:
																		lowerCAmelCase__    						=						v_node
																		component_size[v_node] += component_size[u_node]
																		self.set_component(_UpperCamelCase   )

												elif component_size[u_node] >= component_size[v_node]:
																		lowerCAmelCase__    						=						self.find_component(_UpperCamelCase   )
																		component_size[u_node] += component_size[v_node]
																		self.set_component(_UpperCamelCase   )







						def       UpperCamelCase__      (	self   ):






												"""simple docstring"""
												lowerCAmelCase__    						=						[]
												lowerCAmelCase__    						=						0

												lowerCAmelCase__    						=						[-1] * self.m_num_of_nodes

												# A list of components (initialized to all of the nodes)
												for node in range(self.m_num_of_nodes   ):
																		self.m_component.update({node: node}   )
																		component_size.append(1   )

												lowerCAmelCase__    						=						self.m_num_of_nodes

												while num_of_components > 1:
																		for edge in self.m_edges:
																								lowerCAmelCase__						,       lowerCAmelCase__						,       lowerCAmelCase__    						=						edge

																								lowerCAmelCase__    						=						self.m_component[u]
																								lowerCAmelCase__    						=						self.m_component[v]

																								if u_component != v_component:

																														for component in (u_component, v_component):
																																				if (
																																				    minimum_weight_edge[component] == -1
																																				    or minimum_weight_edge[component][2] > w
																																				):
																																										lowerCAmelCase__    						=						[u, v, w]

																		for edge in minimum_weight_edge:
																								if isinstance(_UpperCamelCase     ,						_UpperCamelCase   ):
																														lowerCAmelCase__						,       lowerCAmelCase__						,       lowerCAmelCase__    						=						edge

																														lowerCAmelCase__    						=						self.m_component[u]
																														lowerCAmelCase__    						=						self.m_component[v]

																														if u_component != v_component:
																																				mst_weight += w
																																				self.union(_UpperCamelCase     ,						_UpperCamelCase     ,						_UpperCamelCase   )
																																				print(F"Added edge [{u} - {v}]\nAdded weight: {w}\n"   )
																																				num_of_components -= 1

																		lowerCAmelCase__    						=						[-1] * self.m_num_of_nodes
												print(F"The total weight of the minimal spanning tree is: {mst_weight}"   )







def 	_UpperCamelCase   (    )  ->   None:

						"""simple docstring"""








if __name__ == "__main__":
					import doctest

					doctest.testmod()







from __future__ import annotations

__snake_case    :    Any         =     {
    """A""": ["""B""", """C""", """E"""],
    """B""": ["""A""", """D""", """E"""],
    """C""": ["""A""", """F""", """G"""],
    """D""": ["""B"""],
    """E""": ["""A""", """B""", """D"""],
    """F""": ["""C"""],
    """G""": ["""C"""],
}


class     __SCREAMING_SNAKE_CASE					:






						def __init__(	self     ,						_UpperCamelCase     ,						_UpperCamelCase   ):






												"""simple docstring"""
												lowerCAmelCase__    						=						graph
												# mapping node to its parent in resulting breadth first tree
												lowerCAmelCase__    						=						{}
												lowerCAmelCase__    						=						source_vertex






						def       UpperCamelCase__      (	self   ):






												"""simple docstring"""
												lowerCAmelCase__    						=						{self.source_vertex}
												lowerCAmelCase__    						=						None
												lowerCAmelCase__    						=						[self.source_vertex]  # first in first out queue

												while queue:
																		lowerCAmelCase__    						=						queue.pop(0   )
																		for adjacent_vertex in self.graph[vertex]:
																								if adjacent_vertex not in visited:
																														visited.add(_UpperCamelCase   )
																														lowerCAmelCase__    						=						vertex
																														queue.append(_UpperCamelCase   )







						def       UpperCamelCase__      (	self     ,						_UpperCamelCase   ):






												"""simple docstring"""
												if target_vertex == self.source_vertex:
																		return self.source_vertex

												lowerCAmelCase__    						=						self.parent.get(_UpperCamelCase   )
												if target_vertex_parent is None:
																		lowerCAmelCase__    						=						(
																		    F"No path from vertex: {self.source_vertex} to vertex: {target_vertex}"
																		)
																		raise ValueError(_UpperCamelCase   )

												return self.shortest_path(_UpperCamelCase   ) + F"->{target_vertex}"


if __name__ == "__main__":
					__snake_case    :    Optional[Any]         =     Graph(graph, """G""")
					g.breath_first_search()
					print(g.shortest_path("""D"""))
					print(g.shortest_path("""G"""))
					print(g.shortest_path("""Foo"""))





