1if __name__ == '__main__':
2    # Python code for minimum spanning tree
3    from collections import defaultdict
4
5    class Graph:
6        def __init__(self, num_vertices):
7            self.num_vertices = num_vertices
8            self.adj_list = defaultdict(list)
9
10        def add_edge(self, source, destination, weight):
11            self.adj_list[source].append((destination, weight))
12            self.adj_list[destination].append((source, weight))
13
14        def min_spanning_tree(self):
15            visited = set()
16            min_span_tree = []
17
18            # Select any starting vertex
19            start_vertex = next(iter(self.adj_list))
20            visited.add(start_vertex)
21
22            while len(visited) < self.num_vertices:
23                min_weight = float('inf')
24                min_edge = None
25
26                # For each visited vertex, find the edge with the minimum weight
27                for vertex in visited:
28                    for adj_vertex, weight in self.adj_list[vertex]:
29                        if adj_vertex not in visited and weight < min_weight:
30                            min_weight = weight
31                            min_edge = (vertex, adj_vertex)
32
33                # Add the minimum weight edge to the minimum spanning tree
34                min_span_tree.append(min_edge)
35                visited.add(min_edge[1])
36
37            return min_span_tree
38
39    # Create a graph with 7 vertices
40    g = Graph(7)
41
42    # Add edges to the graph
43    g.add_edge(0, 1, 4)
44    g.add_edge(0, 2, 3)
45    g.add_edge(1, 2, 1)
46    g.add_edge(1, 3, 2)
47    g.add_edge(2, 3, 4)
48    g.add_edge(3, 4, 2)
49    g.add_edge(4, 5, 6)
50    g.add_edge(4, 6, 3)
51    g.add_edge(5, 6, 1)
52
53    # Find the minimum spanning tree
54    min_span_tree = g.min_spanning_tree()
55
56    print('Minimum Spanning Tree:')
57    for edge in min_span_tree:
58        print(f'{edge[0]} -- {edge[1]}')