Python Program to Find All Reachable Nodes in a Graph using DFS

This is a Python program to find all nodes reachable from a node using DFS in a graph.

Problem Description

The program creates a graph object and allows the user to find all nodes reachable from a node.

Problem Solution

1. Create classes for Graph and Vertex.
2. Create a function find_all_reachable_nodes_helper that takes a Vertex object v and a set visited as arguments.
3. The function begins by adding v to visited.
4. For each neighbour of v that is not in visited, find_all_reachable_nodes_helper is called.
5. Create a function find_all_reachable_nodes that takes a Vertex object v as argument.
6. It creates an empty set reachable.
7. It calls find_all_reachable_nodes_helper with v and the set reachable for the visited parameter.
8. The set reachable is returned.
9. Thus this function returns a set containing all nodes that can be reached from v.
10. This algorithm also works for undirected graphs. In an undirected graph, whenever edge (u, v) is added to the graph, the reverse edge (v, u) is also added.

Program/Source Code

Here is the source code of a Python program to find all nodes reachable from a node using DFS in a 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 __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 find_all_reachable_nodes(v):
    """Return set containing all vertices reachable from vertex."""
    reachable = set()
    find_all_reachable_nodes_helper(v, reachable)
    return reachable
 
 
def find_all_reachable_nodes_helper(v, visited):
    """Add all vertices visited by DFS traversal starting at v to the set visited."""
    visited.add(v)
    for dest in v.get_neighbours():
        if dest not in visited:
            find_all_reachable_nodes_helper(dest, visited)
 
 
g = Graph()
print('Menu')
print('add vertex <key>')
print('add edge <src> <dest>')
print('reachable <vertex key>')
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_edge_exist(src, dest):
                    g.add_edge(src, dest)
                else:
                    print('Edge already exists.')
 
    elif operation == 'reachable':
        key = int(do[1])
        vertex = g.get_vertex(key)
        reachable = find_all_reachable_nodes(vertex)
        print('All nodes reachable from {}:'.format(key),
              [v.get_key() for v in reachable])
 
    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
Program Explanation

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 nodes reachable from a vertex, find_all_reachable_nodes is called.

advertisement
advertisement
Runtime Test Cases
Case 1:
Menu
add vertex <key>
add edge <src> <dest>
reachable <vertex key>
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? add vertex 6
What would you like to do? add vertex 7
What would you like to do? add edge 1 2
What would you like to do? add edge 1 3
What would you like to do? add edge 4 5
What would you like to do? add edge 5 6
What would you like to do? reachable 1
All nodes reachable from 1: [2, 3, 1]
What would you like to do? reachable 4
All nodes reachable from 4: [6, 4, 5]
What would you like to do? reachable 7
All nodes reachable from 7: [7]
What would you like to do? quit
 
Case 2:
Menu
add vertex <key>
add edge <src> <dest>
reachable <vertex key>
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? reachable 1
All nodes reachable from 1: [1]
What would you like to do? add edge 1 2
What would you like to do? reachable 1
All nodes reachable from 1: [2, 1]
What would you like to do? reachable 2
All nodes reachable from 2: [2]
What would you like to do? add edge 2 1
What would you like to do? reachable 2
All nodes reachable from 2: [2, 1]
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.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.