Advertisement
Miloz46

Python iterative and recursive dfs

May 20th, 2022 (edited)
709
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from dataclasses import dataclass
  2.  
  3. def create_list(size: int, element_to_append) -> list:
  4.     retval = []
  5.     for _ in range(size):
  6.         retval.append(element_to_append[:])
  7.     return retval
  8.  
  9. @dataclass
  10. class Graph:
  11.     vertices: list[list[int]]
  12.  
  13.     def __init__(self, filepath: str) -> None:
  14.         self.read_from_file(filepath)
  15.         pass
  16.  
  17.     def read_from_file(self, filepath: str) -> None:
  18.         with open(filepath) as file:
  19.             edges = int(next(file))
  20.             self.vertices = create_list(edges, [])
  21.             for line in file:
  22.                 source, dist = [int(x) for x in line.split()]
  23.                 self.vertices[source].append(dist)
  24.                 self.vertices[dist].append(source)
  25.         pass
  26.  
  27.     def recursive_dfs(self, head_element: int, path = None) -> None:
  28.         if path is None: path = []
  29.         path.append(head_element)
  30.         for neighbour in self.vertices[head_element]:
  31.             if neighbour not in path:
  32.                 print(neighbour)
  33.                 self.recursive_dfs(neighbour, path)
  34.         pass
  35.  
  36.     def iterative_dfs(self, head_element: int) -> None:
  37.         visited = [False for _ in range(len(self.vertices))]
  38.         stack = [head_element]
  39.         while stack:
  40.             current = stack.pop()
  41.             if not visited[current]:
  42.                 print(current)
  43.                 visited[current] = True
  44.                 for neighbour in self.vertices[current]:
  45.                     stack.append(neighbour)
  46.         pass
  47.  
  48. if __name__ == "__main__":
  49.     graph: Graph = Graph("graph-data.txt")
  50.     graph.recursive_dfs(0)
  51.     # graph.iterative_dfs(0)
  52.  
Advertisement
RAW Paste Data Copied
Advertisement