This is a Python program to print DFS numbering of a graph.

The program creates a graph object and allows the user to perform DFS traversal on it and print its DFS numbering.

1. Create classes for Graph and Vertex.

2. Create a function dfs_helper that takes a Vertex object v, a set visited, two dictionaries pre and post and a one-element list time as arguments.

3. time is used to keep track of the current time. It is passed as a one-element list so that it can be passed by reference.

4. The function begins by adding v to visited, incrementing time and setting pre[v] to the current value of time.

5. This is the discovered time.

6. For each neighbour of v that is not in visited, dfs_helper is called.

7. After the loop finishes, time is again incremented.

8. post[v] is set the current value of time.

9. This is the finished time.

10. Create a function dfs that takes a Vertex object v, and two dictionaries pre and post as arguments.

11. It calls dfs_helper with arguments v, an empty set for the set visited, the dictionaries pre and post, and a one-element list containing 0 for time.

12. Thus, the function dfs finds the DFS numbering starting at vertex v and stores the discovered and finished times in the dictionaries pre and post respectively.

13. 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.

Here is the source code of a Python program to print DFS numbering of 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 dfs(v, pre, post): """Display DFS traversal starting at vertex v. Stores pre and post times in dictionaries pre and post.""" dfs_helper(v, set(), pre, post, [0]) def dfs_helper(v, visited, pre, post, time): """Display DFS traversal starting at vertex v. Uses set visited to keep track of already visited nodes, dictionaries pre and post to store discovered and finished times and the one-element list time to keep track of current time.""" visited.add(v) time[0] = time[0] + 1 pre[v] = time[0] print('Visiting {}... discovered time = {}'.format(v.get_key(), time[0])) for dest in v.get_neighbours(): if dest not in visited: dfs_helper(dest, visited, pre, post, time) time[0] = time[0] + 1 post[v] = time[0] print('Leaving {}... finished time = {}'.format(v.get_key(), time[0])) g = Graph() print('Menu') print('add vertex <key>') print('add edge <src> <dest>') print('dfs <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 == 'dfs': key = int(do[1]) print('Depth-first Traversal: ') vertex = g.get_vertex(key) pre = dict() post = dict() dfs(vertex, pre, post) print() 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 print DFS numbering starting at some vertex, dfs is called on the vertex and two empty dictionaries pre and post to store the discovered and finished times.

Case 1: Menu add vertex <key> add edge <src> <dest> dfs <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 edge 1 2 What would you like to do? add edge 2 3 What would you like to do? add edge 3 4 What would you like to do? add edge 1 5 What would you like to do? add vertex 6 What would you like to do? add edge 1 6 What would you like to do? add edge 5 6 What would you like to do? dfs 1 Depth-first Traversal: Visiting 1... discovered time = 1 Visiting 2... discovered time = 2 Visiting 3... discovered time = 3 Visiting 4... discovered time = 4 Leaving 4... finished time = 5 Leaving 3... finished time = 6 Leaving 2... finished time = 7 Visiting 5... discovered time = 8 Visiting 6... discovered time = 9 Leaving 6... finished time = 10 Leaving 5... finished time = 11 Leaving 1... finished time = 12 What would you like to do? quit Case 2: Menu add vertex <key> add edge <src> <dest> dfs <vertex key> display quit What would you like to do? add vertex 1 What would you like to do? dfs 1 Depth-first Traversal: Visiting 1... discovered time = 1 Leaving 1... finished time = 2 What would you like to do? add vertex 2 What would you like to do? add edge 1 2 What would you like to do? dfs 1 Depth-first Traversal: Visiting 1... discovered time = 1 Visiting 2... discovered time = 2 Leaving 2... finished time = 3 Leaving 1... finished time = 4 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__.

**If you find any mistake above, kindly email to [email protected]**

**Related Posts:**

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