How to Check Undirected Graph Connectivity Using BFS in Python

Submitted by razormist on Wednesday, March 11, 2026 - 23:03.

In this tutorial, we will learn how to program “How to Check Undirected Graph Connectivity Using BFS in Python.” The main objective is to understand how to implement undirected graph connectivity using BFS. This tutorial will guide you step by step through the process of implementing graph connectivity using BFS. By the end of this tutorial, you will have a solid understanding of graph connectivity, helping you strengthen your problem-solving abilities and improve your overall coding skills in data structure implementation.

This topic is straightforward and easy to understand. By simply following the instructions provided, you will be able to complete it with ease. The program will guide you step by step through the process of implementing linear search. So, let’s dive into the coding process and start implementing the solution to gain a deeper understanding of search algorithms in Python.

Getting Started:

First you will have to download & install the Python IDLE's, here's the link for the Integrated Development And Learning Environment for Python https://www.python.org/downloads/.

Creating Main Function

This is the main function of the application. The following code will display a simple GUI in terminal console that will display program. To do this, simply copy and paste these blocks of code into the IDLE text editor.

class Graph:
    def __init__(self):
        self.vertices = {}
 
    def add_vertex(self, key):
        vertex = Vertex(key)
        self.vertices[key] = vertex
 
    def get_vertex(self, key):
        return self.vertices[key]
 
    def __contains__(self, key):
        return key in self.vertices
 
    def add_edge(self, src_key, dest_key, weight=1):
        self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight)
 
    def does_edge_exist(self, src_key, 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):
        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 (self.does_edge_exist(v1_key, v2_key) and
                self.does_edge_exist(v2_key, v1_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 self.key
 
    def add_neighbour(self, dest, weight):
        self.points_to[dest] = weight
 
    def get_neighbours(self):
        return self.points_to.keys()
 
    def get_weight(self, dest):
        return self.points_to[dest]
 
    def does_it_point_to(self, dest):
        return dest in self.points_to
 
 
class Queue:
    def __init__(self):
        self.items = []
 
    def is_empty(self):
        return self.items == []
 
    def enqueue(self, data):
        self.items.append(data)
 
    def dequeue(self):
        return self.items.pop(0)
 
 
def label_all_reachable(vertex, component, label):
    visited = set()
    q = Queue()
 
    q.enqueue(vertex)
    visited.add(vertex)
 
    while not q.is_empty():
        current = q.dequeue()
        component[current] = label
 
        for dest in current.get_neighbours():
            if dest not in visited:
                visited.add(dest)
                q.enqueue(dest)
 
 
# MAIN PROGRAM
while True:
 
    print("\n================= Check Undirected Graph Connectivity =================\n")
 
    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("\nWhat would you like to do? ").split()
 
        if len(do) == 0:
            continue
 
        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):
                component_vertices = [v.get_key() for v in component
                                      if component[v] == label]
 
                print("Component {}:".format(label), component_vertices)
 
        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))
 
        elif operation == "quit":
            break
 
        else:
            print("Invalid command.")
 
    # Try Again Option
    opt = input("\nDo you want to try again? (yes/no): ").strip().lower()
 
    if opt == "no":
        print("Exiting program...")
        break
    elif opt != "yes":
        print("Invalid choice. Exiting program...")
        break

This program demonstrates how to check the connectivity of an undirected graph using Python. It defines a `Graph` class to manage vertices and edges, and a `Vertex` class to represent each node along with its neighboring vertices and edge weights. The graph supports operations such as adding vertices, creating undirected edges between vertices, checking whether an edge already exists, and displaying the graph structure. To determine connectivity, the program uses a Breadth-First Search (BFS) approach implemented in the `label_all_reachable` function, which explores all vertices reachable from a starting vertex and assigns them the same component label. By repeating this process for all unvisited vertices, the program identifies and prints the different connected components of the graph. A simple queue structure is used to manage the BFS traversal. Through a menu-driven interface, users can interactively build the graph, display its vertices and edges, and check its connected components until they choose to exit the program.

Output:

There you have it we successfully created How to Check Undirected Graph Connectivity Using BFS in Python. I hope that this simple tutorial help you to what you are looking for. For more updates and tutorials just kindly visit this site. Enjoy Coding!

More Tutorials for Python Language

Python Tutorials