This is a Python program to find all connected components using DFS in an undirected graph.

The program creates a graph object and allows the user to find all connected components.

1. Create classes for Graph and Vertex.

2. Create a function label_all_reachable_helper that takes a Vertex object v, a set visited, a dictionary component and a label as arguments.

3. The function begins by adding v to visited and setting component[v] to label.

4. For each neighbour of v that is not in visited, label_all_reachable_helper is called.

5. Create a function label_all_reachable that takes a Vertex object, a dictionary component and a label as arguments.

6. It calls label_all_reachable_helper with v, an empty set for the set visited, component and label as arugments.

7. Thus, after the function is called, for each vertex in the component containing the source vertex, component[vertex] is set to label.

Here is the source code of a Python program to find all connected components using DFS in an undirected graph. The program output is shown below.

class Graph: def __init__(self): # dictionary containing keys that map to the corresponding vertex object self.vertices = {} def add_vertex(self, key): """Add a vertex with the given key to the graph.""" vertex = Vertex(key) self.vertices[key] = vertex def get_vertex(self, key): """Return vertex object with the corresponding key.""" return self.vertices[key] def __contains__(self, key): return key in self.vertices def add_edge(self, src_key, dest_key, weight=1): """Add edge from src_key to dest_key with given weight.""" self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight) def does_edge_exist(self, src_key, dest_key): """Return True if there is an edge from src_key to dest_key.""" return self.vertices[src_key].does_it_point_to(self.vertices[dest_key]) def add_undirected_edge(self, v1_key, v2_key, weight=1): """Add undirected edge (2 directed edges) between v1_key and v2_key with given weight.""" self.add_edge(v1_key, v2_key, weight) self.add_edge(v2_key, v1_key, weight) def does_undirected_edge_exist(self, v1_key, v2_key): """Return True if there is an undirected edge between v1_key and v2_key.""" return (self.does_edge_exist(v1_key, v2_key) and self.does_edge_exist(v1_key, v2_key)) def __iter__(self): return iter(self.vertices.values()) class Vertex: def __init__(self, key): self.key = key self.points_to = {} def get_key(self): """Return key corresponding to this vertex object.""" return self.key def add_neighbour(self, dest, weight): """Make this vertex point to dest with given edge weight.""" self.points_to[dest] = weight def get_neighbours(self): """Return all vertices pointed to by this vertex.""" return self.points_to.keys() def get_weight(self, dest): """Get weight of edge from this vertex to dest.""" return self.points_to[dest] def does_it_point_to(self, dest): """Return True if this vertex points to dest.""" return dest in self.points_to def label_all_reachable(vertex, component, label): """Set component[v] = label for all v in the component containing vertex.""" label_all_reachable_helper(vertex, set(), component, label) def label_all_reachable_helper(vertex, visited, component, label): """Set component[v] = label for all v in the component containing vertex. Uses set visited to keep track of nodes alread visited.""" visited.add(vertex) component[vertex] = label for dest in vertex.get_neighbours(): if dest not in visited: label_all_reachable_helper(dest, visited, component, label) g = Graph() print('Undirected Graph') print('Menu') print('add vertex <key>') print('add edge <src> <dest>') print('components') print('display') print('quit') while True: do = input('What would you like to do? ').split() operation = do[0] if operation == 'add': suboperation = do[1] if suboperation == 'vertex': key = int(do[2]) if key not in g: g.add_vertex(key) else: print('Vertex already exists.') elif suboperation == 'edge': src = int(do[2]) dest = int(do[3]) if src not in g: print('Vertex {} does not exist.'.format(src)) elif dest not in g: print('Vertex {} does not exist.'.format(dest)) else: if not g.does_undirected_edge_exist(src, dest): g.add_undirected_edge(src, dest) else: print('Edge already exists.') elif operation == 'components': component = dict.fromkeys(g, None) label = 1 for v in g: if component[v] is None: label_all_reachable(v, component, label) label += 1 max_label = label for label in range(1, max_label): print('Component {}:'.format(label), [v.get_key() for v in component if component[v] == label]) elif operation == 'display': print('Vertices: ', end='') for v in g: print(v.get_key(), end=' ') print() print('Edges: ') for v in g: for dest in v.get_neighbours(): w = v.get_weight(dest) print('(src={}, dest={}, weight={}) '.format(v.get_key(), dest.get_key(), w)) print() elif operation == 'quit': break

1. An instance of Graph is created.

2. A menu is presented to the user to perform various operations on the graph.

3. To find all connected components, a dictionary called component is created that contains all Vertex objects in the graph as keys and all of which are mapped to None.

4. Then for each Vertex object v in the graph, if v is mapped to None, label_all_reachable is called on that vertex with a given label. The value of the label is incremented for the next iteration of the loop.

5. The vertices in each component is then displayed.

Case 1: Undirected Graph Menu add vertex <key> add edge <src> <dest> components display quit What would you like to do? add vertex 1 What would you like to do? add vertex 2 What would you like to do? add vertex 3 What would you like to do? add vertex 4 What would you like to do? add vertex 5 What would you like to do? components Component 1: [1] Component 2: [2] Component 3: [3] Component 4: [4] Component 5: [5] What would you like to do? add edge 1 2 What would you like to do? components Component 1: [2, 1] Component 2: [3] Component 3: [4] Component 4: [5] What would you like to do? add edge 3 4 What would you like to do? components Component 1: [2, 1] Component 2: [4, 3] Component 3: [5] What would you like to do? add edge 1 5 What would you like to do? components Component 1: [2, 5, 1] Component 2: [4, 3] What would you like to do? add edge 2 4 What would you like to do? components Component 1: [4, 2, 5, 1, 3] What would you like to do? quit Case 2: Undirected Graph Menu add vertex <key> add edge <src> <dest> components display quit What would you like to do? components What would you like to do? add vertex 1 What would you like to do? add vertex 2 What would you like to do? components Component 1: [1] Component 2: [2] What would you like to do? add edge 1 2 What would you like to do? components Component 1: [1, 2] What would you like to do? add vertex 3 What would you like to do? components Component 1: [1, 2] Component 2: [3] What would you like to do? quit

**Sanfoundry Global Education & Learning Series – Python Programs.**

To practice all Python programs, __here is complete set of 150+ Python Problems and Solutions__.

**Related Posts:**

- Practice Programming MCQs
- Apply for Programming Internship
- Check Python Books
- Check Information Technology Books
- Apply for Python Internship