This is a Python program to implement Depth-First Search on a graph without using recursion.

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

1. Create classes for Graph, Vertex and Stack.

2. Create a function display_dfs that takes a Vertex object v as argument.

3. The function begins by creating an empty set called visited and a Stack object, s.

4. It pushes the passed Vertex object on the stack.

5. A while loop is created which runs as long as the stack is not empty.

6. In each iteration of the loop, a node is popped from the stack.

7. If the popped node has already been visited, skip to the next iteration of the loop.

8. Otherwise, the popped element is displayed and added to the set visited.

9. All of the neighbours of the popped element which have not already been visited are pushed on the stack.

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.

Here is the source code of a Python program to implement DFS traversal on a graph without using recursion. 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 class Stack: def __init__(self): self.items = [] def is_empty(self): return self.items == [] def push(self, data): self.items.append(data) def pop(self): return self.items.pop() def display_dfs(v): visited = set() s = Stack() s.push(vertex) while not s.is_empty(): current = s.pop() if current in visited: continue print(current.get_key(), end=' ') visited.add(current) for dest in current.get_neighbours(): if dest not in visited: s.push(dest) 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: ', end='') vertex = g.get_vertex(key) display_dfs(vertex) 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 perform DFS traversal starting at some vertex, display_dfs is called on that vertex.

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 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 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 edge 1 6 What would you like to do? add edge 5 6 What would you like to do? add edge 3 7 What would you like to do? dfs 1 Depth-first Traversal: 1 5 6 2 3 7 4 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? add vertex 2 What would you like to do? add vertex 3 What would you like to do? dfs 1 Depth-first Traversal: 1 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? dfs 1 Depth-first Traversal: 1 2 3 What would you like to do? add vertex 4 What would you like to do? add edge 3 4 What would you like to do? dfs 1 Depth-first Traversal: 1 2 3 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__.

**Related Posts:**

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